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


Général

Résumé Chapitre entier

Points théoriques

PGCD et PPCM Algorithme d'Euclide

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5 Exercice 6

Prérequis

Résumé

Les notions de plus grand commun diviseur (PGCD) et plus petit commun multiple (PPCM) sont fondamentales en théorie des nombres, et ce chapitre commence par leur définition. Nous présentons ensuite l'algorithme d'Euclide permettant justement de calculer le PGCD de deux nombres entiers, aussi grands soient-ils. Outre cette possibilité, cet algorithme est également très utile d'un point de vue théorique. En effet, il nous permettra notamment par la suite de démontrer le théorème de Bézout et de calculer l'inverse d'un nombre en arithmétique modulaire.


Ce chapitre a été écrit par N. Radu et mis en ligne le 8 décembre 2014.

1. PGCD et PPCM

Définitions

Rappelons les définitions des PGCD et PPCM.

Définition
Le plus grand commun diviseur (PGCD) de deux nombres naturels $x$ et $y$, que nous noterons $(x,y)$ (ou parfois $\mathrm{pgcd}(x,y)$ pour être plus explicite), est comme son nom l'indique le plus grand nombre entier divisant $x$ et $y$ à la fois.

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

Définition
Le plus petit commun multiple (PPCM) de deux nombres naturels $x$ et $y$, parfois noté $[x,y]$ ou $\mathrm{ppcm}(x,y)$, est le plus petit nombre entier strictement positif multiple de $x$ et de $y$ à la fois.

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 nuls. 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 :

Propriété
Si $x, y \in \mathbb{N}_0$, on a toujours
$$(x,y) \cdot [x,y]=x \cdot y.$$

Démonstration
Si on regarde un seul facteur premier $p$ de la décomposition, il apparaît avec l'exposant $\min(e,f)$ dans $(x,y)$ et avec l'exposant $\max(e,f)$ dans $[x,y]$. Dans le membre de gauche de l'égalité, son exposant sera donc $\min(e,f)+\max(e,f)$. Dans le membre de droite, son exposant sera $e+f$, et la conclusion découle du fait que $$\min(e,f)+\max(e,f) = e+f.$$

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.

2. 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'Eucide 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.