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

Imaginons un site internet qui permettrait, sans frais, l’achat et la vente (au même cours) de deux types d’objets :

– des objets de type A à 14 €                        – des objets de type B à 30

• Est-il possible de réaliser une transaction de 252 € sur ce site ?
Si oui, combien d’objets de chaque type faut-il acheter ou vendre ?
(Nota : il n’est pas possible de fractionner les objets !)
• Même question pour une transaction de 2 € ?
• Et une transaction de 1 € ?
• Et une transaction de 0 € ? (autrement qu’en ne faisant rien !)

Sur un autre site du même genre, c’est le même principe mais les prix des objets sont les suivants :

– des objets de type C à 15 €                        – des objets de type D à 28

Mêmes questions que précédemment.

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

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 :

0 15 30 45 60 75 90 105 etc.
0 0 15 30 45 60 75 90 105 120
7 7 22 37 52 67 82 97 112 127
14 14 29 44 59 74 89 104 119 134
21 21 36 51 66 81 96 111 126 141

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 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} :

Multiples de 15 : 0 ; 15 ; 30 ; 45 ; 60 ; 75 ; 90 ; 105 ; 120 ; 135 ; 150 ; 165 ; 180 ; 195 ; …
Multiples de 28 : 0 ; 28 ; 56 ; 84 ; 112 ; 140 ; 168 ; 196 ; 224 ; 252 ; 280 ; …

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…

Voir la démonstration
Déjà, cet ensemble H n’est pas vide ; en effet, il contient a et b. Il contient également des nombres positifs.
Puisqu’il n’est pas vide, il admet un plus petit élément positif non nul que nous noterons \delta.

Nous allons démontrer que \delta est le PGCD de a et de b. Notons d ce PGCD.

Puisque \delta \in H, il existe des entiers u et v tels que \delta = au + bv. Or, le PGCD d de a et b divise toute combinaison linéaire de a et b donc divise \delta :

d | \delta

En particulier :

d \leq \delta

Montrons maintenant que \delta \geq d.
Pour cela, on effectue la division euclidienne de a par \delta :

\exists (q,r) \in \mathbb{Z} \times \mathbb{N}, a = \delta q + r \, \, \text{ avec } 0 \leq r < \delta

Intéressons-nous au reste r. On constate que c’est aussi une combinaison linéaire de a et b (puisque \delta l’est) :

r = a - \delta q = a - (au + bv)q = a(1 - u) + bvq

Donc r \in H. Mais par définition de la division euclidienne, on a 0 \leq r < \delta. Or, \delta est le plus petit élément strictement positif de H. Il n’y a donc pas d’autre choix que d’avoir r=0. Autrement dit :

a = \delta q

Cela signifie que \delta divise a.

On montrerait, de même, que \delta divise b.

Cet entier \delta est donc un diviseur commun de a et b. Mais on a noté d le PGCD de a et b. Par conséquent :

\delta \leq d

Bilan : on a vu que d \leq \delta et \delta \leq d donc :

\delta = d

Qu’est-ce que tout cela signifie ? Eh bien que le plus petit entier naturel (non nul) que l’on pourra obtenir via une combinaison linéaire de a et b n’est autre que le PGCD de a et b !

Ainsi, avec les nombres 14 et 30 (dont le PGCD est 2), le plus petit entier réalisable par combinaison linéaire sera 2. On pourra également obtenir tous les multiples de ce PGCD.
Tandis qu’avec les nombres 15 et 28 (dont le PGCD est 1) on pourra obtenir tous les entiers voulus par combinaisons linéaires.

La notion sous-jacente à toute cette étude était donc ce fameux PGCD. C’est lui qui détermine l’ensemble des valeurs parcourues par ax + by.

Prolongeons encore un peu le raisonnement et cette fois effectuons la division euclidienne de n’importe quel élément h=ax+by de H par le PGCD d :

\exists (q,r) \in \mathbb{Z} \times \mathbb{N}, h = d q + r \, \, \text{ avec } 0 \leq r < d

Intéressons-nous encore au reste r. On constate que c’est aussi une combinaison linéaire de a et b (puisque h et d le sont) :

r = h - d q = ax+by - (au + bv)q = a(x - qu) + b(y-vq)

Donc r \in H. Mais par définition de la division euclidienne, on a 0 \leq r < d. Or, d est le plus petit élément strictement positif de H. Il n’y a donc pas d’autre choix que d’avoir r=0. Autrement dit :

h = d q

Cela signifie que les éléments de H sont tous des multiples du PGCD de a et b. Réciproquement, soit D un multiple de d, cela signifie que D=dk = (au+bv)k = a(ku) + b(kv) \in H.

Nous venons de démontrer que l’ensemble H est exactement l’ensemble des multiples du PGCD de a et b :

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 :

Théorème  1 – Bézout version « forte »

a\mathbb{Z}+b\mathbb{Z} = d\mathbb{Z} \, \text{ où } d = \text{PGCD}(a\,;\,b)

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 :

Théorème 2 – Égalité (ou identité) de Bachet-Bézout

\exists (u\,;\,v) \in \mathbb{Z} \times \mathbb{Z} \text{ tel que } au+bv = \text{PGCD}(a\,;\,b)

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 :

Théorème 3 – Bézout version « classique »

\text{PGCD}(a\,;\,b) = 1 \, \Longleftrightarrow \exists (u\,;\,v) \in \mathbb{Z} \times \mathbb{Z} \text{ tel que } au+bv = 1

Voir deux mini-exemples d'application de ce théorème
Le théorème de Bézout ci-dessus est énoncé sous la forme d’une équivalence. Il peut donc s’utiliser dans les deux sens (et aussi de façon contraposée). Si on sait que a et b sont premiers entre-eux, alors il existe une combinaison linaire au+bv qui donne 1. Réciproquement, si on a trouvé une telle combinaison linéaire, on est assuré que a et b sont premiers entre-eux. Voyons cela à travers deux exemples.

Exemple 1

Démontrer que l’on peut trouver des entiers u et v tels que 8u+25v=1.

Il suffit de remarquer que 8 et 25 sont premiers entre-eux donc de tels entiers u et v existent !
Et dans ce cas présent, il est facile d’en trouver mentalement, par exemple u=-3 et v=1. (Il y a d’autres possibilités bien sûr, et même une infinité).

Exemple 2

Démontrer que, quel que soit l’entier naturel n, les nombres entiers 2n+5 et 3n+7 sont premiers entre-eux.

Il suffit de trouver une combinaison linéaire de 2n+5 et 3n+7 qui donne 1 pour conclure. Ici, ce n’est pas très difficile en croisant les coefficients :

(2n+5) \times 3 + (3n+7)\times (-2) = 6n + 15 - 6n - 14 = 1

Et le théorème de Bézout permet de conclure que \text{PGCD}(2n+5\,;\,3n+7)=1.

Le théorème de Bézout possède de nombreuses applications. C’est grâce à lui que l’on peut facilement déterminer l’inverse modulo n d’un entier premier avec n. Cela sera utile dans les questions de codage en cryptologie.

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=dd=\text{PGCD}(a\,;\,b)… Alors, lançons-nous dans cette résolution…

Voir la résolution

Déjà, il n’aura échappé à personne qu’une telle équation peut se simplifier par d. En effet, puisque d est un diviseur commun de a et b, il existe des entiers a' et b' tels que :

a=da' \, \text{ et } \, b=db'

Ainsi, l’équation ax+by=d est équivalente à :

da'x+db'y=d

a'x+b'y=1

Imaginons que nous ayons déjà une solution particulière (u\,;\,v) (donnée par l’algorithme d’Euclide-Bézout). On a donc, d’une part a'u+b'v=1 et d’autre part, nous cherchons à résoudre l’équation a'x+b'y=1. L’idée, très générale en mathématiques, est de soustraire les deux égalités (on raisonne donc par implication à partir de maintenant) afin d’obtenir :

a'u + b'v = a'x + b'y

Réorganisons un peu les choses :

a'(u-x) + b'(v-y)=0

Nous avons déjà rencontré cette situation là ! C’est une combinaison linéaire nulle de a' et b'. Bien sûr, pour satisfaire une telle égalité, on pourrait fixer u-x=0 et v-y=0 mais cette trivialité nous mènerait à rien d’autre que x=u et y=v ce qui ne nous intéresse pas car on cherche justement les autres couples solutions (x\,;\,y) en plus du couple solution particulier (u\,;\,v). On a vu précédemment, qu’on pouvait trouver une solution non triviale en croisant les coefficients, par exemple en fixant u-x=b' d’une part et v-y=-a' d’autre part donnant ainsi (x\,;\,y)=(u-b'\,;v+a'). Nous avons ainsi un nouveau couple solution. Mais rien ne nous empêcherait de recommencer le procédé pour obtenir alors (x\,;\,y)=(u-2b'\,;v+2a') etc. Ainsi, on construit une famille de couples de la forme :

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

On peut vérifier que ces couples obtenus sont bien des solutions de l’équation a'x+b'y=1. En effet, on a bien :

a'x+b'y=a'(u-kb')+b'(v+ka')=a'u+b'v+k(-a'b'+b'a')=1

Mais qui nous dit que l’on a ainsi décrit l’ensemble de toutes les solutions recherchées ? Eh bien, c’est encore le théorème de Bézout lui-même qui va nous tirer d’affaire ! En effet, récapitulons… On sait d’une part que nous avons l’égalité a'(u-x) + b'(v-y)=0 mais d’autre part, n’oublions pas que, d’après le théorème de Bézout, a'u+b'v=1 alors en multipliant cette dernière égalité par (u-x), il vient :

a'u(u-x)+b'v(u-x)=u-x

Mais puisque a'(u-x)=b'(y-v), l’égalité ci-dessus devient :

ub'(y-v)+b'v(u-x)=u-x

On constate que l’on peut factoriser par b' :

b'[u(y-v)+v(u-x)]=u-x

Cela signifie que b' divise u-v. Par conséquent, il existe un entier relatif k tel que :

b'k=u-x

x=u-kb'

Mais maintenant que l’on sait que l’on a nécessairement x=u-kb', en réinjectant cette relation dans la relation a'(u-x)=b'(y-v), il vient :

a'kb'=b'(y-v)

Et comme b' n’est pas nul (car b ne l’est pas) :

a'k=(y-v)

y=v+ka'

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}

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 :

Théorème 4 – Lemme de Gauss

\text{Si } d \text{ divise un produit } ab \text{ et si } \text{PGCD}(a\,;\,d) = 1 \, \text{ alors } d \text{ divise } b \text{ seul}

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

Voir la démonstration
En effet, puisque \text{PGCD}(a\,;\,d) = 1, il existe des entiers relatifs U et V tels que :

aU+dV=1

En multipliant par b :

abU+dbV=b

Or, par hypothèse, d divise le produit ab. Et de façon évidente, d divise dbV, par conséquent, il divise la somme abU+dbV qui n’est autre que b, et c’est ce qu’il fallait montrer.

Voir deux mini-exemples d'application de ce théorème

Exemple 1

Résoudre l’équation 3x=5yx, y \in \mathbb{Z}.

Bien sûr, on trouve immédiatement la solution (x\,;\,y)=(5\,;\,3) mais la consigne « résoudre » signifie de trouver toutes les solutions et pas juste une seule ! Que pouvons-nous déduire de l’égalité 3x=5y ? Elle indique (entre autres) que 5 divise le produit 3x. Mais comme, par ailleurs, on a \text{PGCD}(5\,;\,3)=1, on en déduit, d’après le lemme de Gauss que 5 divise x seul, ce qui signifie :

x=5k \, \text{ où } k \in \mathbb{Z}

Par conséquent, il vient :

3\times 5k=5y

y=3k

S’il y a des solutions, elles sont nécessairement de la forme (x\,;\,y)=(5k\,;\,3k)k \in \mathbb{Z}. Réciproquement, il est clair que tous ces couples sont solution. En conclusion, l’ensemble S des couples solutions est :

(x\,;\,y)=(5k\,;\,3k)k \in \mathbb{Z}

Lemme d’Euclide
Soit p un nombre premier. Démontrer que :

p | ab \, \Longrightarrow \bigr(p |a \text{ ou } p | b \bigr)

Remarque : la notation p | ab signifie «p divise ab».

Raisonnons par disjonction des cas selon que p divise a ou non :

  • si p | a, il n’y a rien à faire puisque la conclusion est déjà satisfaite ;
  • si p ne divise pas a alors, comme p est un nombre premier, on a \text{PGCD}(a\,;\,p)=1 et d’après le lemme de Gauss, on en déduit que p | b.

Ce lemme de Gauss est très pratique pour résoudre des équations diophantiennes telles que ax+by=dd=\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=cc est un multiple de d.

Nous allons voir comment dans la section suivante.

Partie V – Applications

Première application : sans contexte
Résoudre l’équation diophantienne

11x+19y=549

Voir la résolution

Première étape

On cherche à simplifier les coefficients de l’équation. Ici, il n’y a pas de simplification à faire car \text{PGCD}(11\,;\,19)=1.

Deuxième étape

On s’assure que l’équation possède bien des couples solutions. Si ce n’est pas le cas, c’est terminé ! La condition nécessaire et suffisante pour qu’une équation ax+by=c admette des couples solutions est que \text{PGCD}(a\,;\,b) divise c ce qui est toujours le cas lorsque a et b sont premiers entre-eux (comme ici).

Troisième étape

On cherche une solution particulière (u\,;\,v) à l’équation avec second membre égal au \text{PGCD}(a\,;\,b). Ici il s’agit de l’équation 11x+19y=1. Pour cela, on met en œuvre l’algorithme d’Euclide-Bézout ou en examinant les multiples respectifs de 11 et 19. On obtient  (u\,;\,v)=(7\,;\,-4). On a donc :

11 \times 7 + 19 \times (-4) = 1

On multiplie ensuite par 549 afin de récupérer le bon second membre :

11 \times 3843 + 19 \times (-2196) = 549

Quatrième étape

On retranche membre à membre l’équation générale 11x+19y=549 et la relation ci-dessus avec la solution particulière 11 \times 3843 + 19 \times (-2196) = 549 afin d’éliminer le second membre. Attention ! À partir de ce moment là, on raisonne par implication (et plus par équivalence) ; il sera impératif de vérifier les solutions  !

11(x-3843) + 19(y+2196) = 0

19(y+2196) = 11(3843-x) \quad (\star)

Cinquième étape

On applique le lemme de Gauss !

La relation 19(y+2196) = 11(3843-x) montre (entres autres) que 19 divise le produit 11(3843-x). Mais 19 et 11 sont premiers entre-eux ; par conséquent, d’après le lemme de Gauss, 19 divise (3843-x). Cela signifie qu’il existe un entier relatif k tel que :

3843-x=19k

x=3843-19k

Et en remplaçant dans l’égalité (\star) :

19(y+2196) = 11 \times 19k

y+2196=11k

y=-2196+11k

Sixième étape

On vérifie et on conclut !

La vérification consiste à s’assurer par le calcul de 11x+19y que, réciproquement, on obtient bien le second membre 549 lorsqu’on remplace x et y par les expressions trouvées :

{\footnotesize 11x+19y=11(3843-19k)+19(-2196+11k)=42273-41724=549}

En conclusion, les couples (x\,;\,y) solutions  de l’équation 11x+19y=549 sont bien :

(x\,;\,y)=(3843-19k\,;\,-2196+11k) \, \text{ où } k \in \mathbb{Z}

Comprendre pourquoi on a raisonné par implication

On peut toujours additionner ou soustraire des égalités. Par exemple, pour la soustraction (comme on l’a fait ci-dessus), cela se traduit mathématiquement ainsi :

\bigl( A=B \text{ et } C=D \bigr) \Longrightarrow A-C=B-D

Mais la réciproque est fausse. En effet, on a 5 - 2 = 4 - 1 mais on ne peut pas en déduire que 5 est égal à 4 et 2 est égal à 1 !

Deuxième application : avec contexte
Dans une armurerie, il y a un stock de 40 pistolets à 231 € et de 25 fusils à 399 €. Vous êtes un policier qui piste un trafiquant d’armes qui vient faire un gros achat dans cette armurerie. Vos moyens informatisés vous permettent d’apprendre que le trafiquant vient de dépenser 11529 € mais vous n’avez pas le détail de l’achat.
Pouvez-vous retrouver exactement le nombre pistolets et de fusils achetés ?
Voir la résolution

En notant x et y le nombre de pistolets et de fusils achetés, respectivement, nous devons donc résoudre l’équation :

231x+399y=11529

en tenant compte des conditions 0 \leq x \leq 40 et 0 \leq y \leq 25.

Cette équation n’a de solutions qu’à condition que le PGCD de 231 et 399 divise 11529.

Via l’algorithme d’Euclide, on a :

\text{PGCD}(231\,;\,399) = 21

et 21 est bien un diviseur de 11529 car 11529=21\times 549. Par conséquent, l’équation à résoudre se réduit à :

11x+19y=549

Il s’agit de l’équation résolue dans l’application précédente et nous avions trouvé pour couples solutions :

(x\,;\,y)=(3843-19k\,;\,-2196+11k) \, \text{ où } k \in \mathbb{Z}

Mais ici, nous avons les deux contraintes 0 \leq x \leq 40 et 0 \leq y \leq 25 qui s’écrivent :

0 \leq 3843-19k \leq 40 \quad \text{ et } \quad 0 \leq -2196+11k \leq 25

-3843 \leq -19k \leq -3803 \quad \text{ et } \quad 2196 \leq 11k \leq 2221

\frac{-3843}{-19} \geq k \geq \frac{-3803}{-19} \quad \text{ et } \quad \frac{2196}{11} \leq k \leq \frac{2221}{11}

Mais k étant un entier :

201 \leq k \leq 202 \quad \text{ et } \quad 200 \leq k \leq 201

La seule possibilité est d’avoir k=201, ce qui donne :

(x\,;\,y)=(24\,;\,15)

Le trafiquant a donc acheté 24 pistolets et 15 fusils.

 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

CAPTCHA
Change the CAPTCHA codeSpeak the CAPTCHA code
 

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.