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

Idée première

Derrière l'algorithme d'Euclide se cache une propriété simple :
$$(a,b) = (a-b,b) \quad \text{ si } \quad a \geq b \geq 0 \quad \text{($a,b \in \mathbb{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\cdot b, b) \quad \text{ tant que} \quad a-k\cdot b \geq 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\cdot 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\cdot 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 :
$$\begin{align} (78,33) &= (78-2 \cdot 33, 33) = (12,33)\\ (33,12) &= (33-2 \cdot 12,12) = (9,12)\\ (12,9) &= (12-1 \cdot 9,9) = (3,9)\\ (9,3) &= (9-3 \cdot 3,3) = (0,3) = \boxed{3} \end{align}$$ Une façon plus courante et plus pratique d'écrire cet algorithme est d'écrire les divisions euclidiennes successives :
$$\begin{align} 78 &= 2 \cdot 33 + 12\\ 33 &= 2 \cdot 12 + 9\\ 12 &= 1 \cdot 9 + \boxed{3}\\ 9 &= 3 \cdot 3 + 0 \end{align}$$ 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
$$\begin{align} a &= q_0 \cdot b + r_0\\ b &= q_1 \cdot r_0 + r_1\\ r_0 &= q_2 \cdot r_1 + r_2\\ &\vdots\\ r_{n-2} &= q_{n} \cdot r_{n-1} + \boxed{r_n}\\ r_{n-1} &= q_{n+1} \cdot r_n + 0\\ \end{align}$$ 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] = \frac{a.b}{(a,b)}.$$ Dans notre exemple, on a directement que $$[78,33] = \frac{78 \cdot 33}{3} = 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.