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.
Aucun commentaire:
Enregistrer un commentaire