Algorithme d'Euclide

Théorie des nombres -- Divisibilité et congruence
Applications -- Algorithmique
Mathématiques interactives

  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 :
Consulter aussi...


http://www.bibmath.net