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 L'algorithme d'Euclide permet donc en particulier de calculer les inverses dans les anneaux d'entiers modulaires Z/nZ.

Exemple :

---

Premier nombre :
Deuxième nombre :