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


Général

Introduction Chapitre entier

Points théoriques

PGCD et PPCM Algorithme d'Euclide

Exercices

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

PGCD et PPCM

Définitions

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, $(15,20)=5$.

De manière similaire, 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. 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 = [a, 0]$ car tous les entiers (non nuls) divisent $0$.

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 :

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

En effet, 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.