M&A Présentation

Section 12.1 Présentation

Théorème 12.1.1. Bachet-Bézout.

Soit \(a, b\in\mathbb{Z}^*\text{.}\)

Il existe \(u, v\in\mathbb{Z}\) tels que

\begin{equation*} \text{PGCD}(a;b)=au+bv. \end{equation*}

Terminologie : On dit que \(\text{PGCD}(a;b)\) peut s'exprimer comme combinaison linéaire de \(a\) et de \(b\text{,}\) et on appelle \((u;v)\) un couple de coefficients de cette combinaison linéaire.

Démonstration.

Une preuve classique, mais non constructive, consiste à montrer que \(\text{PGCD}(a;b)\) coïncide avec la plus petite combinaison linéaire positive de \(a\) et de \(b\text{.}\)

Nous allons expliquer comment construire un couple de coefficients \((u;v)\) qui fonctionne.

Principe 12.1.2.

Pour exprimer \(\text{PGCD}(a;b)\) comme combinaison linéaire de \(a\) et de \(b\text{,}\) il suffit de remonter les étapes de l'algorithme d'Euclide menant au calcul de \(\text{PGCD}(a;b)\text{.}\)

Exemple 12.1.3.

Reprenons l'exemple 11.1.31 dans lequel on calculait \(\text{PGCD}(2589;234)\) à l'aide de l'algorithme d'Euclide.

Commençons par réécrire toutes ces divisions euclidiennes en isolant les restes :

\begin{equation*} \begin{array}{rccccr} 15&=&2589&-&234\cdot 11&(\text{E}_1)\\ 9&=&234&-&15\cdot 15&(\text{E}_2)\\ 6&=&15&-&9\cdot 1&(\text{E}_3)\\ 3&=&9&-&6\cdot 1&(\text{E}_4) \end{array} \end{equation*}

Partons maintenant de l'équation \((\text{E}_4)\text{.}\)

Remplaçons d'abord \(6\) par \(15-9\cdot 1\) grâce à \((\text{E}_3)\) :

\begin{align*} 3&=9-6\cdot 1\\ &=9-(15-9\cdot 1)\cdot 1\\ &=9-15\cdot 1+9\cdot 1\\ &=9\cdot 2-15\cdot 1. \end{align*}

Remplaçons ensuite \(9\) par \(234-15\cdot 15\) grâce à \((\text{E}_2)\) :

\begin{align*} 3&=9\cdot 2-15\cdot 1\\ &=(234-15\cdot 15)\cdot 2-15\cdot 1\\ &=234\cdot 2-15\cdot 30-15\cdot 1\\ &=234\cdot 2-15\cdot 31. \end{align*}

Remplaçons enfin \(15\) par \(2589-234\cdot 11\) grâce à \((\text{E}_1)\) :

\begin{align*} 3&=234\cdot 2-15\cdot 31\\ &=234\cdot 2-(2589-234\cdot 11)\cdot 31\\ &=234\cdot 2-2589\cdot 31+234\cdot 341\\ &=234\cdot 343-2589\cdot 31. \end{align*}

On obtient donc la combinaison linéaire

\begin{equation*} 3=2589\cdot (-31)+234\cdot 343 \end{equation*}

c'est-à-dire

\begin{equation*} \text{PGCD}(2589;234)=2589u+234v\qquad\text{avec }u=-31\;\text{et}\;v=343. \end{equation*}

Même si elle s'exécute bien à la main, la séquence des calculs effectués dans l'exemple précédent n'est pas évidente à décrire de manière algorithmique. Nous allons donc nous y prendre autrement.

Exemple 12.1.4.

Reprenons l'exemple 12.1.3 et présentons nos calculs de façon à faire émerger une démarche algorithmique.

La première étape consistait à effectuer la division euclidienne de \(2589\) par \(234\text{,}\) soit

\begin{equation*} 2589=234\cdot 11+15, \end{equation*}

puis à isoler le reste, soit

\begin{equation*} 15=2589-234\cdot 11, \end{equation*}

qui donne la combinaison linéaire de \(2589\) et \(234\) suivante :

\begin{equation} \underbrace{15}_{r_2}=2589\cdot\underbrace{1}_{u_2}+234\cdot\underbrace{(-11)}_{v_2}.\label{deuxiemeCL}\tag{12.1.1} \end{equation}

Quant à la dernière étape, il s'agissait de la combinaison linéaire

\begin{equation} \underbrace{3}_{r_5}=2589\cdot\underbrace{(-31)}_{u_5}+234\cdot\underbrace{343}_{v_5}.\label{derniereCL}\tag{12.1.2} \end{equation}

Pour passer de (12.1.1) à (12.1.2), nous allons faire des combinaisons linéaires de combinaisons linéaires.

Pour pouvoir commencer, on écrit la combinaison linéaire triviale

\begin{equation} \underbrace{234}_{r_1}=2589\cdot\underbrace{0}_{u_1}+234\cdot\underbrace{1}_{v_1}.\label{premiereCL}\tag{12.1.3} \end{equation}

On effectue ensuite la division euclidienne de \(r_1=234\) par \(r_2=15\text{,}\) soit

\begin{equation*} \underbrace{234}_{r_1}=\underbrace{15}_{r_2}\cdot\underbrace{15}_{q_2}+\underbrace{9}_{r_3}, \end{equation*}

dont le quotient

\begin{equation*} q_2=r_1\,//\,r_2=234\,//\,15=15 \end{equation*}

va nous permettre de soustraire à (12.1.3) le produit de (12.1.1) et de \(q_2=15\text{,}\) ce qui donne

\begin{equation*} 234-15\cdot 15=2589\cdot(0-1\cdot 15)+234\cdot(1-(-11)\cdot 15), \end{equation*}

soit

\begin{equation} \underbrace{9}_{r_3}=2589\cdot\underbrace{(-15)}_{u_3}+234\cdot\underbrace{166}_{v_3}.\label{troisiemeCL}\tag{12.1.4} \end{equation}

On est donc parvenu à exprimer \(r_3=9\) comme combinaison linéaire de \(2589\) et \(234\text{.}\) Il ne reste plus qu'à itérer ce principe de calcul deux fois, pour se rendre à \(r_5=3=\text{PGCD}(2589;234)\text{.}\)

Principe 12.1.5. Algorithme d'Euclide étendu.

Pour calculer \(\text{PGCD}(a;b)\) tout en l'exprimant comme combinaison linéaire de \(a\) et de \(b\text{,}\) on construit les suites finies

\begin{equation*} \{r_n\},\;\{u_n\},\;\{v_n\},\;\{q_n\} \end{equation*}

définies par les valeurs initiales

\begin{equation*} \left\{ \begin{array}{lll} r_0=a,&u_0=1,&v_0=0,\\ r_1=b,&u_1=0,&v_1=1, \end{array}\right. \end{equation*}

et les relations de récurrence

\begin{equation*} \begin{cases} q_n=r_{n-1}\,//\,r_n,\\ r_{n+1}=r_{n-1}-r_n\cdot q_n,\\ u_{n+1}=u_{n-1}-u_n\cdot q_n,\\ v_{n+1}=v_{n-1}-v_n\cdot q_n \end{cases} \end{equation*}

pour tout \(n\geq 1\) jusqu'à ce qu'on tombe sur \(r_{k+1}=0\text{.}\)

Alors pour \(n=0,\ldots,k+1,\) on a

\begin{equation*} r_n=au_n+bv_n. \end{equation*}

En particulier, le dernier reste non nul \(r_k\) fournit la combinaison linéaire

\begin{equation*} \text{PGCD}(a;b)=au_k+bv_k. \end{equation*}

Terminologie : Cet algorithme est appelé algorithme d'Euclide étendu.

Remarque : Comme la suite \(r_2,\,r_3,\,\ldots,\,r_k,\,0\) est la même que la suite des restes obtenus par l'algorithme d'Euclide, la convergence de l'algorithme d'Euclide étendu découle de la convergence de ce dernier, ainsi que le fait que le dernier reste non nul \(r_k\) soit égal à \(\text{PGCD}(a;b)\text{.}\)

Exemple 12.1.6.

Reprenons l'exemple 12.1.3 et présentons nos calculs conformément au principe 12.1.5.

On a

\begin{equation*} \begin{array}{|c|c|c|c|c|} \hline r&u&v&\text{Division euclidienne}&q\\ \hline 2589&1&0&\\ \hline 234&0&1&2589=234\cdot 11+15&11\\ \hline 15&1-0\cdot 11&0-1\cdot 11&234=15\cdot 15+9&15\\ &=1&=-11&&\\ \hline 9&0-1\cdot 15&1-(-11)\cdot 15&15=9\cdot 1+6&1\\ &=-15&=166&&\\ \hline 6&1-(-15)\cdot 1&-11-166\cdot 1&9=6\cdot 1+3&1\\ &=16&=-177&&\\ \hline 3&-15-16\cdot 1&166-(-177)\cdot 1&6=3\cdot 2+0&\\ &=-31&=343&\text{Stop}&\\ \hline \end{array} \end{equation*}

On déduit de la dernière ligne la valeur du PGCD

\begin{equation*} \text{PGCD}(2589;234)=3 \end{equation*}

ainsi que la combinaison linéaire

\begin{equation*} 3=2589\cdot(-31)+234\cdot 343. \end{equation*}

Remarque 12.1.7.

L'algorithme d'Euclide étendu constitue une preuve du théorème de Bachet-Bézout 12.1.1.

Algorithme d'Euclide étendu : Calculer le PGCD de deux entiers par divisions euclidiennes successives, tout en l'exprimant comme combinaison linéaire de ces deux entiers.

Objectif : Calculer le PGCD de deux entiers relatifs non nuls \(a, b\) et l'exprimer comme combinaison linéaire de \(a\) et \(b\text{,}\) c'est-à-dire trouver un couple d'entiers relatifs \((u;v)\) tels que

\begin{equation} \text{PGCD}(a;b)=au+bv.\label{eqbezoutassemblage}\tag{12.1.5} \end{equation}
Principe : Faire les mêmes divisions euclidiennes successives que pour l'algorithme d'Euclide, tout en gardant la trace des combinaisons linéaires de \(a\) et de \(b\) qu'on peut en déduire à chaque étape. Plus précisément, suivre les instructions énoncées au principe 12.1.5.
Remarque : L'algorithme d'Euclide étendu fournit une solution particulière \((u;v)\in\mathbb{Z}^2\) de l'équation (12.1.5). Mais il en existe en fait une infinité (voir l'exercice 12.3.3).
Voir aussi : Notes de cours de Jérôme.

Remarque 12.1.8.

Le théorème de Bachet-Bézout 12.1.1 se résume ainsi :

\begin{equation*} \text{PGCD}(a;b)=d\quad\Rightarrow\quad \exists(u;v)\in\mathbb{Z}^2,\quad au+bv=d. \end{equation*}

La réciproque est fausse, comme le montre l'exemple suivant :

\begin{equation*} 5\cdot 3+4\cdot(-2)=7\quad\text{et}\quad\text{PGCD}(5;4)=1\neq 7. \end{equation*}

Mais dans le cas particulier où \(d=1\text{,}\) la réciproque est vraie, comme nous allons le montrer avec le théorème qui suit.

Théorème 12.1.9. Bézout.

Soit \(a, b\in\mathbb{Z}^*\text{.}\)

On a

\begin{equation*} \text{PGCD}(a;b)=1\quad\Leftrightarrow\quad\exists (u;v)\in\mathbb{Z}^2,\quad au+bv=1. \end{equation*}

Terminologie : On dit alors que \(a\) et \(b\) sont premiers entre eux.

Démonstration.

L'implication \(\Rightarrow\) découle immédiatement du théorème 12.1.1.

Établissons maintenant la réciproque.

Supposons donc qu'il existe un couple \((u;v)\in\mathbb{Z}^2\) tel que

\begin{equation*} au+bv=1. \end{equation*}

Soit \(d\) un diviseur commun à \(a\) et à \(b\text{,}\) de sorte qu'il existe deux entiers \(a_0, b_0\) tels que

\begin{equation*} a=d\cdot a_0\quad\text{et}\quad b=d\cdot b_0. \end{equation*}

Alors

\begin{align*} a\cdot u+b\cdot v=1&\quad\Rightarrow\quad d\cdot a_0\cdot u+d\cdot b_0\cdot v=1\\ &\quad\Rightarrow\quad d\cdot(a_0u+b_0v)=1\\ &\quad\Rightarrow\quad d\vert 1\\ &\quad\Rightarrow\quad d=\pm 1 \end{align*}

où la dernière implication repose sur le fait que les seuls diviseurs de \(1\) sont \(-1\) et \(1\text{.}\)

Nous venons donc de montrer que les seuls diviseurs communs à \(a\) et à \(b\) sont \(-1\) et \(1\text{.}\) Par la définition 11.1.22 du PGCD, on a donc

\begin{equation*} \text{PGCD}(a;b)=1. \end{equation*}