Calculer le PGCD : deux méthodes

Methode 1 : la liste des diviseurs

On liste tous les diviseurs de chaque nombre, puis on repere le plus grand qu'ils ont en commun. C'est simple mais long pour de grands nombres.

Exemple : PGCD(20, 30)

• Diviseurs de 20 : 1, 2, 4, 5, 10, 20
• Diviseurs de 30 : 1, 2, 3, 5, 6, 10, 15, 30
• Communs : 1, 2, 5, 10 -> PGCD(20, 30) = 10

Methode 2 : l'algorithme d'Euclide (plus rapide)

Cette méthode repose sur une regle : PGCD(a, b) = PGCD(b, reste de a divise par b), et on s'arrete quand le reste vaut 0. Le PGCD est alors le dernier reste non nul.

Exemple : PGCD(252, 105)

1. 252 = 105 x 2 + 42 -> on continue avec (105, 42)
2. 105 = 42 x 2 + 21 -> on continue avec (42, 21)
3. 42 = 21 x 2 + 0 -> reste nul, on s'arrete

Le dernier reste non nul est 21, donc PGCD(252, 105) = 21.

Comparaison des deux méthodes

Methode	Avantage	Inconvenient
Liste des diviseurs	Facile a comprendre	Long pour les grands nombres
Algorithme d'Euclide	Rapide, même pour de grands nombres	Demande de bien poser les divisions

Pieges classiques

• Ne pas confondre le quotient et le reste dans une division euclidienne : a = b x q + r, avec 0 <= r < b.
• Oublier de s'arreter des que le reste est 0 : le PGCD est le DIVISEUR de la derniere ligne, pas le reste precedent mal lu.
• Croire que l'algorithme d'Euclide ne marche que sur de petits nombres : c'est en realite l'inverse, il est surtout utile pour les grands nombres.