PGCD (2). Algorithme d'Euclide. PPCM

 Cet article fait suite à 

• PGCD (1) . Algorithme des soustractions successives

Dans ce billet, nous voyons un algorithme permettant de calculer le plus grand commun diviseur de deux entiers (le pgcd) plus efficace que l'algorithme des soustractions successives. Cette algorithme basé sur des divisions euclidiennes successives s'appelle l'algorithme d'Euclide. Un script Python est donné plus bas. 

Ensuite, nous définissons le plus petit commun multiple (ppcm) de deux entiers et nous donnons une relation le reliant au pgcd.

Algorithme d'Euclide

On peut améliorer la méthode précédente à partir de la remarque suivante sur la division euclidienne.

Lorsque l'on retire $b$ (avec $0 < b\leq a$) à $a$ plusieurs fois jusqu'à ce que le résultat obtenu soit inférieur à $b$, on fait en fait une division euclidienne : 

$$a-bq=r$$

où $0\leq r<b$ est le reste de la division euclidienne de $a$ par $b$, et $q$ le quotient de cette même division qui est le nombre maximum de fois que l'on peut retirer $b$ à $a$ avant que le résultat ne devienne négatif.

Cela revient donc à faire une division au lieu de faire $q$ soustractions, ce qui s'avère utile lorsque le calcul d'un division ne demande pas plus d'effort que celui d'un soustraction. 

Exemple numérique.

On peut reprendre l'exemple de l'article [] en remplaçant plusieurs soustractions par le même nombre par une division :

• $2051=2\times 1001 + 49$
• $1001=20\times 49 + 21$
• $49=2\times 21 +7$
• $21=3\times 7$

On en déduit que $7$ est le plus grand commun diviseur de $2051$ et $1001$ en seulement $4$ étapes, au lieu de $26$.

Théorème (Algorithme d'Euclide).

Soit $a,b$ deux entiers tels que $0< b \leq a$.

On pose 

$$\left\{\begin{array}{rclr} r_0     & = & a &\\ r_1     & =&b&\\r_{n+2}&=& \textrm{reste de la division euclidienne de } r_{n+1} \textrm{par } r_{n} & (n\in\mathbb N, r_n>0) \end{array} \right.$$

Alors la suite $(r_n)$ est décroissante et stationnaire en $\textrm{pgcd}(a,b)$.

Plus précisément, il existe un entier $t\geq 1$ tel que $r_{t}>0$ et $r_{t+1}=0$ et pour tout entier $k\leq t$, on a $r_{k+1}<r_k$.  

Preuve. 

Tout d'abord, on montre que pour tout entier naturel $n$, $\textrm{pgcd}(r_n,r_{n+1}=\textrm{pgcd}(a,b)$. 

Notons $d=\textrm{pgcd}(a,b)$.

Pour $n=0$, il n'y a rien à montrer.

Supposons que pour un certain $n$, $\textrm{pgcd}(r_n,r_{n+1}=\textrm{pgcd}(a,b)$.

On a $r_{n}=r_{n+1}q+r_{n+2}$, avec $0\leq r_{n+2}<r_{n+1}$.

Soit $D=\textrm{pgcd}(r_{n+1},r_{n+2})$.

$d$ divise $r_{n+1}$ et $r_n$ donc $d$ divise $r_n-r_{n+1}q=r_{n+2}$. Donc $d$ est un diviseur commun à $r_{n+2}$ et $r_{n+1}$, et $d\leq D$.

De même $D$ divise $r_n$ car $r_{n}=r_{n+1}q+r_{n+2}$. C'est donc un diviseur commun à $r_n$ et à $r_{n+1}$. Ainsi $D\leq d$.

On a donc $D=d$ prouvant par récurrence que pour tout entier naturel $n$, $\textrm{pgcd}(r_n,r_{n+1}=\textrm{pgcd}(a,b)$.

Par construction, la suite $(r_n)$ est strictement décroissante jusqu'à ce que $r_n=0$. 

Voici un algorithme Python permettant de calculer le $\textrm{pgcd}$ de deux entiers naturels en utilisant l'algorithme d'Euclide.

Algorithme Python

Voir cette page Google Collab. 

Plus petit commun multiple

Si $a$ et $b$ sont deux nombres entiers naturel, notons 

$\mathcal M(a)$ et $\mathcal M(b)$ les ensembles respectifs de leurs multiples. 

Le nombre $a\times b$ étant à la fois un multiple de $a$ et de $b$ est un élément de $\mathcal M(a)\cap \mathcal M(b)$. 

L'ensemble $\mathcal M(a)\cap \mathcal M(b)$ étant un sous-ensemble non-vide de $\mathbb N$ possède un plus petit élément, un minimum. 

Cet élément s'appelle le plus petit commun multiple à $a$ et à $b$. 

On le note $\textrm{ppcm}(a,b)$.

Propriété. 

Si $a,b$ sont deux entiers naturels, alors

$$ab=\textrm{ppcm}(a,b)\times \textrm{pgcd}(a,b)$$

Démonstration. 

Comme $\textrm{pgcd}(a,b)$ divise $a$ et $b$, il existe un entier naturel $k$ tel que $a=k\times\textrm{pgcd}(a,b)$ et un entier naturel $h$ tel que $b=h\times\textrm{pgcd}(a,b)$.

$h$ et $k$ sont premiers entre eux car s'il avaient un diviseur commun $d$ strictement supérieur à $1$, alors $d\times \textrm{pgcd}(a,b)$ serait un diviseur commun à $a$ et à $b$ tel que $d\times \textrm{pgcd}(a,b)> \textrm{pgcd}(a,b)$, contredisant la maximalité de $\textrm{pgcd}(a,b)$ comme diviseur commun à $a$ et à $b$.

Ainsi $$ab=\left[kh\times\textrm{pgcd}(a,b)\right]\times \textrm{pgcd}(a,b)$$

On note $m=kh\times\textrm{pgcd}(a,b)$.

Comme $m=ha$ et $m=kb$, $m$ est donc un multiple commun à $a$ et à $b$.

Soit $M$ un multiple commun à $a$ et à $b$. On a $M=ta=sb$ pour des entiers naturels $s$ et $t$. 

Supposons que $M<m$.

Ainsi $M=t\times k\times\textrm{pgcd}(a,b)$ (et $M=s\times h\times\textrm{pgcd}(a,b)$). 

$t\times k\times\textrm{pgcd}(a,b)=M<m=k\times\textrm{pgcd}(a,b)$ implique $t<1$ d'où $t=0$, puis $M=0$. On peut en déduire que $m$ est le plus multiple à $a$ et à $b$ non nul. 

Autrement dit $m=\textrm{ppcm}(a,b)$.

Exemple. 

Calculer la somme des fractions

$$\frac{7}{63}+\frac{5}{42}$$

Pour que ces deux fractions s'écrivent avec un même dénominateur, on cherche un dénominateur commun. En prenant le plus petit commun multiple, on pourra optimiser les calculs à faire car les nombres en jeu seront les plus petits possible.

$\mathrm{pgcd}(42,63)=7\times \mathrm{pgcd}(6,9)=21 \times \mathrm{pgcd}(2,3)=21$

$63=21\times 3$ et $42=21\times 2$. Ainsi, $\mathrm{ppcm}(63,21)=\frac{21\times 3\times 21\times 2}{21}=21\times 3\times 2=63\times 2=42\times 3=126$

On a $\frac{7}{63}=\frac{2\times 7}{2\times 63}=\frac{14}{126}$ et

$\frac{5}{42}=\frac{5\times 3}{42\times 3}=\frac{15}{126}$.

On en déduit que

$$\frac{7}{63}+\frac{5}{42}=\frac{14}{126}+\frac{15}{126}=\frac{29}{126}$$

Et ensuite

Dans un article suivant, je présenterai un algorithme améliorant l'algorithme d'Euclide : l'algorithme d'Euclide amélioré.