Théorème de Bézout et équations diophantiennes
Mathématicien français du dix-huitième siècle, Étienne Bézout fut l’auteur de plusieurs manuels qui ont marqué leur époque. De nos jours, son nom reste surtout attaché à deux théorèmes dont l’un est particulièrement important en arithmétique.
Rappels
Soit l’ensemble des diviseurs de deux entiers relatifs \(a\) et \(b.\) On le note \(D(a, b).\)
Le plus grand élément de \(D(a, b)\) est appelé plus grand commun diviseur (PGCD) de \(a\) et de \(b,\) noté pgcd\((a,b).\) Si pgcd\((a,b) = 1,\) alors \(a\) et \(b\) sont premiers entre eux.
Identité de Bézout (ou théorème de Bachet-Bézout)
Identité de Bézout : soit \(a\) et \(b\) deux entiers non nuls. Alors il existe un couple d’entiers relatifs \((x, y)\) tel que \(ax + by\) \(=\) pgcd\((a,b).\)
Par conséquent, si pgcd\((a,b) = 1,\) il existe un couple d’entiers relatifs \((x, y)\) tel que \(ax + by = 1.\) C’est ce cas particulier qui est appelé théorème de Bézout.
Autre conséquence, tout diviseur commun à \(a\) et à \(b\) divise leur PGCD.
Corollaire de Bézout : l’équation \(ax + by = c\) admet des solutions entières si et seulement si \(c\) est un multiple de pgcd\((a, b).\)
Illustrons l’identité. Nous savons que pgcd\((6, 27) = 3.\) Si nous prenons \(x = 5\) et \(y = -1,\) alors \(5 × 6 + (-1) × 27\) \(=\) \(3.\)
Voir l'exercice de la page sur les droites rationnelles et le premier exercice sur équations diophantiennes.
Démonstration de l’identité
Soit \(E\) l’ensemble constitué des entiers naturels strictement positifs décomposables sous la forme \(ax + by.\)
Cela signifie que le plus petit élément de \(E\) est pgcd\((a,b).\)
On démontre facilement que \(E\) est un ensemble non vide. En effet, si \(a > 0\) et si l’on choisit \(x = 1\) et \(y = 0,\) nous obtenons \(ax + b = a\) et \(a ∈ \mathbb{N}^*.\) En revanche, si \(a < 0\) on choisit \(x = -1\) et \(y = 0\) et nous obtenons \(-a\) qui est bien, dans ce cas de figure, un entier naturel.
Nommons \(d\) le plus petit élément de \(E.\) Donc \(ax + by = d.\) Montrons que \(d\) divise \(a.\)
Si l’on effectue une division euclidienne de \(a\) par \(d,\) alors \(a = qd + r\) (\(q\) est le quotient et \(r\) est le reste).
Donc \(a = (ax by)q + r\)
\(⇔ a - q(ax + by) = r\)
\(⇔ a - qax - qby = r\)
\(⇔ a(1 - qx) + b(-qy) = r\)
Si \(r > 0,\) alors \(r ∈ E\) mais comme \(r < d\) cela contredit que \(d\) est le plus petit élément de \(E.\) Donc \(r = 0.\) On peut faire le même raisonnement avec \(b.\)
Donc \(d\) divise \(a\) et \(b\) et ainsi \(d =\) pgcd\((a,b).\)
Application aux équations diophantiennes
Les équations diophantiennes sont des équations polynomiales à coefficients entiers et à une ou plusieurs inconnues entières (éventuellement rationnelles). Elles sont nommées ainsi en hommage à Diophante d’Alexandrie, mathématicien du troisième siècle.
Nous nous intéresserons ici aux équations de type \(ax + by = c.\) Elles peuvent n’avoir aucune solution. La recherche de leur existence est d’ailleurs l’application de l’identité ou du théorème de Bézout.
Par exemple, l’équation \(21x + 2y = 1\) admet au moins un couple de solutions puisque 21 et 2 sont premiers entre eux (théorème de Bézout). De même l’équation \(81x + 7y = 2\) admet au moins un couple de solutions puisque 81 et 7 sont premiers entre eux, donc l'équation \(81u + 7v = 1\) admet des solutions et il suffit de poser \(x = 2u\) et \(y = 2v\) pour en déduire que l’équation admet bien au moins un couple de solutions.
En revanche, inutile de chercher à résoudre l’équation \(7x + 28y = 13\) puisque pgcd\((7,28) = 7\) et 13 n’est pas un multiple de 7.
Ensuite, on cherche un couple de solutions particulier. C’est l’objet de l’exercice ci-dessous. Attention, celui-ci n’est pas terminé puisqu’il faut ensuite trouver TOUTES les solutions, ce qui nécessite l'application du théorème de Gauss (qui ne fait pas l’objet de cette page).
Comment déterminer les coefficients d’une identité de Bézout ?
Première technique, nous conservons la formulation avec \(a\) et \(b.\)
Prenons par exemple l’équation diophantienne \(42x + 26y = 2.\) Donc \(a = 42\) et \(b = 26.\)
\(42 = 2 × 3 × 7\) et \(26 = 2 × 13,\) donc 2 est bien pgcd\((42,26).\)
Première étape de l’algorithme d’Euclide : \(42 = 1 × 26 + 16\)
Exprimons le reste en fonction de \(a\) et \(b.\)
\(a = b + 16\) (plus évident que ça, impossible à trouver !).
Donc \(16 = a - b\)
Deuxième étape de l’algorithme : \(26 = 1 × 16 + 10.\)
Exprimé en fonction de \(a\) et \(b,\) cela donne \(b = 1 × (a - b) + 10\)
Donc \(2b - a = 10\)
Troisième étape euclidienne : \(16 = 1 × 10 + 6\)
On l’exprime en fonction de \(a\) et \(b\) : \(a - b = 2b - a + 6\)
D’où \(-3b + 2a = 6\)
Quatrième étape : \(10 = 1 × 6 + 4\)
Il s’ensuit que \(2b - a = -3b + 2a + 4\) et donc \(5b - 3a = 4\)
Cinquième étape : \(6 = 1 × 4 + 2.\) Cette fois, nous sommes arrivés au reste égal à 2. La victoire est proche.
\(-3b + 2a = 5b - 3a + 2\)
\(⇔ -8b + 5a = 2\)
Il ne reste plus qu’à remplacer \(a\) et \(b\) par leurs valeurs.
\(-8 × 26 + 5 × 42 = 2\)
Une solution particulière est donc le couple \((5\,;-8).\)
Note : nous aurions pu modifier l’équation en divisant ses membres par 2 et résoudre \(21x + 13y = 1.\) Sa résolution n’aurait pas été plus rapide.
Seconde technique : on remonte l’algorithme d’Euclide.
Réécrivons-le :
\(42 = 1 × 26 + 16\)
\(26 = 1 × 16 + 10\)
\(16 = 1 × 10 + 6\)
\(10 = 1 × 6 + 4\)
\(6 = 1 × 4 + 2\)
Il faut partir de la dernière ligne puis remonter jusqu’à la première en exprimant à chaque étape le reste comme une combinaison exprimée à l’étape précédente.
\(2 = 6 - (1 × 4).\) Le reste à faire disparaître est 4.
\(2 = 6 - (10 - 6).\) Il serait ballot de développer.
\(2\) \(=\) \(6 - 10 + 6\) \(=\) \(2 × 6 - 10.\) Le reste à éliminer est 6.
\(2\) \(=\) \(2(16 - 1 × 10) - 10\) \(=\) \(2 × 16 - 2 × 10 - 10\) \(=\) \(2 × 16 - 3 × 10\)
\(2\) \(=\) \(2 × 16 - 3(26 - 16)\) \(=\) \(2 × 16 - 3 × 26 + 3 × 16\) \(=\) \(5 × 16 - 3 × 26\)
\(2 = 5(42 - 26) - 3 × 26\) \(=\) \(5 × 42 - 5 × 26 - 3 × 26\) \(=\) \(5 × 42 - 8 × 26.\)
Nous retrouvons notre couple de solutions particulières \((5\,;-8).\)
