Rechercher un outil sur dCode.fr

PGCD - Plus grand commun diviseur

Le plus grand commun diviseur de deux entiers est le plus grand entier naturel qui divise simultanément ces deux entiers.

dCode est ton ami !

Plus aucun jeu, plus aucune énigme, plus aucune chasse au trésor ne vous résisteront !
Ecrire à l'auteur de dCode

PGCD - Plus grand commun diviseur

Annonces sponsorisées :

Calculer le PGCD de plusieurs nombres

Separer les nombres par des espaces, séparer les calculs par un retour à la ligne.

Nombres premiers entre eux

Deux nombres a et b sont dits premiers entre eux si il n'y a aucun nombre à part 1 qui soit à la fois diviseur de a et de b.

PGCD et nombres négatifs

Le programme ne gère pas les nombres négatifs. Cependant pour être rigoureux mathématiquement, tout dépend de la définition du PGCD retenue, défini sur N*, il est toujours positif, défini sur Z* il est positif ou négatif, c'est le même à un coefficient -1 près.
Dans ce second cas, pour toutes les solutions proposées l'opposé est aussi valable : PGCD(6,9) = PGCD(-6,9) = PGCD(6,-9) = PGCD(-6,-9) = 3 (ou -3). Par convention, seule la valeur positive est retenue.

Algorithme du PGCD


// JAVASCRIPT
function pgcd(a,b) {
 return (b==0)?a:pgcd(b,a%b);
}

// PHP
function pgcd($a,$b) {
 return ($b==0)?$a:pgcd($b,$a%$b);
}

Programmation PGCD sur calculatrice

Casio

"A=" : ? -> R
"B=" : ? -> Y
I -> U : 0 -> W : 0 -> V : I -> X
While Y <> 0
Int(R/Y) -> Q
U -> Z : W -> U : Z-Q*W -> W
V -> Z : X -> V : Z-Q*X -> X
R -> Z : Y -> R : Z-Q*Y -> Y
WhileEnd
"U=" : U : "V=" : V
"PGCD=" : R

TI Texas Instrument

Input "A=", R
Input "B=", Y
I -> U : 0 -> W : 0 -> V : I -> X
While Y <> 0
Int(R/Y) -> Q
U -> Z : W -> U : Z-Q*W -> W
V -> Z : X -> V : Z-Q*X -> X
R -> Z : Y -> R : Z-Q*Y -> Y
End
Disp "U=", U, "V=3, V
Disp "PGCD=", R

Démontrer que PGCD(b,c)=1, alors PGCD(a,b*c) = PGCD(a,b).PGCD(a,c)

En utilisant la décomposition en facteurs premiers :
b = p1^a1 * p2^a2 * ... * pn^an
c = q1^b1 * q2^b2 * ... * qm^bm
Comme PGCD(b,c)=1, aucun des facteurs p n'est égal à un q.

Or PGCD(a,b) = un produit de facteurs p
Et PGCD(a,c) = un produit de facteurs q
PGCD(a,b*c) = un produit de facteurs p et q
Donc PGCD(a,b*c) = PGCD(a,b).PGCD(a,c)

Code source

dCodeur se réserve la propriété du code source du script PGCD - Plus grand commun diviseur. Toute demande écrite pour un applet (déchiffrement, chiffrement, encodage, décodage, encryptage, décryptage, traduction, traducteur, conversion, solveur), une fonction (décrypter, encrypter, déchiffrer, chiffrer, décoder, code, traduire, convertir, résoudre) ou un script en langage Java, C++, PHP, Python, etc. pourra être formulée via la page contact.

Commentaires

Outils similaires

Recommander

Mots-clés

pgcd - ppcm - diviseur - division - euclidienne - commun - grand - plus - euclide

Rechercher un outil sur dCode.fr