Déterminer le PGCD de deux nombres
Méthode :
Lister les diviseurs de chacun des nombres et sélectionner le plus grand diviseur commun.
Exemple : déterminer le PGCD de 63 et de 42.
\(63=\underline{1}\times63=\underline{3}\times\underline{21}=\underline{7}\times9\)
\(42=\underline{1}\times42=2\times\underline{21}=\underline{3}\times14=6\times\underline{7}\)
Le PGCD de 63 et de 42 est 21
Méthode :
Décomposer chacun des nombres en produit de facteurs premiers.
Exemple : Déterminer le PGCD de 60 et 126.
\(60={\color{red}{2}}\times2\times{\color{red}{3}}\times5\)
\(126={\color{red}{2}}\times{\color{red}{3}}\times3\times7\)
Les facteurs communs sont 2 et 3 ; Le PGCD de 60 et 126 est \(2\times3=6\).
Méthode : Algorithme des différences
On effectue la soustraction du plus grand par le plus petit, puis on remplace le plus grand par la différence, et on recommence jusqu'à ce que la différence soit nulle. Le PGCD est, alors, le dernier résultat non nul.
Exemple : Déterminer le PGCD de 12 et 28.
\(\begin{eqnarray*}28-12 & = & 16\\16-12 & = & 4\\12-4 & = & 8\\8-4 & = & 4\\4-4 & = & 0\end{eqnarray*}\)
Le dernier résultat non nul est 4, donc le PGCD de 12 et 28 est 4.
Méthode : Algorithme d'Euclide
On effectue la division euclidienne du plus grand par le plus petit et on recommence avec le diviseur et le reste, jusqu'à ce que le reste soit nul. Le PGCD est alors le dernier reste non nul.
Exemple : Déterminer le PGCD de 360 et 128.
\(\begin{array}{c@{=}c@{\times}c@{+}c}Dividende & Diviseur & Quotient & Reste\\360 & 128 & 2 & 104 \\128 & 104 & 1 & 24 \\104 & 24 & 4 & 8 \\24 & 8 & 3 & 0 \\\end{array}\)
Le dernier reste non nul est 8, donc le PGCD de 360 et 128 est 8.