Soient
tels que
.
L'algorithme suivant sert à calculer le
PGCD et la
solution générale
de l'équation de Bézout
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.
...
...
...
est une div. eucl.
,
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 .
ThéorèmeOn a
PGCD . Si
PGCD divise ,
la solution générale de l'équation
est donnée par
où
. Si
PGCD ne divise pas , l'équation
n'admet pas de solution
.
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
où
.
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 . En particulier,
nous avons
et
. La solution
est la seule avec ces propriétés.
Les coefficients apparaissent dans l'identité
Voir les exercices
après la démonstration.
Démonstration. Notons d'abord que l'algorithme s'arrête.
En effet, est le reste d'une division euclidienne par
. Donc 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 PGCD
En effet, par construction, nous avons une équation
Elle montre que l'ensemble des diviseurs communs à
et est égal à l'ensemble des diviseurs communs à
et . En particulier, les plus grands éléments
de ces ensembles sont égaux. La formule pour s'ensuit par
récurrence :
PGCD
PGCD
PGCD PGCD PGCD
Pour montrer la deuxième affirmation, nous introduisons les
matrices
Nous avons
Par récurrence, il s'ensuit que
et
En particulier, nous avons
et la
matrice
est à coefficients entiers. Donc si nous posons
alors sont des entiers. Nous avons
de façon que l'équation
est équivalente à l'équation
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
où
. Donc l'équation admet des solutions
si et seulement si divise et dans ce cas
la solution générale est
Exercices. 1) Trouver toutes les solutions
des
équations suivantes : a) , b) , c) ,
d) , e)
f)
.
2) Avec les notations de l'algorithme d'Euclide-Bézout, montrer
que
Indication : On pourra utiliser l'identité
3) Supposons . Avec les notations de l'algorithme
d'Euclide-Bézout, montrer que
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
de
et une seule
telle que
. Montrer qu'on a
.
b) Montrer qu'il existe une solution
de
et une seule
telle que
. Montrer qu'on 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 .
5) Nous allons estimer le nombre d'étapes de
l'algorithme d'Euclide-Bézout.
Pour un couple d'entiers avec notons
le nombre apparaissant comme nombre d'étapes de l'algorithme
d'Euclide-Bézout appliqué à .
a) Montrer que
.
b) Soit , et
pour tout
. Par définition, le nombre est le -ième
nombre de Fibonacci. Montrer que
,
que
si et que l'égalité
ne se présente que pour et .