Algorithme d'Euclide
Quel est le plus grand diviseur commun (=pgcd) de 126 et 462? On apprend au collège à calculer ce pgcd en décomposant les 2 nombres en produits de facteurs premiers, et en réunissant les facteurs en commun. Cette méthode n'est plus envisageable quand les entiers deviennent grands (plusieurs centaines de chiffres décimaux), car la factorisation est un problème difficile. On calcule donc le pgcd en appliquant l'algorithme d'Euclide, qui repose sur la constation suivante :On effectue donc des divisions euclidiennes, jusqu'à ce qu'on trouve un reste nul. Le dernier reste non nul est le pgcd de a et b.
Si a et b sont deux entiers avec par exemple a>=b, si r est le reste de a par b, alors le pgcd de a et b vaut le pgcd de b et r.
Exemple 1 :
On souhaite calculer le pgcd de 255 et 141.
- 255=1×141+114
- 141=1×114+27
- 114=4×27+6
- 27=4×6+3
- 6=2×3+0
L'algorithme d'Euclide permet aussi de calculer les coefficients de Bezout de a et b (on l'appelle algorithme d'Euclide étendu). Rappelons que si d est le PGCD de a et b, il existe des entiers u et v tels que au+bv=d. L'algorithme d'Euclide permet de calculer ces coefficients u et v. Pour cela, il suffit de remonter les calcules, en exprimant le pgcd d en fonction des autres nombres.
Exemple 2 :
Pour 255 et 141, on élimine tout ce qui n'est pas ni 255, ni 141, ni 3.
- 27=4×6+3
- 114=4×27+6 ×(-4) (on élimine les 6).
- 141=1×114+27 ×17 (on élimine les 27, il y en a 1 à gauche, et -16 à droite).
- 255=1×141+114 ×(-21) (on élimine les 114).