A la découverte des théorèmes de Bézout

Le théorème d’Étienne Bézout (mathématicien Français, 1730 – 1783) est en rapport avec le PGCD (Plus Grand Commun Diviseur) de deux entiers a et b. Ce théorème se décline sous plusieurs versions :
• version « faible » (égalité ou identité de Bachet-Bézout)
• version « équivalence », la plus utilisée (cas des entiers premiers entre-eux)
• et une version « forte », moins connue des lycéens (description de l’ensemble des valeurs prises par les combinaisons linéaires de \footnotesize a et \footnotesize b).
Ces énoncés peuvent paraître simples en première lecture (il ne font apparaître que des additions et des multiplications d’entiers !) mais leurs significations sont néanmoins assez profondes et plus délicates à comprendre (elles portent sur la notion de sous-groupes de \footnotesize \mathbb{Z}).
Vous n’aurez cependant besoin d’aucune connaissance préalable (à part savoir ce qu’est un PGCD) pour lire cet article et pour découvrir, à travers des exemples simples, toutes les arcanes de ces théorèmes !

Partie I – Introduction contextuelle

Savez-vous répondre à ces questions ? Comment procéder ?

Essayons de modéliser le problème. La première question posée revient à résoudre l’équation :

{\blue{14}}x+{\textcolor{#db142e}{30}}y=252

où x et y sont des entiers qui représentent respectivement les quantités d’objets de type A et type B à acheter.

On constate que l’on peut simplifier cette équation par 2 :

{\blue{7}}x+{\textcolor{#db142e}{15}}y=126

Et puis après ? Comment procéder ? Nous n’avons qu’une seule équation pour deux inconnues !

Une première idée, enfantine, consiste à procéder de manière exhaustive. On fait la liste de tous les multiples de {\blue{7}} et la liste de tous les multiples de {\textcolor{#db142e}{15}} et on examine, en les additionnant, s’il y a moyen d’obtenir 126 :

Et là, bingo, on constate qu’on trouve bien 126 dans le tableau en faisant la combinaison linéaire suivante :

126=21+105={\blue{7}}\times 3+{\textcolor{#db142e}{15}}\times 7

En multipliant par 2 :

{\blue{14}}\times 3+{\textcolor{#db142e}{30}}\times 7=252

La réponse à la question posée est donc oui et il faut acheter trois objets à {\blue{14}} € et sept objets à {\textcolor{#db142e}{30}} €. Ouf !

Cependant, en examinant le tableau ci-dessus, il semblerait
que les entiers n’y soient pas tous présents…

On voudrait maintenant une transaction à 2 €. Déjà, juste en faisant des achats et pas de vente, ça ne va pas être possible puisque le prix d’achat le plus bas est déjà de {\blue{14}} €. Il va falloir acheter une certaine quantité d’un type d’objet et vendre une certaine quantité de l’autre type !

Nous devons donc résoudre l’équation suivante :

{\blue{14}}x+{\textcolor{#db142e}{30}}y=2

dans laquelle les inconnues x et y sont des entiers relatifs.

Comme tout à l’heure, on peut simplifier par 2 :

{\blue{7}}x+{\textcolor{#db142e}{15}}y=1

On recommence le même tableau que précédemment mais avec des multiples négatifs ? Hum… pourquoi pas, mais observons bien notre équation… Un œil averti remarquera sans peine un couple solution évident à savoir (x\,;\,y) = (-2\,;\,1). En effet :

{\blue{7}} \times (-2) +{\textcolor{#db142e}{15}}\times 1 =1

Et en multipliant par 2 :

{\blue{14}} \times (-2) +{\textcolor{#db142e}{30}}\times 1 =2

Pour avoir une transaction à 2 €, il suffit de vendre deux objets à {\blue{14}} € et d’en acheter un seul à {\textcolor{#db142e}{30}} €. Là encore la réponse est oui !

Mais on ne sait toujours pas si l’on peut « fabriquer » n’importe quel entier en faisant des combinaisons linéaires de {\blue{14}} et de {\textcolor{#db142e}{30}}…

Ceci étant dit, imaginons un instant que l’on arrive à trouver une certaine combinaison linéaire de {\blue{14}} et {\textcolor{#db142e}{30}} qui donne \textbf{1} :

{\blue{14}}u + {\textcolor{#db142e}{30}}v = 1

Dans ce cas là, on pourra « fabriquer » sans aucun problème n’importe quel entier e puisqu’il suffira de multiplier l’égalité précédente par e :

{\blue{14}}ue + {\textcolor{#db142e}{30}}ve = e

La clé du problème est donc de savoir s’il existe ce fameux couple d’entiers relatifs (u\,;\,v) tel que {\blue{14}}u + {\textcolor{#db142e}{30}}v = 1 !

Malheureusement, dans notre cas présent, notre œil un peu aiguisé, lorsqu’il observe la relation {\blue{14}}u + {\textcolor{#db142e}{30}}v = 1 se fait vite la réflexion suivante : le membre de gauche est toujours un nombre pair, tandis que le membre de droite, lui, est un nombre impair…

Par conséquent, il ne sera pas possible d’avoir une combinaison linéaire de {\blue{14}} et de {\textcolor{#db142e}{30}} qui donne 1… Pas de chance… On ne pourra pas « fabriquer » n’importe quel entier avec des {\blue{14}} et des {\textcolor{#db142e}{30}}. Par le même argument, on constate qu’il ne sera pas possible d’obtenir un nombre impair, quel qu’il soit. En revanche, dans le cas présent, nous pourrons obtenir tous les nombres pairs (il suffit de multiplier la combinaison linéaire donnant 2 vue plus haut). Mais de façon générale, avec d’autres valeurs initiales que 14 et 30, quels sont les nombres que nous pourrons fabriquer ? Certains ont peut-être déjà deviné la réponse à la question, pour les autres suspens…

Nous en saurons bientôt plus sur cette question en allant faire un tour sur le deuxième site avec des objets C et D… Mais, pas si vite, il reste encore un cas très particulier à voir : est-il possible de déterminer une combinaison linéaire qui donne 0 ? Assurément, il suffit de ne rien faire car on a toujours 0x + 0y=0… On appelle cela une trivialité. Mais existe-t-il une combinaison linéaire non triviale donnant 0 ? La réponse est oui, il suffit de croiser nos deux nombres :

{\blue{14}} \times (-30) + {\textcolor{#db142e}{30}} \times 14 = 0

Fabriquer 0 n’est donc très difficile et toujours possible même avec des coefficients non nuls.

Poursuivons nos investigations et allons maintenant faire un tour sur le deuxième site dans lequel on a des objets à {\textcolor{#458f38}{15}} € et \textcolor{#ff8b26}{28} € cette fois. Comme on l’a vu précédemment, voyons s’il est possible de trouver une certaine combinaison linéaire donnant 1 :

{\textcolor{#458f38}{15}}u + \textcolor{#ff8b26}{28}v = 1

Nous ne pouvons plus opposer un argument de parité différente comme dans l’exemple précédent. Cette fois-ci, le membre de gauche {\textcolor{#458f38}{15}}u + \textcolor{#ff8b26}{28}v peut très bien être impair (il faut et il suffit que u le soit).  Mais comment trouver un tel couple (u\,;\,v) ? Mentalement ? Pas si évident ! Dressons la liste des multiples respectifs de {\textcolor{#458f38}{15}} et de \textcolor{#ff8b26}{28} :

Existe-t-il dans ces listes deux multiples qui diffèrent de 1 ?
Oui ! Il y a dans la première liste 195 qui est {\textcolor{#458f38}{15}} \times 13 et dans la seconde, on a 196 qui est \textcolor{#ff8b26}{28} \times 7. Par conséquent, on a :

{\textcolor{#458f38}{15}} \times (-13) + \textcolor{#ff8b26}{28} \times 7 = 1

Et c’est gagné ! Partant de là, par simple multiplication, on pourra construire une combinaison linéaire de {\textcolor{#458f38}{15}} et \textcolor{#ff8b26}{28} qui donne n’importe quel entier.

Faisons un premier bilan : on a vu que, dans le premier cas (avec les nombres {\blue{14}} et {\textcolor{#db142e}{30}}), il n’est pas possible d’obtenir tous les entiers voulus, alors qu’on le peut dans le second cas (avec les nombres {\textcolor{#458f38}{15}} et \textcolor{#ff8b26}{28}) puisqu’il existe une combinaison linéaire donnant 1. Mais pourquoi, avec certaines paires d’entiers, on peut trouver une combinaison linéaire donnant 1 et pas avec d’autres ? Qu’est-ce qui différencie les deux situations ? Il nous faut tirer cela au clair !

Partie II – Formalisation et démonstration

Soient a et b deux entiers naturels non nuls. Notons a\mathbb{Z} et b\mathbb{Z} les ensembles contenant tous les multiples respectifs de a et b :

a\mathbb{Z} = \{ \dots, -3a, -2a, -a, 0, a, 2a, 3a, \dots\} b\mathbb{Z} = \{ \dots, -3b, -2b, -b, 0, b, 2b, 3b, \dots\}

On s’intéresse à l’ensemble des combinaisons linéaires de a et b ce qui nous amène à considérer un nouvel ensemble :

H = \{ax+by, \text{ où } x, y \in \mathbb{Z} \}

Ensemble que l’on note également H=a\mathbb{Z}+b\mathbb{Z}.

Nous allons démontrer que cet ensemble H est d’une forme très simple en fait…

a\mathbb{Z}+b\mathbb{Z} = d\mathbb{Z}

Voilà, l’affaire est bouclée ! Les entiers que l’on peut fabriquer, par combinaison linéaire, à partir de deux entiers a et b sont exactement les multiples de leur PGCD. C’est d’ailleurs un peu le paradoxe du PGCD car il est à la fois le plus GRAND diviseur commun de a et b et en même temps le plus PETIT entier (strictement positif) réalisable par combinaisons linéaires de a et b.

Partie III – Formulation des théorèmes

Dans la partie précédente, nous avons vu que l’ensemble des combinaisons linéaires ax+by de deux entiers a et b non nuls est exactement égal à l’ensemble des multiples du PGCD d de ces deux entiers.

C’est la version « forte » du théorème de Bézout qui se résume dans l’égalité « ensembliste » ci-dessous :

Comment comprendre ce théorème ? En disant par exemple qu’une équation de la forme ax+by=c (équation diophantienne) admettra un couple d’entiers solution (x\,;\,y) si et seulement si le nombre c est un multiple du PGCD de a et b.

En particulier, il existe une combinaison linéaire particulière qui est juste égale au PGCD de a et b. Il s’agit de l’égalité de Bachet-Bézout :

Cette égalité porte le nom de « Bachet-Bézout » car le mathématicien Claude-Gaspard Bachet de Méziriac (1581-1638) l’avait déjà découverte en 1624 bien avant que Bézout approfondisse ces questions.

En particulier, lorsque les entiers a et b sont premiers entre-eux, il existe donc un couple d’entiers relatifs (u\,;\,v) tel que au+bv=1. Mais, réciproquement, si on a trouvé une telle relation au+bv=1, alors étant donné que le PGCD d de a et b divise toute combinaison linéaire de a et b, il divise 1 et donc d=1. C’est le théorème de Bézout « classique » énoncé sous la forme d’une équivalence :

Noter qu’on n’a pas de réciproque lorsque a et b ne sont pas premiers entre-eux dans ce sens que si on a une relation du type ax+by=c, rien ne nous garantit que c soit le PGCD de a et b. Tout ce qu’on pourra dire, c’est que c  est un multiple de ce PGCD (d’après le théorème « fort » de Bézout). Par exemple, on a 2 \times 8 + 4 \times (-2) = 8 et pourtant 8 n’est pas le PGCD de 2 et 4 mais un multiple de celui-ci.

Noter également que dans l’égalité de Bachet-Bézout, il n’y a pas unicité du couple (u\,;\,v). Par exemple, prenons a=70 et b=28. Le PGCD de ces deux nombres est d=14. Il existe donc des entiers relatifs u et v tels que 70u+28v=14, ce qui se simplifie en 5u+2v=1. On voit que le couple (u\,;\,v)=(1\,;\,-2) convient mais le couple (u\,;\,v)=(-1\,;\,3) aussi. Du coup, se posent de nouvelles questions… Comment trouver un tel couple et quels sont les liens entre tous ces couples ?

Partie IV – Avant mise en œuvre des théorèmes

Avant de voir diverses applications, commençons déjà par voir comment on peut déterminer un couple (u\,;\,v) dans une égalité de Bézout. En effet, le théorème 2 nous dit qu’un tel couple existe mais ne donne aucune indication sur la façon dont on peut le trouver. Dans les cas simples, lorsque les nombres a et b ne sont pas très grands, on peut s’en sortir mentalement comme dans l’exemple ci-dessus avec a=70 et b=28. Une autre méthode consiste à lister tous les multiples de a et b et rechercher deux nombres dans ces listes qui diffèrent du PGCD. C’est ce qu’on a fait plus haut dans cet exposé avec 15 et 28. Mais si les nombres a et b sont plus grands, ces méthodes deviennent vite fastidieuses. N’y a-t-il pas un moyen, général, de déterminer u et v ? La réponse à cette question est oui ! Il suffit, pour cela, d’appliquer l’algorithme d’Euclide-Bézout (ou algorithme d’Euclide étendu). On renvoie le lecteur à nos documents sur les questions « type-bac » (BAC S – spécialité Maths – Avec rappels de cours) pour voir ou découvrir cette méthode en détail.

Allons plus loin et voyons de quelle forme sont tous ces couples (u\,;\,v). Cela revient à résoudre l’équation diophantienne ax+by=d où d=\text{PGCD}(a\,;\,b)… Alors, lançons-nous dans cette résolution…

Bilan : l’ensemble des couples solutions de l’équation ax+by=d est donc bien :

(x\,;\,y)=(u-kb'\,;\,v+ka') \, \text{ où } k \in \mathbb{Z}

où a' et b' sont tels que a=da' \, \text{ et } \, b=db'.

Pour les personnes qui connaissent les congruences, cela signifie que les couples solutions (x\,;\,y) de l’équation ax+by=d sont de la forme :

x \equiv u \, [b'] \, \text{ et } y \equiv v \, [a']

C’est bien compliqué et fastidieux tout cela ! Faudra-t-il refaire tous ces calculs à chaque fois que nous voudrons résoudre une équation du type ax+by=d ? Rassurez-vous, non ! Dans la pratique, nous utiliserons un outil merveilleux qui permettra de raccourcir considérablement les calculs, il s’agit du Lemme de Gauss :

La démonstration de ce lemme de Gauss (1777 – 1855) repose sur le théorème de Bézout…

Ce lemme de Gauss est très pratique pour résoudre des équations diophantiennes telles que ax+by=d où d=\text{PGCD}(a\,;\,b) comme on l’a fait plus haut de façon très fastidieuse ou, plus généralement, des équations diophantiennes de la forme ax+by=c où c est un multiple de d.

Nous allons voir comment dans la section suivante.

Partie V – Applications