PGCD (1) . Algorithme des soustractions successives.

Dans cet articles, nous définissons le PGCD de deux nombres entiers, puis nous donons un premier algorithme permettant de le calculer à l'aide de soustrations.

On note pour tout nombre entier naturel $a$ :

$$E_a=\left\{n\in\mathbb N, n\leq a \right\}$$

(On pourra consulter [Ensembles finis...])

et 

$$\mathcal D_a=\left\{n\in\mathbb N, n\ \textrm{divise} \ a \right\}$$

(On pourra consulter [Soustraction et division euclidienne], §Divisibilité)

Propriétés préliminaires

Si $a$ est un nombre relatif alors sa valeur absolue $|a|$ est l'entier naturel défini par 

$$|a|=\left\{ \begin{array}{rcl}  a   &\textrm{ si }& a\geq 0  \\ -a &\textrm{ si}& a\leq 0 \end{array}\right.$$

Puisque $a=dq$ si et seulement si $a=(-d)(-q)$, $d$ est un diviseur de 

$a$ si et seulement si $-d$ est un diviseur de $a$. 

Comme $a=dq$ si et seulement si $-a=d(-q)$, $d$ divise $a$ si et seulement si $d$ divise $-a$. On en déduit que $a$, $-a$ et donc aussi $|a|$ ont les mêmes diviseurs. 

En particulier $a$ et $|a|$ ont les mêmes diviseurs positifs. 

Propriété 1.

Tout nombre entier relatif $a$ possède un nombre fini de diviseurs positifs.

Remarque.

Ce nombre est non nul car $1$ est un diviseur de tout entier relatif.

Preuve.

D'après ce qui précède, on peut supposer que $a$ est positif (quitte à considérer $|a|$ à sa place).

Puisque $a=dq\leq 1d=d$, l'ensemble des diviseurs $d$ de $a$ est majoré par $a$ : $\mathcal D(a)\subset E_a$.

On en déduit que l'ensemble des diviseurs de $a$ admet au plus $a+1$ diviseurs.

Une autre propriété sera utile dans la suite.

Propriété 2.

Si $a,b$ sont divisible par $d$, alors $d$ divise toute combinaison de la forme $ka+tb$, avec $k,t$ entiers relatifs.

Preuve. 

Si $a=dq$ et $b=dp$, on alors $ka+tb=d(kq+kp)$.

 $\textrm{pgcd}$ : définition et calcul

Si $a$ et $b$ sont des nombres entiers relatifs, ils ont au poins un diviseur en commun : $1$.

On note respectivement $\mathcal{D}(a)$ et $\mathcal{D}(b)$ les ensembles des diviseurs de $a$ et respectivement de $b$.

L'intersection $\mathcal{D}(a)\cap\mathcal D(b)$ possède au moins le nombre $1$ comme élément. De plus comme elle est incluse dans l'ensemble fini $\mathcal{D}(a)$, cette intersection contient un maximum.

Ce maximum est appelé le plus grand commun diviseur de $a$ et de $b$. C'est un entier supérieur ou égal à $1$. On le note $\textrm{pgcd}(a,b)$.

Propriété 3. 

Si $a,b$ sont des entiers relatifs, alors $\textrm{pgcd}(a,b)=\textrm{pgcd}(|a|,|b|)$.

Preuve. 

D'après la propriété 1, $a$ et $|a|$ ont les mêmes diviseurs et $b$ et $|b|$ ont les mêmes diviseurs.

Remarques. 

- Pour tout entier $a$ relatif, $\textrm{pgcd}(a,0)=|a|$. En effet, tout nombre divise $0$ car pour tout entier $d$, $0=0d$. Comme le plus grand diviseur de $a$ est $|a|$, on en déduit que c'est $\textrm{pgcd}(a,0)$.

- Pour tout $a\in\mathbb N$, $\textrm{pgcd}(a,a)=a$. 

Ainsi pour calculer le plus grand commun diviseur de deux nombre entiers, il suffit de savoir calculer le plus grand commun diviseur de deux nombres entiers naturels. 

Propriété 4. 

Si $a,b$ sont des entiers relatifs, alors $\textrm{pgcd}(a-b,b)=\textrm{pgcd}(a,b)$.

Démonstration.

D'après la propriété 2, avec $k=1$ et $t=-1$, si $d$ divise $a$ et $b$, alors $d$ divise $a-b$. Tout diviseur commun à $a$ et à $b$ est donc aussi un diviseur commun à $a-b$ et à $b$.

Supposons maintenant que $d$ divise $b$ et $a`=a-b$. Alors d'après la propriété 2, $d$ divise aussi leur somme $a$. Ainsi tout diviseur commun à $a-b$ et à $b$ est aussi un diviseur commun à $a$ et à $a-b$.

On peut en déduire que $\mathcal D(a)\cap \mathcal D(b)=\mathcal D(a-b)\mathcal D(b)$. Donc ces ensemble ont le même maximum : $\textrm{pgcd}(a,b)=\textrm{pgcd}(a-b,b)$.

La propriété 4 nous permet d'avoir un premier algorithme pour calculer le $\textrm{pgcd}$ de deux entiers relatifs.

Propriété 5. (Algorithme des différences successives)

Supposons que $0< b\leq a$.

On définit par récurrence la suite $(a_n)$ et la suite $(b_n)$ : 

$$\left\{\begin{array}{rcl} a_0&= & a\\ b_0   &=& b \\ a_{n+1} & = & \max(a_{n}-b_n,b_n) \\ b_{n+1}&=&\min(a_{n}-b_n,b_n) \end{array} \right.$$

Il existe un rang $t$ tel que pour tout $r\geq t$, $a_r=\textrm{pgcd}(a,b)$.

 

Démonstration. 

1) Par récurrence, on montre que pour tout $n$, $\textrm{pgcd}(a_n,b_n)=\textrm{pgcd}(a,b)$. 

• C'est clair si $n=0$.
• Supposons $\textrm{pgcd}(a_n,b_n)=\textrm{pgcd}(a,b)$ pour un certain $n$.
  Alors $$\textrm{pgcd}(a_{n+1},b_{n+1})=\textrm{pgcd}(a_n-b_n,b_n)=\textrm{pgcd}(a_n,b_n)=\textrm{pgcd}(a,b)$$

2) On a pour tout $n$ : 

• $a_n\geq a_{n+1}$
• $b_n\geq b_{n+1}$
• $a_n\geq b_n$

Le troisième point est clair par définition des deux suites. 

On montre les autres inégalités en même temps par récurrence.

• Si $n=0$, on a $a_0=a$, $b_0=b$ et $a_1=\max(a_{0}-b_0,b_0)=\max(a-b,b)$. Comme $b\leq a$ et $a-b\leq a$, on en déduit que $a_1\leq a=a_0$.

    Aussi $b_1=\min(a_{0}-b_0,b_0)=\min(a-b,b)\leq b=b_0$.

• Supposons pour un certain entier naturel $n$ : 

$a_n\geq a_{n+1}$

$b_n\geq b_{n+1}$

Alors comme $a_{n+2}=\max(a_{n+1}-b_{n+1},b_{n+1})$, et que

$a_{n+1}-b_{n+1}\leq a_{n+1}$ et $b_{n+1}\leq a_{n+1}$ on a 

$a_{n+2}\leq a_{n+1}$. Aussi $b_{n+2}\leq b_{n+1}$ car $b_{n+2}=\min(a_{n+1}-b_{n+1},b_{n+1})$.

Les deux suites sont donc décroissantes dans $\mathbb N$. D'après le principe de descente infinie, elles sont donc stationnaires : il existe un rang $N_a$ et un rang $N_b$ tels que pour tout $n\geq N_a$,

$a_n=a_{N_a}$

et pour tout $n\geq N_b$, $b_n=b_{N_b}$.

Soit $t$ le plus petit $N_a$ ainsi défini, et $s$ le plus petit $N_b$ ainsi défini.

Alors $a_r=a_{r+1}=\max(a_{r}-b_r,b_r)$. 

Soit $r\geq t$.

Si $b_r\neq 0$, $a_r-b_r<a_r$, donc $a_{r+1}=b_r=a_r$. Dans ce cas, on a $\textrm{pgcd}(a,b)=\textrm{pgcd}(a_r,b_r)=\textrm{pgcd}(a_r,a_r)=a_r$.

Si $b_r=0$, alors $\textrm{pgcd}(a,b)=\textrm{pgcd}(a_r,0)=a_r$. 

Si $\textrm{pgcd}(a_r,b_r)=a_r$, alors on a $b_r=0$, ou on a $a_r$ divisant $b_r$, d'où $a_r\leq b_r$, mais puisque $b_r\leq a_r$, on a $a_r=b_r$. 

Ensuite, dans ce cas, on a $a_r-b_r=0$ et d'où $a_{r+1}=b_r$ et $b_{r+1}=0$.

La suite $(a_n)$ stationne donc en $\textrm{pgcd}(a,b)$.

On en déduit qu'à partir d'un certain rang tous les termes de la suite $(b_n)$ sont nuls (par décroissance). Par définition de $s$, (si $s\geq 1$), on a $b_{s-1}>0$ et $b_s=0$. 

On a pour $s\geq 1$ (c'est-à-dire $b\neq 0$), $b_s=0$ donc $a_{s-1}-b_{s-1}=0$ par définition de $b_s$ (puisque $b_{s-1}\neq 0$). On a donc $a_{s-1}=b_{s-1}$, et $\textrm{pgcd}(a,b)=\textrm{pgcd}(a_{s-1},b_{s-1})=b_{s-1}=a_{s-1}$. Par ailleurs, $a_s=b_{s-1}=a_{s-1}$ donc $t\leq s$.

Remarquons que si $s\geq 2$, et si $a_{s-2}=a_{s-1}=\max(b_{s-2},a_{s-2}-b_{s-2})$, on a $a_{s-2}=b_{s-2}$ car $b_{s-2}\neq 0$. Dans ce cas $b_{s-1}=a_{s-2}-b_{s-2})=0$. Cela contredirait la minimalité de $s$. 

Donc $a_{s-2}>a_{s-1}$. Ainsi $t\geq s$.

On a donc $t=s$.

On a donc par ce théorème obtenu un algorithme permettant de déterminer le plus grand commun diviseurs de deux nombres sans avoir à déterminer les ensembles de diviseurs de ces deux nombres.

Pour trouver ce plus grand divseur, il suffit de construire les deux suites $(a_n)$ et $(b_n)$ jusqu'à ce que $a_n=b_n$ ou $b_n=0$.

Exemple numérique.

Déterminer le $\textrm{pgcd}$ de $2051$ et $1001$.

Solution. 

• On a $a_0=2051$, $b_0=1001$. 
• $2051-1001=1050$, $a_1=1050$, $b_1=1001$
• $1050-1001=49$, $a_2=1001$, $b_2=49$
• $1001-49=952$, $a_3=952$, $b_3=49$
• $952-49=903$, $a_4=903$, $b_4=49$
• $903-49=854$, $a_5=854$, $b_5=49$
• $854-49=795$, $a_6=795$, $b_6=49$
• $795-49=756$, $a_7=756$, $b_7=49$
• $756-49=707$, $a_8=707$, $b_8=49$
• $707-49=658$, $a_9=658$, $b_9=49$
• $658-49=609$, $a_{10}=609$, $b_{10}=49$
• $609-49=560$, $a_{11}=560$, $b_{11}=49$
• $560-49=511$, $a_{12}=511$, $b_{12}=49$
• $511-49=462$, $a_{13}=462$, $b_{13}=49$
• $462-49=413$, $a_{14}=413$, $b_{14}=49$
• $413-49=364$, $a_{15}=364$, $b_{15}=49$
• $364-49=315$, $a_{16}=315$, $b_{16}=49$
• $315-49=266$, $a_{17}=266$, $b_{17}=49$
• $266-49=217$, $a_{18}=217$, $b_{18}=49$
• $217-49=168$, $a_{19}=168$, $b_{19}=49$
• $168-49=119$, $a_{20}=118$, $b_{20}=49$
• $119-49=70$, $a_{21}=70$, $b_{21}=49$
• $70-49=21$, $a_{22}=49$, $b_{22}=21$
• $49-21=28$, $a_{23}=28$, $b_{23}=21$
• $28-21=14$, $a_{24}=21$, $b_{24}=14$
• $21-14=7$, $a_{25}=14$, $b_{25}=7$
• $14-7=7$, $a_{26}=7$, $b_{26}=7$

L'algorithme s'arrête car $a_{26}=b_{26}=7$, et on a $\textrm{pgcd}(2051,1001)=7$

Algorithme Python

Voici en lien un algorithme Python en récursif.

Et ensuite ?

Dans un prochain article, nous verrons un autre algorithme beaucoup plus efficace en nombre d'opérations. Il permmettra en effet de regrouper plusieurs divisions successives par un même nombre en une division euclidienne. C'est l'algorithme d'Euclide.