PGCD

Calcul du PGCD (ou Plus Grand Commun Diviseur) de deux ou plusieurs nombres.

Qu'est ce que le PGCD ?

Le PGCD (ou Plus Grand Commun Diviseur) de deux entiers est le plus grand diviseur commun à ces deux entiers.

Exemple: quelle est le PGCD de 14 et 49 ?

Diviseurs de 14 = 1, 2, 7, 14
Diviseurs de 49 = 1, 7, 49

On remarque que les diviseurs communs à 14 et 49 sont 1 et 7. Le PGCD est le plus grand d'entre eux, donc,
PGCD(14 , 49) = 7.

Comment calculer le PGCD ?

Il existe plusieurs méthodes pour calculer le PGCD.

Méthode des diviseurs

C'est la méthode qui découle directement de la définition (ou méthode force brute). Elle est applicable pour trouver le PGCD de deux ou plusieurs nombres. Voici les étapes à suivre,
• Lister les diviseurs des nombres (on peut utiliser ce calculateur Trouver les diviseurs d'un nombre).
• Extraire la liste des diviseurs communs.
• Le PGCD est le plus grand nombre de cette dernière liste.

Exemple : Quelle est le PGCD de 54 et 81 ?

Diviseurs de 54 = 1, 2, 3, 6, 9, 18, 27, 54
Diviseurs de 81 = 1, 3, 9, 27, 81

La liste des diviseurs communs à 54 et 81 est 1, 3, 9, 27
Le plus grand nombre de cette liste est 27. On déduit,
PGCD (54 , 81) = 27

A part pour les petits nombres, la méthode force brute n'est pas recommandée car elle exige de calculer les diviseurs des nombres, ce qui peut être lent et fastidieux pour les grands nombres.

Méthode d'Euclide

Appelée aussi 'Méthode des divisions successives', cette méthode est la conséquence de la propriété suivante,

Soit A, B, q et r des entiers naturels. Si A = B.q + r alors PGCD(A , B) = PGCD(B , r)

La méthode d'Euclide consiste à appliquer successivement cette égalité avec q et r égaux respectivement aux quotient et reste de la division euclidienne de A par B.

Pour trouver le PGCD de A et B, on procéde par étapes comme suit,

• Faire la division euclidienne de A (le plus grand des deux entiers) par B, on obtient un quotient q et un reste r.
• Répéter la même opération en remplaçant le couple (A,B) par (b,r). On obtient q' et r', quotient et reste de la division euclidienne de b par r.
• Répéter l'opération avec (r , r') et ainsi de suite jusqu'à arriver à un reste nul.
• Le PGCD est égale au dernier reste non nul.

Exemple: Quelle est le PGCD de 544 et 88 ?

• 544 ÷ 88 = 6 reste 16
• 88 ÷ 16 = 5 reste 8
• 16 ÷ 8 = 2 reste 0

Le dernier reste non nul est 8 donc PGCD (544 , 88) = 8.

Dans chaque étpape, on garde le reste calculé dans l'étape précédente et le plus petit nombres entre le dividende et le diviseur. On répète le processus jusqu'à ce qu'on obtienne un reste nul.

Cette méthode est, en général, la plus rapide et la plus recommandée pour trouver le PGCD de deux nombres. Elle n'est pas applicable pour plus de deux nombres.

Méthode avec factorisation

On illustre cette méthode avec l'exemple suivant : quelle est le PGCD de 3960 et 18900 ?

• On factorise les deux nombres,

`3960 = 2^3*3^2*5*11` (factoriser 3960)
`18900 = 2^2*3^3*5^2*7` (factoriser 18900)

• On va calculer le PGCD à partir de sa décomposition en facteurs premiers car ses facteurs premiers sont les facteurs premiers communs à 3960 et 18900. Ainsi,
les facteurs premiers de 3960 sont 2, 3, 5 et 11.
les facteurs premiers de 18900 sont 2, 3, 5 et 7.
les facteurs premiers du PGCD sont donc 2, 3, 5.

Chaque facteur aura l'exposant le plus petit des deux factorisations. Ainsi,
2 aura un exposant 2 (on compare les exposants 3 et 2 dans `2^3` et `2^2` en prenant le plus petit exposant)
3 aura un exposant 2 (c'est le plus petit exposant de `3^2` comparé à `3^3`)
5 aura un exposant 1 (c'est le plus petit exposant de `5^1` comparé à `5^2`)

On a donc,

`PGCD ( 3960 , 18900 ) = 2^2 * 3^2 * 5 = 180`

Cette méthode est la plus recommandée pour calculer le PGCD de plus de deux nombres.

Méthode des soustractions successives

Cette méthode découle du principe suivant. Si p divise A et p divise B alors p divise A - B.

On en déduit que PGCD (A , B) divise A - B, puisque PGCD (A , B) est un diviseur commun à A et B.

Pour calculer le PGCD de A et B (A > B), on applique cette proprité de manière répétée.

• Etape 1 : PGCD (A , B) divise A - B
• Etape 2 : PGCD (A , B) divise A - B et PGCD (A , B) divise B, donc, il divise leur différence A - B - B = A - 2×B
• On répéte ce processus jusqu'à obtention d'une différence nulle. Prenons un exemple pour être plus concret.

Quelle est le PGCD de 72 et 32 ?

A=72  B=32

72 - 32 = 40  (A - B)
40 - 32 = 8
32 - 8 = 24
24 - 8 = 16
16 - 8 = 8
8 - 8 = 0

Dans chaque étape, on calcule la différence entre la résultat de l'étape précédente et du plus petit des deux autres nombres. On s'arrête quand le résultat est égal à 0.

le PGCD est le dernier résultat non nul (dans cet exemple 8). PGCD (72 , 32) = 8

Si on atteint une différence de 1, le PGCD est égale à 1. On dit que les deux nombres sont premiers entre eux.

Cette méthode ne s'applique pas à plus de deux nombres. De plus, en dehors des petits nombres, elle peut être longue et fastidieuse dans certains cas.

Quelle méthode choisir ?

Si on doit choisir une seule méthode parmi les quatres, la méthode d'Euclide est la meilleure et la plus rapide, avec les nuances suivantes.

Cas de deux nombres
Pour les petits nombres, les méthodes 'recherche de diviseurs' et 'différences successives' peuvent suffire.
Pour les grands nombres, la méthode d'Euclide est recommandée.

Cas de plus de deux nombres
La méthode par factorisation est recommandée sauf pour les petits nombres où la méthode de recherche des diviseurs (force brute) peut suffire.

Cas particuliers

• PGCD ( A , 0 ) = |a|  A étant un entier relatif.
• Si B divise A, alors PGCD (A , B ) = b.
• Si PGCD ( A , B ) = 1, on dit que A et B sont des nombres premiers entre eux (ou étrangers).

Propriétés du PGCD (avancé)

A et B sont deux entiers non nuls alors,

• PGCD ( A , B ) divise PPCM( A , B ) (plus petit commun multiple commun)

• Si on multiplie A et B par un même entier naturel k alors, leur PGCD est multiplié par k.
PGCD ( k.A , k. B ) = k.PGCD ( A , B )

• Le produit du PGCD et du PPCM est égal à la valeur absolue du produit des deux nombres.
PGCD (A , B) x PPCM (A , B) = | A x B |

• Tout diviseur commun à A et B divise leur PGCD. Autrement dit,
Si p | A et p | B  alors  p divise PGCD(A , B).

Programmation

Voici comment on programme le calcul du PGCD de deux nombres entiers.

Python

def pgcd(a,b):
    while b:
        a, b = b, a%b
    return a

Voir aussi

Trouver les diviseurs d'un nombre
PPCM (plus petit commun multiple)
Division euclidienne

---