PGCD et nombres premiers entre eux - cours

Le pgcd de deux entiers naturelsest leur plus grand diviseur commun.
On note pgcd (a, b) le pgcd des nombres a et b.

Nous allons calculer pgcd (72, 132) de quatre manières différentes :

Méthoden° 1 :

Recherchons tous les diviseurs des deux nombres.
Les diviseurs de 72 sont : 1 ; 2 ; 3 ; 4 ; 6 ; 8 ; 9 ; 12 ; 18 ; 24 ; 36; 72.
En effet : 72 = 1 x 72 = 2 x 36 = 3 x 24 = 4 x 18 = 6 x 12 =8 x 9.

Les diviseurs de 132 sont : 1 ; 2 ; 3 ; 4 ; 6 ; 11 ; 12 ; 22 ; 33 ; 44 ; 66 ; 132.
En effet : 132 = 1 x 132 = 2 x 66 = 3 x 44 = 4 x 33 = 6x 22 = 11 x 12.

Les diviseurs communs (présents dans les deux listes) sont : 1 ; 2; 3 ; 4 ; 6 ; 12.

Le plus grand diviseur commun est donc : 12.

Remarque : les diviseurs communs sont les diviseurs du pgcd.

Méthoden° 2 :

Décomposons les deux nombres en produits de facteurs premiers.
72= 2 x 2 x 2 x 3 x 3 = 2³x 3²
132= 2 x 2 x 3 x 11 = 2² x 3¹ x 11¹
Pour calculer le pgcd, nous sélectionnons les facteurs communs (présents dansles deux produits) ; s'ils figurent avec des exposants, nous leur attribuons leur plus petit exposant ; ensuite nous effectuons le produit :
pgcd(72, 132) = 2²x 3¹= 4 x 3 = 12

Méthoden° 3 :

Par soustractions successives.
Principe: si a < b, alors : pgcd (a, b) = pgcd (a, b – a).
Il est permis de remplacer le plus grand des deux nombres par la différence desdeux nombres ; ceci ne change pas le pgcd.
pgcd(72, 132) = pgcd (72, 132 - 72) = pgcd (72, 60)
pgcd (72, 60) =pgcd (72 - 60, 60) = pgcd (12, 60)
pgcd (12, 60) = pgcd (12, 60 -12) = pgcd (12, 48)
pgcd (12, 48) = pgcd (12, 48 - 12) = pgcd (12,36)
pgcd (12, 36) = pgcd (12, 36 - 12) = pgcd (12, 24)
pgcd(12, 24) = pgcd (12, 24 - 12) = pgcd (12, 12)

À partir de là, la solution est évidente : le pgcd est12.

Méthoden° 4 :

Par divisions successives (algorithme d’Euclide).
Principe: si a < b, alors : pgcd (a, b) = pgcd (a, b % a).
À la manière des informaticiens, nous notons b % a,  le reste de la division euclidienne de b para.
Il est permis de remplacer le plus grand des deux nombres par le reste de la division euclidienne du plus grand nombre par le plus petit; ceci ne change pas le pgcd.
132: 72 = 1 reste 60 ; remplaçons donc 132 par 60 :
pgcd (132,72) = pgcd (72, 60)
72: 60 = 1 reste 12 ; remplaçons donc 72 par 12 :
pgcd (72,60) = pgcd (60, 12)
60: 12 = 5 reste 0 ; remplaçons donc 60 par 0 :
pgcd (60, 12)= pgcd (12, 0)
À partir de là, la solution est évidente : le pgcd est 12.

Si deux nombres entiers n'ont aucun diviseur commun autre que 1, alors leur pgcd est égal à 1 ; on dit que ces nombres sont premiers entre eux.
Quand on divise deux nombres entiers par leur pgcd, on obtient deux nombres premiers entre eux.

Le pgcd est souvent utilisé dans les simplifications de fractions : La meilleure simplification possible consiste à diviser le numérateur et le dénominateur par leur pgcd ; on obtient directement la fraction irréductible.