A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

319 personne(s) sur le site en ce moment

E. Cartan

A lire

Articles

Math/Infos

Récréation
A télécharger

Télécharger

Théorème de Cantor-Bernstein

Théo. Sylow

Théo. Ascoli

Théo. Baire

Loi forte grd nbre

Nains magiques

L'algorithme d'Euclide-Bézout

suivant: Une autre approche de monter: bad précédent: Généralisation à d'autres systèmes Table des matières

L'algorithme d'Euclide-Bézout

Soient $a,b,c\in{\mbox{\bf Z}}$ tels que $(a,b)\neq (0,0)$ . L'algorithme suivant sert à calculer le PGCD et la solution générale $(x,y)\in{\mbox{\bf Z}}^2$ de l'équation de Bézout

$\displaystyle a x+b y= c.$

L'algorithme se présente sous forme d'un tableau. Dans une première étape on remplit les deux premières lignes comme indiquées dans le tableau ci-dessous. Le coefficient

n'est pas défini; le coefficient

est le quotient de la division euclidienne de

par

. Les lignes suivantes se calculent chacune en fonction des deux précédentes comme indiquée ci-dessous.


	a			0
	b		0		est une div. eucl.
		...	...	...
$\vdots$
	$r_{k-1}$	$q_{k-1}$	$x_{k-1}$	$y_{k-1}$
					$r_{k-1}=q_k r_k+r_{k+1}$ est une div. eucl.
	$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$

	$r_{N+1}=0$		$x_{N+1}$	$y_{N+1}$

La première colonne contient donc les restes des divisions euclidiennes successives, la deuxième colonne les quotients et les deux dernières colonnes des coefficients

tels que

(voir la démonstration ci-dessous).

Les coefficients de la première colonne forment une suite strictement décroissante de nombres positifs entiers. Par définition, est le plus petit entier avec $r_{N+1}=0$ .

Théorème On a PGCD . Si PGCD divise , la solution générale de l'équation

$\displaystyle ax+by=c$

est donnée par

$\displaystyle x$	$\displaystyle =$	$\displaystyle \frac{c}{\mbox{PGCD }(a,b)}x_N+l x_{N+1}$
$\displaystyle y$	$\displaystyle =$	$\displaystyle \frac{c}{\mbox{PGCD }(a,b)}y_N+l y_{N+1}$

où $l\in{\mbox{\bf Z}}$ . Si PGCD ne divise pas , l'équation n'admet pas de solution $(x,y)\in{\mbox{\bf Z}}^2$ .

Exemple 22 Nous cherchons le PGCD

et toutes les solutions de l'équation

PGCD

. Nous obtenons le tableau


		0
	0





0

Ainsi PGCD

et la solution générale de l'équation

est donnée par

$\displaystyle x$	$\displaystyle =$	$\displaystyle 11 - 25 l$
$\displaystyle y$	$\displaystyle =$	$\displaystyle -29 + 66 l$

où $l\in{\mbox{\bf Z}}$ .

Notons que et . Notons aussi que les dernières deux colonnes sont des suites alternées et que les modules de , sont strictement croissants pour $k\geq 3$ . En particulier, nous avons $0\leq x_N< -(-25)$ et $-66< y_N\leq 0$ . La solution est la seule avec ces propriétés. Les coefficients apparaissent dans l'identité

$\displaystyle \frac{198}{75}= 2 + \frac{1}{1+ \frac{\textstyle \mbox{\rule{0cm... ...8\baselineskip}}1}{\textstyle \mbox{\rule{0cm}{0.8\baselineskip}}2}}}}} \;\; .$

Voir les exercices après la démonstration.

Démonstration. Notons d'abord que l'algorithme s'arrête. En effet, $r_{k+1}$ est le reste d'une division euclidienne par . Donc $r_{k+1}$ est compris entre 0 et . Les forment donc une suite strictement décroissante de nombres positifs entiers. Une telle suite doit aboutir à zéro après un nombre fini d'étapes.

Montrons que PGCD . Montrons d'abord que nous avons

PGCD $\displaystyle (r_{k-1}, r_k)=$ PGCD $\displaystyle (r_k, r_{k+1}).$

En effet, par construction, nous avons une équation

$\displaystyle r_{k-1} = q_k r_k + r_{k+1}.$

Elle montre que l'ensemble des diviseurs communs à $r_{k-1}$ et

est égal à l'ensemble des diviseurs communs à

et $r_{k+1}$ . En particulier, les plus grands éléments de ces ensembles sont égaux. La formule pour

s'ensuit par récurrence :

PGCD $\displaystyle (a,b)$	$\displaystyle =$	PGCD $\displaystyle (b,r_3)= \ldots$
	$\displaystyle =$	PGCD $\displaystyle (r_{N-1},r_N)=$ PGCD $\displaystyle (r_N, r_{N+1})=$ PGCD $\displaystyle (r_N,0)= r_N.$

Pour montrer la deuxième affirmation, nous introduisons les matrices

$\begin{displaymath} S_k=\left[ \begin{array}{cc} x_k & x_{k+1} y_k & y_{k+1} \end{array}\right] \: , \;k\geq 1. \end{displaymath}$

Nous avons

$\begin{displaymath} S_1=\left[ \begin{array}{cc} 1 & 0 0 & 1 \end{array}\righ... ...t[ \begin{array}{cc} 0 & 1 1 & -q_{k+1} \end{array}\right]. \end{displaymath}$

Par récurrence, il s'ensuit que

$\displaystyle [ a\;\;b] S_k = [r_k \;\; r_{k+1}]$ et $\displaystyle \quad \det S_k=-(-1)^k.$

En particulier, nous avons $[a\;\; b] S_N=[r_N\;\; 0]$ et la matrice

$\begin{displaymath} S_N^{-1}=-(-1)^N \left[ \begin{array}{cc} y_{N+1} & -x_{N+1} -y_N & x_N \end{array}\right] \end{displaymath}$

est à coefficients entiers. Donc si nous posons

$\displaystyle \left[ \begin{array}{c} u v \end{array} \right] = S_N^{-1} \left[ \begin{array}{c} x y \end{array} \right]\: , \;$

alors

sont des entiers. Nous avons

$\begin{displaymath}[a \;\; b]\left[ \begin{array}{c} x y \end{array} \right]=... ...r_N\;\; 0] \left[ \begin{array}{c} u v \end{array} \right] \end{displaymath}$

de façon que l'équation

$\displaystyle [a \;\; b] \left[ \begin{array}{c} x y \end{array} \right]=c$ $\displaystyle \mbox{(resp. $ax+by=c$)}$

est équivalente à l'équation

$\displaystyle [r_N \;\; 0] \left[ \begin{array}{c} u v \end{array} \right]=c$ $\displaystyle \mbox{(resp. $r_N u + 0 v=c$)}$ $\displaystyle .$

Or il est clair que cette dernière équation admet des solutions si et seulement si

divise

et que dans ce cas la solution générale est

$\begin{displaymath} \left[ \begin{array}{c} u v \end{array}\right] = \left[ \begin{array}{c} c/r_N l \end{array}\right] \: , \; \end{displaymath}$

où $l\in{\mbox{\bf Z}}$ . Donc l'équation

admet des solutions si et seulement si

divise

et dans ce cas la solution générale est

$\begin{displaymath} \left[ \begin{array}{c} x y \end{array}\right] = S_N \le... ...x_{N+1} \\ \frac{c}{r_N} y_N + l y_{N+1} \end{array}\right]. \end{displaymath}$

Exercices. 1) Trouver toutes les solutions $(x,y)\in{\mbox{\bf Z}}^2$ des équations suivantes : a) , b) , c) , d) , e) f) .

2) Avec les notations de l'algorithme d'Euclide-Bézout, montrer que

$\displaystyle x_{N+1}= (-1)^N \frac{c}{\mbox{PGCD }(a,b)} \mbox{ et } y_{N+1}= -(-1)^N \frac{a}{\mbox{PGCD }(a,b)}.$

Indication : On pourra utiliser l'identité

$\begin{displaymath} \left[ \begin{array}{cc} a & b -y_N & x_N \end{array}\rig... ...[ \begin{array}{cc} r_N & 0 0 & -(-1)^N \end{array}\right]. \end{displaymath}$

3) Supposons . Avec les notations de l'algorithme d'Euclide-Bézout, montrer que

$\displaystyle \frac{a}{b}=q_2+ \frac{\textstyle \mbox{\rule{0cm}{0.8\baselinesk... ...aselineskip}}r_5}{\textstyle \mbox{\rule{0cm}{0.8\baselineskip}}r_4}}}= \ldots$

4) Nous allons caractériser la solution fournie par l'algorithme d'Euclide-Bézout parmi toutes les solutions de l'équation de Bézout. Supposons, pour simplifier, que et que PGCD .

a) Montrer qu'il existe une solution $(x_+,y_+)\in{\mbox{\bf Z}}^2$ de 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{\mbox{\bf Z}}^2$ de et une seule telle que $-b<x_-\leq 0$ . Montrer qu'on a $0\leq y_+<a$ .

c) Montrer qu'on a si est impair et si est pair. Indication : on pourra commencer par montrer que les suites et sont strictement croissantes pour $k\geq 3$ .

5) Nous allons estimer le nombre d'étapes de l'algorithme d'Euclide-Bézout. Pour un couple d'entiers avec $a>b\geq 0$ notons le nombre apparaissant comme nombre d'étapes de l'algorithme d'Euclide-Bézout appliqué à .

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

b) Soit , et $F_n=F_{n-1}+F_{n-2}$ pour tout . Par définition, le nombre est le -ième 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'égalité ne se présente que pour et $b=F_{n-1}$ .