\documentstyle[12pt]{article}



\setlength{\oddsidemargin}{0.5cm}
\setlength{\textwidth}{15cm}
\setlength{\textheight}{23cm}
\setlength{\topmargin}{0.5cm}
\setlength{\headheight}{0cm}
\setlength{\headsep}{0cm}

\newtheorem{theorem}{Theorem}

\newcommand{\el}{\par \mbox{} \par \vspace{-0.5\baselineskip}\noindent}
\newcommand{\ko}{\; ,}
\newcommand{\ts}{\textstyle \mbox{\rule{0cm}{0.8\baselineskip}}}

\newcommand{\ra}{\rightarrow}
\newcommand{\N}{\mbox{{\bf N}}}
\newcommand{\Z}{\mbox{{\bf Z}}}
\newcommand{\pgcd}{\mbox{PGCD}\,}
\newcommand{\eps}{\varepsilon}
\renewcommand{\det}{\mbox{d\'et}\,}
%Pictures
\setlength{\unitlength}{0.25cm}
\newcommand{\lblarge}[3]{\put(#1,#2){\makebox(3,2){$ #3 $}}}
\newcommand{\lb}[3]{\put(#1,#2){\makebox(2,2){$ #3 $}}}
\newcommand{\lbt}[3]{\put(#1,#2){\makebox(0,0)[t]{$ #3 $}}}
\newcommand{\lbb}[3]{\put(#1,#2){\makebox(0,0)[b]{$ #3 $}}}
\newcommand{\lbtl}[3]{\put(#1,#2){\makebox(0,0)[tl]{$ #3 $}}}
\newcommand{\lbtr}[3]{\put(#1,#2){\makebox(0,0)[tr]{$ #3 $}}}
\newcommand{\lbbl}[3]{\put(#1,#2){\makebox(0,0)[bl]{$ #3 $}}}
\newcommand{\lbbr}[3]{\put(#1,#2){\makebox(0,0)[br]{$ #3 $}}}
\newcommand{\arrow}[5]{\put(#1,#2){\vector(#3,#4){#5}}}
\newcommand{\lin}[5]{\put(#1,#2){\line(#3,#4){#5}}}
\newcommand{\lbold}[3]{\put(#1,#2){\makebox(1,0.5){$ #3 $}}}
\renewcommand{\dot}[2]{\put(#1,#2){\circle*{0.5}}}



\begin{document}
\begin{center}
Universit\'e Paris 7  \hfill 19 octobre 1994\\
U.F.R. de Math\'ematiques\hfill \mbox{B.~Keller } \\
D.E.U.G. Math\'ematiques : MT 282  \hfill \mbox{ }
\mbox{ }
\end{center}
\begin{center}
{\bf L'algorithme d'Euclide--B\'ezout}
\end{center}

Soient $a,b,c \in\Z$ tels que $(a,b)\neq (0,0)$.
L'algorithme suivant sert \`a calculer le $\pgcd(a,b)$ et la
solution g\'en\'erale $(x,y)\in\Z^2$ de l'\'equation de B\'ezout
\[
a\,x+b\,y= c.
\]
L'algorithme se pr\'esente sous forme d'un tableau. 
Dans une premi\`ere \'etape
on remplit les deux premi\`eres lignes comme indiqu\'ees 
dans le tableau ci-dessous. Le coefficient $q_1$ n'est pas d\'efini;
le coefficient $q_2$ est le quotient de la division euclidienne
de $a$ par $b$. 
Les lignes suivantes se calculent 
chacune en fonction des deux pr\'ec\'edentes comme indiqu\'ee
ci-dessous.


\begin{center}
\begin{tabular}{|c|cccc|l} \cline{1-5}
$k$ & $r_k$ & $q_k$ & $x_k$ & $y_k$ &
  \\ 
\cline{1-5}
$1$     & a          & $*$       & $1$       & $0$ & 
 \\
$2$     & b          & $q_2$     & $0$       & $1$ & 
$a=q_2\,b+ r_3$ est une div. eucl.  \\
$3$     & $r_3$      & \ldots     & \ldots     & \ldots &
 \\
$\vdots$ &         &           &           &      &
 \\
$k-1$   & $r_{k-1}$  & $q_{k-1}$ & $x_{k-1}$ & $y_{k-1}$ &
\\
$k$     & $r_k$      & $q_k$     & $x_k$     & $y_k$    &
$r_{k-1}=q_k\,r_k+r_{k+1}$ est une div. eucl. \\
$k+1$   & $r_{k+1}$  & $q_{k+1}$ & $x_{k+1}$ & $y_{k+1}$ &
$x_{k+1}=x_{k-1}-q_k x_k$, $y_{k+1}=y_{k-1}-q_k y_k$ \\
$\vdots$ &         &           &           &        &
  \\
$N$   & $r_N$      & $q_N$     & $x_N$     & $y_N$  &
  \\
$N+1$ & $r_{N+1}=0$  & $*$ & $x_{N+1}$ & $y_{N+1}$ & 
  \\
\cline{1-5}
\end{tabular}
\end{center}
La premi\`ere colonne contient donc les restes des divisions
euclidiennes successives, la deuxi\`eme colonne les quotients
et les deux derni\`eres colonnes des coefficients $x_k$, $y_k$
tels que $a\,x_k+b\,y_k=r_k$ (voir la d\'emonstration ci-dessous).

Les coefficients de la premi\`ere colonne forment une suite
strictement d\'ecroissante de nombres positifs entiers.
Par d\'efinition, $N$ est le plus petit entier avec $r_{N+1}=0$.
%Notons \`a titre de curiosit\'e que si $b=0$ l'algorithme
%s'arr\^ete \`a $N=1$ et $q_2$ n'est pas d\'efini. 

\el
{\bf Th\'eor\`eme.} 
{\em 
On a  $r_N  =  \pgcd(a,b)$. Si $\pgcd(a,b)$ divise $c$,
la solution g\'en\'erale de l'\'equation
\[
ax+by=c
\]
est donn\'ee par 
\begin{eqnarray*}
x & = & \frac{c}{\pgcd(a,b)}x_N+l x_{N+1} \\
y & = & \frac{c}{\pgcd(a,b)}y_N+l y_{N+1}
\end{eqnarray*}
o\`u $l\in\Z$. Si $\pgcd(a,b)$ ne divise pas $c$, l'\'equation
$ax+by=c$ n'admet pas de solution $(x,y)\in\Z^2$. 
}
\el
\noindent{\bf Exemple.} Nous cherchons le $\pgcd(198,75)$ et
toutes les solutions de l'\'equation $198 x + 75 y = \pgcd( 198,75)$.
Nous obtenons le tableau
\begin{center}
\begin{tabular}{|c|cccc|} \cline{1-5}
$k$ & $r_k$ & $q_k$ & $x_k$ & $y_k$  \\ \hline
$1$     & $198$    & $*$   & $1$  & $0$ \\
$2$     & $75$     & $2$   & $0$  & $1$  \\
$3$     & $48$     & $1$   & $1$  & $-2$ \\
$4$     & $27$     & $1$   & $-1$ & $3$ \\
$5$     & $21$     & $1$   & $2$  & $-5$ \\
$6$     & $6$      & $3$   & $-3$ & $8$ \\
$7$     & $3$      & $2$   & $11$ & $-29$ \\
$8$     & $0$      & $*$   & $-25$ & $66$ \\
\hline
\end{tabular}
\end{center}
Ainsi $\pgcd(198,75)=3$ et la solution g\'en\'erale
de l'\'equation $198 x + 75 y =3$ est donn\'ee par
\begin{eqnarray*}
x & = & 11 - 25 l \\
y & = & -29 + 66 l
\end{eqnarray*}
o\`u $l\in\Z$. 

Notons que $25=75/3$ et $66=198/3$. 
Notons aussi que les derni\`eres deux colonnes 
sont des suites altern\'ees et que les mo\-dules de $x_k$, $y_k$
sont strictement croissants pour $k\geq 3$. En particulier,
nous avons $0\leq x_N< -(-25)$ et $-66< y_N\leq 0$. La solution
$(x_N,y_N)$ est la seule avec ces propri\'et\'es.
Les coefficients $q_k$ apparaissent dans l'identit\'e 
\[
\frac{198}{75}= 2 + 
\frac{1}{1+
\frac{\ts 1}{\ts 1+
\frac{\ts 1}{\ts 1+
\frac{\ts 1}{\ts 3+
\frac{\ts 1}{\ts 2}}}}} \;\; .
\]
Voir les exercices
apr\`es la d\'emonstration.


\el
\noindent
{\bf D\'emonstration.} Notons d'abord que l'algorithme s'arr\^ete.
En effet, $r_{k+1}$ est le reste d'une division euclidienne par
$r_k$. Donc $r_{k+1}$ est compris entre $0$ et $r_k-1$. Les $r_k$ forment
donc une suite strictement d\'ecroissante de nombres positifs
entiers. Une telle suite doit aboutir \`a z\'ero apr\`es
un nombre fini d'\'etapes. 

Montrons  que $r_N=\pgcd(a,b)$. Montrons d'abord que nous avons 
\[
\pgcd(r_{k-1}, r_k)=\pgcd(r_k, r_{k+1}).
\]
En effet, par construction, nous avons une \'equation
\[
r_{k-1} = q_k r_k + r_{k+1}.
\]
Elle montre que l'ensemble des diviseurs communs \`a $r_{k-1}$
et $r_k$ est \'egal \`a l'ensemble des diviseurs communs \`a
$r_k$ et $r_{k+1}$. En particulier, les plus grands \'el\'ements
de ces ensembles sont \'egaux. La formule pour $r_N$ s'ensuit par
r\'ecurrence :
\begin{eqnarray*}
\pgcd(a,b)& = & \pgcd(b,r_3)= \ldots   \\
          & = & \pgcd(r_{N-1},r_N)=\pgcd(r_N, r_{N+1})=\pgcd(r_N,0)= r_N.
\end{eqnarray*}


Pour montrer la deuxi\`eme affirmation, nous introduisons les
matrices
\[
S_k=\left[ 
\begin{array}{cc} x_k & x_{k+1} \\ y_k & y_{k+1} \end{array}
\right] \ko k\geq 1.
\]
Nous avons
\[
S_1=\left[
\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}
\right] 
\mbox{   et   }
S_{k+1}= S_k \left[
\begin{array}{cc} 0 & 1 \\ 1 & -q_{k+1} \end{array}
\right].
\]
Par r\'ecurrence, il s'ensuit que 
\[
[ a\;\;b] S_k = [r_k \;\; r_{k+1}] \quad\mbox{et}\quad
\det S_k=-(-1)^k.
\]
En particulier, nous avons $[a\;\; b] S_N=[r_N\;\; 0]$ et la
matrice 
\[
S_N^{-1}=-(-1)^N \left[ 
\begin{array}{cc} y_{N+1} & -x_{N+1} \\ -y_N & x_N \end{array}
\right]
\]
est {\em \`a coefficients entiers}. Donc si nous posons
\[
\left[ \begin{array}{c} u \\ v \end{array} \right]
=
S_N^{-1} \left[ \begin{array}{c} x \\ y \end{array} \right]\ko
\]
alors $u,v$ sont des {\em entiers}. Nous avons
\[
[a \;\; b] \left[ \begin{array}{c} x \\ y \end{array} \right]=
[a \;\; b] S_N S_N^{-1} \left[ \begin{array}{c} x \\ y 
                                          \end{array} \right]=
[r_N\;\; 0] \left[ 
\begin{array}{c} u \\ v \end{array} \right]
\]
de fa\c{c}on que l'\'equation 
\[
[a \;\; b] \left[ \begin{array}{c} x \\ y \end{array} \right]=c
\quad\mbox{(resp. $ax+by=c$)}
\]
est \'equivalente \`a l'\'equation
\[
[r_N \;\; 0] \left[ \begin{array}{c} u \\ v \end{array} \right]=c
\quad\mbox{(resp. $r_N u + 0\,v=c$)}.
\]
Or il est clair que cette derni\`ere \'equation admet des solutions
si et seulement si $r_N$ divise $c$ et que dans ce cas la solution
g\'en\'erale est
\[
\left[
\begin{array}{c} u \\ v \end{array}
\right] =
\left[ 
\begin{array}{c} c/r_N \\ l \end{array}
\right] \ko
\]
o\`u $l\in\Z$. Donc l'\'equation $ax+by=c$ admet des solutions
si et seulement si $r_N$ divise $c$ et dans ce cas
la solution g\'en\'erale est
\[
\left[ 
\begin{array}{c} x \\ y \end{array}
\right]
= S_N \left[
\begin{array}{c} u \\ v \end{array}
\right]
= \left[
\begin{array}{cc} x_N & x_{N+1} \\ y_N & y_{N+1} \end{array}
\right]
\left[ 
\begin{array}{c} c/r_N \\ l \end{array}
\right]
= \left[
\begin{array}{c}
\frac{c}{r_N} x_N + l x_{N+1} \\
\frac{c}{r_N} y_N + l y_{N+1}
\end{array}
\right]. 
\]
\el
\el
\el
{\bf Exercices.} 1) Trouver toutes les solutions $(x,y)\in\Z^2$ des
\'equations suivantes~: a)~$5x+3y=2$, b) $4x+9y=1$, c) $17x+68y=3$,
d) $20x+30y=0$, e) $1789x+1994y=1$ f) $1994x+666y=2$.
\el
2) Avec les notations de l'algorithme d'Euclide-B\'ezout, montrer
que
\[
x_{N+1}= (-1)^N \frac{c}{\pgcd(a,b)} \mbox{   et   }
y_{N+1}= -(-1)^N \frac{a}{\pgcd(a,b)}.
\]
Indication : On pourra utiliser l'identit\'e
\[
\left[
\begin{array}{cc} a & b \\ -y_N & x_N \end{array}
\right] S_N= 
\left[
\begin{array}{cc} r_N & 0 \\ 0 & -(-1)^N \end{array}
\right].
\]
\el
3) Supposons $a>b>0$. Avec les notations de l'algorithme 
d'Euclide-B\'ezout, montrer que
\[
\frac{a}{b}=q_2+
\frac{\ts r_3}{\ts b}= 
q_2+
\frac{\ts 1}{\ts q_3+
\frac{\ts r_4}{\ts r_3}}
=q_2+
\frac{\ts 1}{\ts q_3+
\frac{\ts 1}{\ts q_4+
\frac{\ts r_5}{\ts r_4}}}= \ldots
\]
\el
4) Nous allons caract\'eriser la solution $(x_N,y_N)$ fournie par
l'algorithme d'Euclide-B\'ezout parmi toutes les solutions 
de l'\'equation de B\'ezout. Supposons, pour simplifier,
que $a>b>0$ et que $\pgcd(a,b)=1$. 

a) Montrer qu'il existe une solution $(x_+,y_+)\in\Z^2$ de $ax+by=1$ 
et une seule
telle que $0\leq x_+<b$. Montrer qu'on a
$-a<y_+\leq 0$. 

b) Montrer qu'il existe une solution $(x_-, y_-)\in\Z^2$ 
de $ax+by=1$ 
et une seule 
telle que $-b<x_-\leq 0$. Montrer qu'on a
$0\leq y_+<a$. 

c) Montrer qu'on a $(x_N,y_N)= (x_+,y_+)$ si $N$ est impair
et $(x_N,y_N)=(x_-,y_-)$ si $N$ est pair. Indication : on pourra
commencer par montrer que les suites $-(-1)^k x_k$ et $(-1)^k y_k$
sont strictement croissantes pour $k\geq 3$. 
\el
5) Nous allons estimer le nombre d'\'etapes de 
l'algorithme d'Euclide-B\'ezout.
Pour un couple d'entiers $(a,b)$ avec $a>b\geq 0$ notons $N(a,b)$
le nombre $N$ apparaissant comme nombre d'\'etapes de l'algorithme
d'Euclide-B\'ezout appliqu\'e \`a $(a,b)$.

a) Montrer que $N(a,b)\leq 1+\log_2 a$.

b) Soit $F_0=0$, $F_1=1$ et $F_n=F_{n-1}+F_{n-2}$ pour tout
$n>1$. Par d\'efinition, le nombre $F_n$ est le {\em $n$-i\`eme 
nombre de Fibonacci}. Montrer que $N(F_n, F_{n-1})=n$, 
que $N(a,b)\leq n$ si $a\leq F_n$ et que l'\'egalit\'e
ne se pr\'esente que pour $a=F_n$ et $b=F_{n-1}$. 
\end{document}










