Processing

Théorie > Théorie des nombres > Algorithme d'Euclide

Algorithme d'Euclide

Idée première

Derrière l'algorithme d'Euclide se cache une propriété simple :
(a,b)=(ab,b) si ab0(a,bN). 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 ab et b. En effet, tout élément divisant a et b divise également ab, et inversement, tout élément divisant ab 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 ab et b.

En appliquant cette égalité k fois à la suite, on a même
(a,b)=(akb,b) tant queakb0.

L'algorithme

Lorsque l'on désire calculer le PGCD de deux nombres a et b, on peut donc remplacer a par akb, 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 aqb 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)=(78233,33)=(12,33)(33,12)=(33212,12)=(9,12)(12,9)=(1219,9)=(3,9)(9,3)=(933,3)=(0,3)=3 Une façon plus courante et plus pratique d'écrire cet algorithme est d'écrire les divisions euclidiennes successives :
78=233+1233=212+912=19+39=33+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=q0b+r0b=q1r0+r1r0=q2r1+r2rn2=qnrn1+rnrn1=qn+1rn+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]=78333=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.