Mathématiques et algorithmique

1. Commençons par exécuter l'algorithme d'Euclide, tout en isolant les restes :

   \begin{equation*} \begin{array}{rclcrclr} 772&=&44\cdot 17+24&\quad\Rightarrow\quad&24&=&772-44\cdot 17&(\text{E}_1)\\ 44&=&24\cdot 1+20&\quad\Rightarrow\quad&20&=&44-24\cdot 1&(\text{E}_2)\\ 24&=&20\cdot 1+4&\quad\Rightarrow\quad&4&=&24-20\cdot 1&(\text{E}_3)\\ 20&=&4\cdot 5+0&\text{Stop.}&&&& \end{array} \end{equation*}

   On en déduit d'abord que

   \begin{equation*} \text{PGCD}(772;44)=4. \end{equation*}

   Puis on remonte :

   \begin{equation*} \begin{array}{rclr} 4&=&24-20\cdot 1&(\text{E}_3)\\ &=&24-(44-24\cdot 1)\cdot 1&\text{grâce à }(\text{E}_2)\\ &=&24-44+24&\\ &=&24\cdot 2-44&\\ &=&(772-44\cdot 17)\cdot 2-44&\text{grâce à }(\text{E}_1)\\ &=&772\cdot 2-44\cdot 34-44&\\ &=&772\cdot 2-44\cdot 35.& \end{array} \end{equation*}

   On obtient donc la combinaison linéaire

   \begin{equation*} 4=772\cdot 2+44\cdot (-35) \end{equation*}

   c'est-à-dire

   \begin{equation*} \text{PGCD}(772;44)=772u+44v\qquad\text{avec }u=2\;\text{et}\;v=-35. \end{equation*}

2. Commençons par exécuter l'algorithme d'Euclide, tout en isolant les restes :

   \begin{equation*} \begin{array}{rclcrclr} 1975&=&225\cdot 8+175&\quad\Rightarrow\quad&175&=&1975-225\cdot 8&(\text{E}_1)\\ 225&=&175\cdot 1+50&\quad\Rightarrow\quad&50&=&225-175\cdot 1&(\text{E}_2)\\ 175&=&50\cdot 3+25&\quad\Rightarrow\quad&25&=&175-50\cdot 3&(\text{E}_3)\\ 50&=&25\cdot 2+0&\text{Stop.}&&&& \end{array} \end{equation*}

   On en déduit d'abord que

   \begin{equation*} \text{PGCD}(1975;225)=25. \end{equation*}

   Puis on remonte :

   \begin{equation*} \begin{array}{rclr} 25&=&175-50\cdot 3&(\text{E}_3)\\ &=&175-(225-175\cdot 1)\cdot 3&\text{grâce à }(\text{E}_2)\\ &=&175-225\cdot 3+175\cdot 3&\\ &=&175\cdot 4-225\cdot 3&\\ &=&(1975-225\cdot 8)\cdot 4-225\cdot 3&\text{grâce à }(\text{E}_1)\\ &=&1975\cdot 4-225\cdot 32-225\cdot 3&\\ &=&1975\cdot 4-225\cdot 35.& \end{array} \end{equation*}

   On obtient donc la combinaison linéaire

   \begin{equation*} 25=1975\cdot 4+225\cdot (-35) \end{equation*}

   c'est-à-dire

   \begin{equation*} \text{PGCD}(1975;225)=1975u+225v\qquad\text{avec }u=4\;\text{et}\;v=-35. \end{equation*}

3. Commençons par exécuter l'algorithme d'Euclide, tout en isolant les restes :

   \begin{equation*} \begin{array}{rclcrclr} 1981&=&222\cdot 8+205&\quad\Rightarrow\quad&205&=&1981-222\cdot 8&(\text{E}_1)\\ 222&=&205\cdot 1+17&\quad\Rightarrow\quad&17&=&222-205\cdot 1&(\text{E}_2)\\ 205&=&17\cdot 12+1&\quad\Rightarrow\quad&1&=&205-17\cdot 12&(\text{E}_3)\\ 17&=&1\cdot 17+0&\text{Stop.}&&&& \end{array} \end{equation*}

   On en déduit d'abord que

   \begin{equation*} \text{PGCD}(1975;225)=25. \end{equation*}

   Puis on remonte :

   \begin{equation*} \begin{array}{rclr} 1&=&205-17\cdot 12&(\text{E}_3)\\ &=&205-(222-205\cdot 1)\cdot 12&\text{grâce à }(\text{E}_2)\\ &=&205-222\cdot 12+205\cdot 12&\\ &=&205\cdot 13-222\cdot 12&\\ &=&(1981-222\cdot 8)\cdot 13-222\cdot 12&\text{grâce à }(\text{E}_1)\\ &=&1981\cdot 13-222\cdot 104-222\cdot 12&\\ &=&1981\cdot 13-222\cdot 116.& \end{array} \end{equation*}

   On obtient donc la combinaison linéaire

   \begin{equation*} 1=1981\cdot 13+222\cdot (-116) \end{equation*}

   c'est-à-dire

   \begin{equation*} \text{PGCD}(1981;222)=1981u+222v\qquad\text{avec }u=13\;\text{et}\;v=-116. \end{equation*}

4. Commençons par exécuter l'algorithme d'Euclide, tout en isolant les restes :

   \begin{equation*} \begin{array}{rclcrclr} 12003&=&999\cdot 12+15&\quad\Rightarrow\quad&15&=&12003-999\cdot 12&(\text{E}_1)\\ 999&=&15\cdot 66+9&\quad\Rightarrow\quad&9&=&999-15\cdot 66&(\text{E}_2)\\ 15&=&9\cdot 1+6&\quad\Rightarrow\quad&6&=&15-9\cdot 1&(\text{E}_3)\\ 9&=&6\cdot 1+3&\quad\Rightarrow\quad&3&=&9-6\cdot 1&(\text{E}_4)\\ 6&=&3\cdot 2+0&\text{Stop.}&&&& \end{array} \end{equation*}

   On en déduit d'abord que

   \begin{equation*} \text{PGCD}(12003;999)=3. \end{equation*}

   Puis on remonte :

   \begin{equation*} \begin{array}{rclr} 3&=&9-6\cdot 1&(\text{E}_4)\\ &=&9-(15-9\cdot 1)\cdot 1&\text{grâce à }(\text{E}_3)\\ &=&9-15+9&\\ &=&9\cdot 2-15&\\ &=&(999-15\cdot 66)\cdot 2-15&\text{grâce à }(\text{E}_2)\\ &=&999\cdot 2-15\cdot 132-15&\\ &=&999\cdot 2-15\cdot 133&\\ &=&999\cdot 2-(12003-999\cdot 12)\cdot 133&\text{grâce à }(\text{E}_1)\\ &=&999\cdot 2-12003\cdot 133+999\cdot 1596&\\ &=&999\cdot 1598-12003\cdot 133.&\\ \end{array} \end{equation*}

   On obtient donc la combinaison linéaire

   \begin{equation*} 3=12003\cdot (-133)+999\cdot 1598 \end{equation*}

   c'est-à-dire

   \begin{equation*} \text{PGCD}(12003;999)=12003u+999v\qquad\text{avec }u=-133\;\text{et}\;v=1598. \end{equation*}

5. Commençons par exécuter l'algorithme d'Euclide, tout en isolant les restes :

   \begin{equation*} \begin{array}{rclcrclr} 30&=&4\cdot 7+2&\quad\Rightarrow\quad&2&=&30-4\cdot 7&(\text{E}_1)\\ 4&=&2\cdot 2+0&\text{Stop.}&&&& \end{array} \end{equation*}

   On en déduit d'abord que

   \begin{equation*} \text{PGCD}(30;4)=2. \end{equation*}

   Il n'y a rien à remonter ici. L'équation \((\text{E}_1)\) donne la combinaison linéaire

   \begin{equation*} 2=30\cdot 1+4\cdot (-7) \end{equation*}

   c'est-à-dire

   \begin{equation*} \text{PGCD}(30;4)=30u+4v\qquad\text{avec }u=1\;\text{et}\;v=-7. \end{equation*}

6. Commençons par exécuter l'algorithme d'Euclide, tout en isolant les restes :

   \begin{equation*} \begin{array}{rclcrclr} 30&=&5\cdot 6+0&\text{Stop.}&&&& \end{array} \end{equation*}

   Dans ce cas particulier (\(5\vert 30\)), on déduit d'abord que

   \begin{equation*} \text{PGCD}(30;5)=5. \end{equation*}

   Il n'y a rien à remonter ici. On a la combinaison linéaire triviale

   \begin{equation*} 5=30\cdot 0+5\cdot 1 \end{equation*}

   c'est-à-dire

   \begin{equation*} \text{PGCD}(30;5)=30u+5v\qquad\text{avec }u=0\;\text{et}\;v=1. \end{equation*}

1. On a

   \begin{equation*} \begin{array}{|c|c|c|c|c|} \hline r&u&v&\text{Division euclidienne}&q\\ \hline 772&1&0&\\ \hline 44&0&1&772=44\cdot 17+24&17\\ \hline 24&1-0\cdot 17&0-1\cdot 17&44=24\cdot 1+20&1\\ &=1&=-17&&\\ \hline 20&0-1\cdot 1&1-(-17)\cdot 1&24=20\cdot 1+4&1\\ &=-1&=18&&\\ \hline 4&1-(-1)\cdot 1&-17-18\cdot 1&20=4\cdot 5+0&\\ &=2&=-35&\text{Stop}&\\ \hline \end{array} \end{equation*}

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

   \begin{equation*} \text{PGCD}(772;44)=4 \end{equation*}

   ainsi que la combinaison linéaire

   \begin{equation*} 4=772\cdot 2+44\cdot (-35). \end{equation*}

2. On a

   \begin{equation*} \begin{array}{|c|c|c|c|c|} \hline r&u&v&\text{Division euclidienne}&q\\ \hline 1975&1&0&\\ \hline 225&0&1&1975=225\cdot 8+175&8\\ \hline 175&1-0\cdot 8&0-1\cdot 8&225=175\cdot 1+50&1\\ &=1&=-8&&\\ \hline 50&0-1\cdot 1&1-(-8)\cdot 1&175=50\cdot 3+25&3\\ &=-1&=9&&\\ \hline 25&1-(-1)\cdot 3&-8-9\cdot 3&50=25\cdot 2+0&\\ &=4&=-35&\text{Stop}&\\ \hline \end{array} \end{equation*}

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

   \begin{equation*} \text{PGCD}(1975;225)=25 \end{equation*}

   ainsi que la combinaison linéaire

   \begin{equation*} 25=1975\cdot 4+225\cdot (-35). \end{equation*}

3. On a

   \begin{equation*} \begin{array}{|c|c|c|c|c|} \hline r&u&v&\text{Division euclidienne}&q\\ \hline 1981&1&0&\\ \hline 222&0&1&1981=222\cdot 8+205&8\\ \hline 205&1-0\cdot 8&0-1\cdot 8&222=205\cdot 1+17&1\\ &=1&=-8&&\\ \hline 17&0-1\cdot 1&1-(-8)\cdot 1&205=17\cdot 12+1&12\\ &=-1&=9&&\\ \hline 1&1-(-1)\cdot 12&-8-9\cdot 12&17=1\cdot 17+0&\\ &=13&=-116&\text{Stop}&\\ \hline \end{array} \end{equation*}

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

   \begin{equation*} \text{PGCD}(1981;222)=1 \end{equation*}

   ainsi que la combinaison linéaire

   \begin{equation*} 1=1981\cdot 13+222\cdot (-116). \end{equation*}

4. On a

   \begin{equation*} \begin{array}{|c|c|c|c|c|} \hline r&u&v&\text{Division euclidienne}&q\\ \hline 12003&1&0&\\ \hline 999&0&1&12003=999\cdot 12+15&12\\ \hline 15&1-0\cdot 12&0-1\cdot 12&999=15\cdot 66+9&66\\ &=1&=-12&&\\ \hline 9&0-1\cdot 66&1-(-12)\cdot 66&15=9\cdot 1+6&1\\ &=-66&=793&&\\ \hline 6&1-(-66)\cdot 1&-12-793\cdot 1&9=6\cdot 1+3&1\\ &=67&=-805&&\\ \hline 3&-66-67\cdot 1&793-(-805)\cdot 1&6=3\cdot 2+0&\\ &=-133&=1598&\text{Stop}&\\ \hline \end{array} \end{equation*}

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

   \begin{equation*} \text{PGCD}(12003;999)=3 \end{equation*}

   ainsi que la combinaison linéaire

   \begin{equation*} 3=12003\cdot (-133)+999\cdot 1598. \end{equation*}

5. On a

   \begin{equation*} \begin{array}{|c|c|c|c|c|} \hline r&u&v&\text{Division euclidienne}&q\\ \hline 30&1&0&\\ \hline 4&0&1&30=4\cdot 7+2&7\\ \hline 2&1-0\cdot 7&0-1\cdot 7&4=2\cdot 2+0&\\ &=1&=-7&\text{Stop}&\\ \hline \end{array} \end{equation*}

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

   \begin{equation*} \text{PGCD}(30;4)=2 \end{equation*}

   ainsi que la combinaison linéaire

   \begin{equation*} 2=30\cdot 1+4\cdot (-7). \end{equation*}

6. On a

   \begin{equation*} \begin{array}{|c|c|c|c|c|} \hline r&u&v&\text{Division euclidienne}&q\\ \hline 30&1&0&\\ \hline 5&0&1&30=5\cdot 6+0&\\ &&&\text{Stop}&\\ \hline \end{array} \end{equation*}

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

   \begin{equation*} \text{PGCD}(30;5)=5 \end{equation*}

   ainsi que la combinaison linéaire

   \begin{equation*} 5=30\cdot 0+5\cdot 1. \end{equation*}

Par hypothèses, on a

donc

1. L'algorithme fourni donne

   \begin{equation*} \text{PGCD}(377;233)=1\quad\text{et}\quad 1=377\cdot 89+233\cdot (-144). \end{equation*}

   Notons \((u_0;v_0)=(89;-144)\) cette solution particulière de l'équation

   \begin{equation} au+bv=\text{PGCD}(a;b)\quad\Leftrightarrow\quad 377\cdot u+233\cdot v=1.\label{eqbezout1}\tag{12.3.3} \end{equation}

   Si on pose, par exemple,

   \begin{equation*} \left\{ \begin{array}{rcccccccccc} u&=&u_0&+&b&=&89&+&233&=&322\\ v&=&v_0&-&a&=&-144&-&377&=&-521 \end{array}\right. \end{equation*}

   on obtient une autre solution \((u;v)=(322;-521)\) de l'équation (12.3.3).

   Et si on pose, par exemple,

   \begin{equation*} \left\{ \begin{array}{rcccccccccc} u&=&u_0&+&2b&=&89&+&2\cdot 233&=&555\\ v&=&v_0&-&2a&=&-144&-&2\cdot 377&=&-898 \end{array}\right. \end{equation*}

   on obtient une autre solution \((u;v)=(555;-898)\) de l'équation (12.3.3).

2. L'algorithme fourni donne

   \begin{equation*} \text{PGCD}(377;234)=13\quad\text{et}\quad 13=377\cdot 5+234\cdot (-8). \end{equation*}

   Notons \((u_0;v_0)=(13;-8)\) cette solution particulière de l'équation

   \begin{equation} au+bv=\text{PGCD}(a;b)\quad\Leftrightarrow\quad 377\cdot u+234\cdot v=13.\label{eqbezout2}\tag{12.3.4} \end{equation}

   Si on pose, par exemple,

   \begin{equation*} \left\{ \begin{array}{rcccccccccc} u&=&u_0&-&b&=&13&-&234&=&-221\\ v&=&v_0&+&a&=&-8&+&377&=&369 \end{array}\right. \end{equation*}

   on obtient une autre solution \((u;v)=(-221;369)\) de l'équation (12.3.4).

   Et si on pose, par exemple,

   \begin{equation*} \left\{ \begin{array}{rcccccccccc} u&=&u_0&+&5b&=&13&+&5\cdot 234&=&1183\\ v&=&v_0&-&5a&=&-8&-&5\cdot 377&=&-1893 \end{array}\right. \end{equation*}

   on obtient une autre solution \((u;v)=(1183;-1893)\) de l'équation (12.3.4).

3. L'algorithme fourni donne

   \begin{equation*} \text{PGCD}(356002;18954)=2\quad\text{et}\quad 2=356002\cdot (-694)+18954\cdot 13035. \end{equation*}

   Notons \((u_0;v_0)=(-694;13035)\) cette solution particulière de l'équation

   \begin{equation} au+bv=\text{PGCD}(a;b)\quad\Leftrightarrow\quad 356002\cdot u+18954\cdot v=2.\label{eqbezout3}\tag{12.3.5} \end{equation}

   Si on pose, par exemple,

   \begin{equation*} \left\{ \begin{array}{rccccc} u&=&u_0&+&7b&=&131984\\ v&=&v_0&-&7a&=&-2478979 \end{array}\right. \end{equation*}

   on obtient une autre solution \((u;v)=(131\,984;-2\,278\,979)\) de l'équation (12.3.5).

   Et si on pose, par exemple,

   \begin{equation*} \left\{ \begin{array}{rccccc} u&=&u_0&-&3b&=&-57556\\ v&=&v_0&+&3a&=&1081041 \end{array}\right. \end{equation*}

   on obtient une autre solution \((u;v)=(-57\,556;1\,081\,041)\) de l'équation (12.3.5).

Supposons que \(a\vert bc\) et que \(\text{PGCD}(a;b)=1\text{.}\)

Comme \(a\vert bc\text{,}\) il existe \(d\in\mathbb{Z}\) tel que

Et comme \(\text{PGCD}(a;b)=1\text{,}\) il existe \((u;v)\in\mathbb{Z}^2\) tel que

On a donc

avec \(e=uc+dv\in\mathbb{Z}\text{,}\) d'où \(a\vert c\text{.}\)

Rappel : Comme \(p\) est premier, ses seuls diviseurs positifs sont \(1\) et \(p\text{.}\)

Supposons que \(p\vert bc\text{.}\)

• Si \(p\) divise \(b\text{,}\) on a fini.

• Si \(p\) ne divise pas \(b\text{,}\) alors le plus grand diviseur commun à \(p\) et à \(b\) est forcément \(1\text{.}\) On a donc

  \begin{equation*} p\vert bc\quad\text{et}\quad\text{PGCD}(p;b)=1 \end{equation*}

  d'où

  \begin{equation*} p\vert c \end{equation*}

  par le lemme de Gauss 12.3.5.

1. Supposons que \(a\) et \(b\) sont premiers entre eux, et qu'ils divisent \(x\) tous les deux. Alors, d'une part, il existe \(k\in\mathbb{Z}\) tel que

   \begin{equation*} x=ka. \end{equation*}

   D'autre part, on a donc

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

   Par le lemme de Gauss 12.3.5, on en déduit que \(b\) divise \(k\text{,}\) de sorte qu'il existe \(m\in\mathbb{Z}\) tel que

   \begin{equation*} k=mb. \end{equation*}

   Finalement, on obtient

   \begin{equation*} x=ka=(mb)\cdot a=m\cdot(ab) \end{equation*}

   ce qui montre que \(ab\) divise \(x\text{.}\)

2. Ce résultat découle du précédent par récurrence sur \(n\text{.}\)

1. Par définition des nombres rationnels, il existe \((a;b)\in\mathbb{Z}\times\mathbb{N}^*\) tel que

   \begin{equation*} r=\frac{a}{b}. \end{equation*}

   Si \(\text{PGCD}(a;b)=1\text{,}\) on a fini.

   Sinon, notons \(d:=\text{PGCD}(a;b)\text{.}\) Comme \(d\) divise \(a\) et \(b\text{,}\) il existe deux entiers relatifs \(a_0, b_0\) tels que

   \begin{equation*} a=da_0\quad\text{et}\quad b=db_0. \end{equation*}

   On a alors

   \begin{equation*} r=\frac{a}{b}=\frac{da_0}{db_0}=\frac{a_0}{b_0}, \end{equation*}

   et il ne reste plus qu'à montrer que \(\text{PGCD}(a_0;b_0)=1\text{.}\)

   Par le théorème de Bachet-Bézout 12.1.1, il existe \((u;v)\in\mathbb{Z}^2\) tel que \(au+bv=d\text{,}\) d'où

   \begin{equation*} da_0u+db_0v=d. \end{equation*}

   En divisant par \(d\text{,}\) on obtient

   \begin{equation*} a_0u+b_0v=1, \end{equation*}

   d'où \(\text{PGCD}(a_0;b_0)=1\) par le théorème de Bézout 12.1.9.

2. Supposons qu'il existe \((a_1;a_2)\) et \((b_1;b_2)\) tels que

   \begin{equation*} r=\frac{a_1}{b_1}=\frac{a_2}{b_2}\quad\text{avec}\quad(a_i;b_i)\in\mathbb{Z}\times\mathbb{N}^*\;\text{ et }\;\text{PGCD}(a_i;b_i)=1. \end{equation*}

   Nous devons montrer que \((a_1;a_2)=(b_1;b_2)\text{.}\)

   Commençons par noter que

   \begin{equation*} a_1b_2=b_1a_2. \end{equation*}

   • Alors

     \begin{equation*} b_1\vert b_1a_2=a_1b_2\quad\text{et}\quad\text{PGCD}(a_1;b_1)=1 \end{equation*}

     implique que

     \begin{equation*} b_1\vert b_2 \end{equation*}

     par le lemme de Gauss 12.3.5.

     Par un raisonnement symétrique, on a aussi

     \begin{equation*} b_2\vert b_1. \end{equation*}

   • Comme \(b_1\) et \(b_2\) sont tous deux positifs, on déduit de ce qui précède qu'il existe deux entiers positifs \(c, d\) tels que

     \begin{equation*} b_1=cb_2\quad\text{et}\quad b_2=db_1. \end{equation*}

     On a alors

     \begin{equation*} b_1=cdb_1, \end{equation*}

     si bien qu'une division par \(b_1\) entraîne

     \begin{equation*} cd=1. \end{equation*}

     Comme le seul diviseur positif de \(1\) est \(1\) lui-même, il en découle que

     \begin{equation*} c=d=1, \end{equation*}

     d'où \(b_1=b_2\text{.}\)

   • Finalement, revenant à l'équation \(a_1b_2=a_2b_1\text{,}\) on a aussi \(a_1=a_2\text{,}\) ce qui complète la démonstration.