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.