PGCD (Plus Grand Commun Diviseur)

Le PGCD (pour plus grand commun diviseur) de deux entiers est le plus grand entier naturel est un diviseur de ces deux entiers.

Méthode de calcul de PGCD 1 : lister les diviseurs des nombres et trouver le plus grand diviseur commun.

Méthode de calcul de PGCD 2 : utiliser l'algorithme d'Euclide (méthode préférée pour les calculatrice)

Etape 1. Réaliser une division euclidienne du plus grand des deux nombres A par le second B, pour trouver un dividende D et un reste R. Conserver les nombres B et R.

Etape 2. Répéter l'étape 1 (avec les nombres conservés : B devient le nouveau A et R devient le nouveau B) jusqu'à arriver à un reste nul.

Etape 3. Le PGCD des nombres A et B de départ est égal au dernier reste non nul.

Méthode de calcul de PGCD 3 : utiliser la décomposition en facteurs premiers

Le PGCD est le produit des facteurs communs (c'est à dire, la multiplication des nombres présents dans toutes les décompositions)

Méthode de calcul de PGCD 4 : connaissant le PPCM, utiliser la formule PGCD(a, b) = a * b / PPCM(a, b)

Méthode PGCD 1 : lister les diviseurs des nombres et trouver le plus grand commun.

Méthode PGCD 2 : utiliser la formule PGCD(a,b,c) = PGCD( PGCD(a,b) , c )

Méthode PGCD 3 : utiliser la décomposition en facteurs premiers

Le PGCD est la multiplication des facteurs communs

Pour simplifier une fraction, il est possible de diviser le numérateur et de démonimateur par leur PGCD afin d'obtenir une fraction irréductible.

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 $.

Deux nombres $ a $ et $ b $ sont dits premiers entre eux si leur PGCD est $ 1 $ : $ pgcd(a,b) = 1 $

Le PGCF est le plus grand commun facteur, c'est l'autre nom du PGCD.

Le programme convertit les nombres négatifs en positifs. 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, mais c'est le même à un coefficient -1 près. Par convention, seule la valeur positive est retenue. $$ PGCD(a,b) = PGCD(-a,b) = PGCD(a,-b) = PGCD(-a,-b) $$

Une méthode alternative aux divisions euclidiennes successive : les soustractions successives basé sur la propriété $$ pgcd(a,b) = pgcd(b,a) = pgcd(b,a-b) = pgcd(a,b-a) $$

Utiliser la formule $ PGCD(a,b) = (a \times b) / PPCM(a, b) $

avec $ a \times b $ le produit des 2 nombres et PPCM leur plus petit commun multiple

// 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);
}
// Python
def pgcd(a, b):
while b!=0:
a,b=b,a%b
return a


En utilisant la décomposition en facteurs premiers

$$ b = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_n^{a_n} $$

$$ c = q_1^{b_1} \times q_2^{b_2} \times \cdots \times q_m^{b_m} $$

Comme PGCD(b,c)=1, aucun des facteurs $ p $ n'est égal à un facteur $ q $. Or $ PGCD(a,b) $ est un produit de facteurs p et et $ PGCD(a,c) $ est un produit de facteurs $ q $ et $ PGCD(a, b \times c) $ est un produit de facteurs $ p $ et $ q $. Donc $ PGCD(a, b \times c) = PGCD(a,b) \times PGCD(a,c) $

Les calculatrices intègrent les fonctions de PGCD sous le nom de GCD (Greatest Common Divisor). Si non voici des programmes

Pour Casio// Calcul PGCD
"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

Pour TI (82,83,84,89)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

Le PGCD est un diviseurs communs à 2 nombres, donc un nombre plus petit ayant les 2 nombres comme multiples.

Le PPCM est un multiple commun à 2 nombres, donc un nombre plus grand ayant les 2 nombres comme diviseurs.

Le PGCD et le PPCM sont reliés par la formule : $$ PGCD(a, b) = \frac{ a \times b }{ PPCM(a, b) } $$