algorithme d'euclide

L'algorithme d'Euclide est une méthode pour trouver pratiquement le PGCD de deux nombres sans avoir besoin de faire leur décomposition en facteurs premiers. Il est basé sur la propriété suivante :
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.
On fait donc des divisions euclidiennes, jusqu'à ce qu'on trouve un reste nul. Le dernier reste non nul est le pgcd de a et b.
Ex : 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
Le pgcd de 255 et 141 est donc 3.
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 une valeur possible pour ces entiers u et v. Il suffit pour cela de remonter les calculs, en exprimant le pgcd d en fonction des autres nombres, d'abord dans la dernière équation, puis dans la précédente, et ainsi de suite...
Ex : Pour 255 et 141, on élimine tout ce qui n'est pas 255 et 141.
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).
On somme tout, on regroupe, et on trouve :
38×141-21×255=3

---