Algorithme d'Euclide
Idée première
Derrière l'algorithme d'Euclide se cache une propriété simple :
(a,b)=(a−b,b) si a≥b≥0(a,b∈N). Cette égalité découle du fait que l'ensemble des diviseurs communs de a et b est le même que l'ensemble des diviseurs communs de a−b et b. En effet, tout élément divisant a et b divise également a−b, et inversement, tout élément divisant a−b et b divise également a.
De là, il est évident que le plus grand commun diviseur de a et b est égal au plus grand commun diviseur de a−b et b.
En appliquant cette égalité k fois à la suite, on a même
(a,b)=(a−k⋅b,b) tant quea−k⋅b≥0.
L'algorithme
Lorsque l'on désire calculer le PGCD de deux nombres a et b, on peut donc remplacer a par a−k⋅b, un nombre plus petit. Autant prendre k le plus grand possible, à savoir le quotient q de la division euclidienne de a par b. Remplacer a par a−q⋅b revient donc à remplacer a par le reste de la division euclidienne de a par b.
L'algorithme d'Euclide consiste à appliquer cette opération plusieurs fois de suite jusqu'à ce que l'un des deux nombres soit égal à 0. Puisque rien ne vaut un bon exemple, calculons (78,33) à l'aide de cet algorithme :
(78,33)=(78−2⋅33,33)=(12,33)(33,12)=(33−2⋅12,12)=(9,12)(12,9)=(12−1⋅9,9)=(3,9)(9,3)=(9−3⋅3,3)=(0,3)=3 Une façon plus courante et plus pratique d'écrire cet algorithme est d'écrire les divisions euclidiennes successives :
78=2⋅33+1233=2⋅12+912=1⋅9+39=3⋅3+0 On constate qu'il suffit d'effectuer la division euclidienne de a par b (ici 78 et 33), puis de recommencer en remplacant a par b (33) et b par le reste obtenu (12). On effectue ainsi une succession de divisions euclidiennes, et le PGCD est finalement donné par le dernier reste non-nul trouvé (3 sur notre exemple).
En toute généralité, on écrit
a=q0⋅b+r0b=q1⋅r0+r1r0=q2⋅r1+r2⋮rn−2=qn⋅rn−1+rnrn−1=qn+1⋅rn+0 Remarquons à nouveau qu'en calculant ainsi le PGCD des nombres a et b, on a également calculé leur PPCM puisque l'on a vu précédemment que
[a,b]=a.b(a,b). Dans notre exemple, on a directement que [78,33]=78⋅333=858.
Importance
En plus d'être très efficace d'un point de vue calculatoire (il est couramment utilisé en informatique), cet algorithme est très utile d'un point de vue théorique. C'est grâce à lui que nous allons démontrer sans peine le théorème de Bézout, résultat phare d'un prochain chapitre.