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

Définitions

Rappelons les définitions des PGCD et PPCM.


Par exemple, on a $(15,20)=5$.


On a par exemple $[15,20] = 60$.

Remarque : Ces deux notions ne sont pas bien définies lorsque les deux nombres sont nuls. On supposera donc toujours être dans le cas où l'un des deux nombres est différent de $0$. Par contre, elles ont tout à fait un sens lorsqu'un seul des deux nombres est nul. Dans ce cas, on a $(a,0) = a$ et $[a, 0] = 0$ car tous les entiers non-nuls divisent $0$ et $0$ ne divise aucun entier non-nul.

Calcul

Si les décompositions en facteurs premiers de $x$ et de $y$ sont connues, alors il est aisé de calculer leur PGCD et PPCM. En effet, notons
$$x = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_n^{e_n},$$ $$y = q_1^{f_1} \cdot q_2^{f_2} \cdot \ldots \cdot q_m^{f_m}$$ les décompositions des deux nombres. Quitte à rajouter des termes avec exposant $0$ (rappelons que $x^0 = 1$ par convention si $x \neq 0$), nous pouvons supposer que les $p_i$ et $q_i$ apparaissant dans les deux décompositions sont les mêmes (par exemple, au lieu d'écrire $15 = 3^1 \cdot 5^1$ et $20 = 2^2 \cdot 5^1$, on peut écrire $15 = 2^0 \cdot 3^1 \cdot 5^1$ et $20 = 2^2 \cdot 3^0 \cdot 5^1$) :
$$x = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_n^{e_n},$$ $$y = p_1^{f_1} \cdot p_2^{f_2} \cdot \ldots \cdot p_n^{f_n}.$$ De là, nous pouvons déduire la décomposition en facteurs premiers de $(x,y)$ et $[x,y]$. En effet, $(x,y)$ doit tout d'abord diviser les deux nombres $x$ et $y$, donc ses facteurs premiers doivent forcément être des éléments $p_i$. Et à chaque facteur $p_i$, vu que nous cherchons le plus grand diviseur, il est optimal de mettre le plus grand exposant possible. Pour continuer à diviser $x$ et $y$, l'exposant à mettre est $\min(e_i,f_i)$. Ainsi, on en déduit
$$(x,y) = p_1^{\min(e_1,f_1)} \cdot p_2^{\min(e_2,f_2)} \cdot \ldots \cdot p_n^{\min(e_n,f_n)}.$$ De la même façon, on trouve que
$$[x,y] = p_1^{\max(e_1,f_1)} \cdot p_2^{\max(e_2,f_2)} \cdot \ldots \cdot p_n^{\max(e_n,f_n)}.$$ Ainsi, pour notre exemple, on retrouve bien
$$(15,20) = 2^{\min(0,2)} \cdot 3^{\min(1,0)} \cdot 5^{\min(1,1)} = 2^0 \cdot 3^0 \cdot 5^1 = 5,$$ $$[15,20] = 2^{\max(0,2)} \cdot 3^{\max(1,0)} \cdot 5^{\max(1,1)} = 2^2 \cdot 3^1 \cdot 5^1 = 60.$$

Première propriété

Cette constatation nous permet de démontrer le résultat suivant :



Sur notre exemple, remarquons que l'on a bien
$$(15,20) \cdot [15,20] = 5 \cdot 60 = 300 = 15 \cdot 20.$$

Difficulté

Malheureusement, on ne connaît pas toujours la décomposition en facteurs premiers des nombres qui nous intéressent. Nous allons cependant voir qu'il existe un moyen très efficace pour calculer le PGCD de deux nombres : l'algorithme d'Euclide. De plus, au vu de la formule précédente reliant le PGCD et le PPCM, on sera également en mesure de calculer le PPCM de deux nombres.

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.