PGCD (3). Algorithme d'Euclide étendu (sous forme d'activité)

Cet article présente l'algorithme d'Euclide étendu. Il est rédigé sous forme d'activité pouvant être présenté comme un prolongement du cours de l'option maths expertes de terminales, il peut aussi être utilisé de manière indépendante.

Prérequis : 

• Division euclidienne 
• PGCD (2). Algortihme d'Euclide

L'algorithme que nous allons présenter ci-dessous permet de calculer le PGCD $d$ de deux entiers $a$ et $b$, comme l'algorithme d'Euclide. Il permet de plus d'exhiber deux entiers $u$ et $v$ tels que 

$$d=au+bv$$

Algorithme d'Euclide étendu (activité)

Soient $a$ et $b$ deux entiers naturels.

On écrit $a=bq+r$, avec $0\leq r<b$, $q$ et $r$ sont respectivement le quotient et le reste de la division euclidienne de $a$ par $b$.

On pose :

• $r_0=a$, $r_1=b$ 
• $u_0=1$, $u_1=0$
• $v_0=0$, $v_1=1$

Ensuite pour tout $n\geq 0$, tant que $r_{n+1}>0$ on définit 

• $r_{n+2}$ est le reste de la division euclidienne de $r_{n}$ par $r_{n+1}$.
• $q_n$ est le quotient de la division euclidienne de $r_n$ par $r_{n+1}$
• $u_{n+2}=u_{n}-q_nu_{n+1}$
• $v_{n+2}=v_{n}-q_nv_{n+1}$

On rappelle d'après l'algorithme d'Euclide classique que la suite $(r_n)$ est décroissante et qu'il existe un entier $t$ tel que $r_{t+1}=0$, et que $r_t=\mathrm{pgcd}(a,b)$. 

Questions.

1. Démontrer que pour tout $m\leq t$, on a $au_m+bv_m=r_m$.
2. Comment utiliser les suites $(u_n)$ et $(v_n)$ pour obtenirdes entiers $u$ et $v$ tels que $au+bv=\mathrm{pgcd}(a,b)$.
3. Écrire une fonction Python appelée \verb|euclide_etendu| ayant pour arguments deux entiers \verb|a| et \verb|b| permettant de trouver des coefficients de Bézout $u,v$ tels que  $$d=|a|u+|b|v$$

 

Solution

1) Faisons une démonstration par récurrence. On va faire une \textit{récurrence forte}. On pose pour tout $m\leq t$ :   $$\mathcal P_m : \forall n\leq m, au_n+bv_n=r_n$$

(a) Initialisation. 

•     Au rang $0$, on a $au_0+bv_0=a\times 1 + b\times 0 = a$ et $r_0=a$. 
•     Au rang $1$, on a $au_1+bv_1=a\times 0 + b\times 1 =b$ et $r_1=b$.

    On a donc bien $\mathcal P_0$ (et même $\mathcal P_1$).

 (b) Hérédité. 

Supposons pour un certain entier $m\leq t$ : $$\mathcal P_m : \forall n\leq m, au_n+bv_n=r_n$$ et montrons $$\mathcal P_{m+1} : \forall n\leq m+1, au_n+bv_n=r_n$$

Il reste juste à prouver $au_{m+1}+bv_{m+1}=r_{m+1}$.

On a en utilisant l'hypothèse de récurrence $\mathcal P_m$ avec $n=m-1$ et avec $n=m$,

$$\begin{array}{rcl} au_{m+1}+bv_{m+1}&=&a(u_{m-1}-q_{m-1}u_m)+b(v_{m-1}-q_{m-1}v_m) \\ &=&au_{m-1}+bv_{m-1}-q_{m-1}(au_m+bv_m) \\ &=&r_{m-1}-(u_{m+1}-q_{m-1}r_m\\ \end{array}$$

Comme $r_{m-1}=q_{m-1}r_m+r_{m+1}$, on obtient $au_{m+1}+bv_{m+1}=r_{m-1}-q_{m-1}r_m=r_{m+1}$.

L'hérédité est donc prouvée.

    

 (c) Conclusion. 

Par initialisation et hérédité, on a pour tout $m\leq t$ : $$\mathcal P_m : \forall n\leq m, au_n+bv_n=r_n$$  

En particulier $\forall m\leq t, au_m+bv_m=r_m$.

  

2) Comme d'après l'algorithme d'Euclide $r_t=\mathrm{pgcd}(a,b)$, on a $au_t+bv_t=r_t=\mathrm{pgcd}(a,b)$. Ainsi $u_t$ et $v_t$ sont les coefficients de Bézout $u$ et $v$.

    

3) Voir ici. 

Exemple. 

Déterminer le plus grand diviseur $d$ commun de 2051 et 1001, et trouver $u$ et $v$ tels que $2051u+1001v=d$.

On pose :

• $r_0=2051$, $r_1=1001$ 
• $u_0=1$, $u_1=0$
• $v_0=0$, $v_1=1$

On calcule les suites $(r_n)$, $(q_n)$, $(u_n)$ et $(v_n)$ :

(1) $2051=2\times 1001+49$ ainsi 

• $r_2=49$
• $q_0=2$
• $u_2=u_0-q_0 u_1=1-2\times 0=1$
• $v_2=v_0-q_0 v_1 =0-2\times 1=-2$

(2) $1001=20\times 49 +21$

• $r_3=21$
• $q_1=20$
• $u_3=u_1-q_1 u_2=0-20\times 1=-20$
• $v_3=v_1-q_1 v_2 =1-20\times (-2)=41$

(3) $49=2\times 21 +7$

• $r_3=7$
• $q_2=2$
• $u_4=u_2-q_2 u_3=1-2\times (-20)=41$
• $v_4=v_2-q_2 v_3 =-2-2\times 41=-84$

(4) $21=3\times 7 +0$

$$2051\times 41+1001\times (-84)= 7$$

Théorème de Bézout

Nous venons, grâce à l'algorithme d'Euclide étendu de montrer les deux théorèmes suivants.

Théorème (Identité de Bézout).

Soient $a$ et $b$ deux entiers relatifs. On note $d=\textrm{pgcd}(a,b)$. 

Il existe deux entiers $u$ et $v$ tels que $$au+bv=d$$

En conséquence, nous avons le théorème suivant.

On dit que deux entiers relatifs sont premiers entre eux si leur plus grand diviseur commun est 1. 

Théorème (Bézout).

Deux entiers relatifs $a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=1$. 

 

Preuve.

Supposons que $a$ et $b$ sont premiers, alors, d'après l'identité de Bézout, il existe $u$ et $v$ tels que $au+bv=1$. Cela revient à dire que $a$ et $b$ n'ont pas d'autre diviseur commun positif que $1$.

Réciproquement, supposons que $au+bv=1$. Si $d$ est un diviseur commun de $a$ et de $b$, on a 

$a=da'$ et $b=db'$. On a donc $da'+db'=1$ d'où $d(a'+b')=1$. Si $d$ est positif, $d\leq 1$ car $d$ divise $1$, et donc $d=1$. On en déduit que $a$ et $b$ sont premiers entre eux.

Conclusion et suite

Le théorème de Bézout, nous assure l'existence d'une solution particulière à l'équation 

$ax+by=d$, où $d=\mathrm{pgcd}(a,b)$ appelée équation diophantienne.

Nous verrons dans un autre article une méthode pour résoudre ce type d'équation. 

Nous verrons aussi le théorème de Gauss, en conséquence du théorème de Bézout. Il nous permettra par la suite de s'intéresser à la décomposition d'un entier naturel en facteur premiers.