L’identité de Bézout, ou comment remonter l’algorithme d’Euclide

L’algorithme d’Euclide descend : il réduit un couple d’entiers jusqu’à leur PGCD. Ce que l’on ignore souvent, c’est qu’on peut le remonter, et qu’en le remontant on obtient bien davantage que le PGCD : on obtient une façon de l’écrire à partir des deux nombres de départ. C’est l’identité de Bézout, et elle ouvre la résolution des équations diophantiennes.

Cet article donne d’abord le corrigé de l’exercice précédent, puis expose l’identité.

Corrigé, partie A

1. L’algorithme d’Euclide appliqué à $a=1\,386$ et $b=3\,003$ tient en deux divisions :

$\displaystyle \begin{array}{rcl} 3\,003 &=& 2\times 1\,386 + 231\\ 1\,386 &=& 6\times 231 + 0 \end{array}$

Le dernier reste non nul vaut 231, donc $\mathrm{pgcd}(1\,386\,;\,3\,003)=231$ .

2. Reprenons le lemme de l’article précédent : chaque étape de l’algorithme conserve l’ensemble des diviseurs communs. À la dernière étape, le couple est $(d\,;\,0)$ où $d$ est le PGCD, et les diviseurs communs de $d$ et de 0 sont exactement les diviseurs de $d$ . D’où un résultat qui servira partout :

Les diviseurs communs de $a$ et $b$ sont exactement les diviseurs de $\mathrm{pgcd}(a\,;\,b)$ .

Notons $m=\mathrm{pgcd}(a\,;\,b)$ . Un entier $d$ divise $a$ , $b$ et $c$ si et seulement s’il divise $a$ et $b$ , et divise $c$ ; c’est-à-dire si et seulement s’il divise $m$ et divise $c$ ; c’est-à-dire si et seulement s’il divise $\mathrm{pgcd}(m\,;\,c)$ . Les deux triplets ont donc les mêmes diviseurs communs, et le même plus grand. $\square$

3. Il reste à calculer $\mathrm{pgcd}(231\,;\,1\,260)$ :

$\displaystyle \begin{array}{rcl} 1\,260 &=& 5\times 231 + 105\\ 231 &=& 2\times 105 + 21\\ 105 &=& 5\times 21 + 0 \end{array}$

Donc $\mathrm{pgcd}(1\,386\,;\,3\,003\,;\,1\,260)=21$ .

4. Par décomposition :

$\displaystyle \begin{array}{rcl} 1\,386 &=& 2\times 3^{2}\times 7\times 11\\ 3\,003 &=& 3\times 7\times 11\times 13\\ 1\,260 &=& 2^{2}\times 3^{2}\times 5\times 7 \end{array}$

Les seuls facteurs premiers présents dans les trois écritures sont 3 et 7, chacun à l’exposant 1 au minimum. Le PGCD vaut donc $3\times 7=21$ . Le résultat concorde — mais il aura fallu factoriser trois nombres, là où cinq divisions suffisaient.

Corrigé, partie B

5. La relation de la question 6 donne immédiatement

$\displaystyle \mathrm{ppcm}(1\,386\,;\,3\,003)=\frac{1\,386\times 3\,003}{231}=6\times 3\,003=18\,018$

en simplifiant $1\,386/231=6$ avant de multiplier. Aucune factorisation nouvelle.

6. Posons $m=\mathrm{pgcd}(a\,;\,b)$ , puis $a=ma^{\prime}$ et $b=mb^{\prime}$ . Les entiers $a^{\prime}$ et $b^{\prime}$ sont premiers entre eux : un diviseur commun $d$ de $a^{\prime}$ et $b^{\prime}$ donnerait à $md$ le statut de diviseur commun de $a$ et $b$ , donc $md\leq m$ , donc $d=1$ .

Le nombre $ma^{\prime}b^{\prime}$ est un multiple commun, puisqu’il vaut $ab^{\prime}$ et aussi $ba^{\prime}$ . Montrons qu’il divise tout multiple commun $M$ . Écrivons $M=ak=ma^{\prime}k$ . Comme $b$ divise $M$ , l’entier $mb^{\prime}$ divise $ma^{\prime}k$ , donc $b^{\prime}$ divise $a^{\prime}k$ . Or $a^{\prime}$ et $b^{\prime}$ sont premiers entre eux ; nous verrons plus bas que cela force $b^{\prime}$ à diviser $k$ . Alors $k=b^{\prime}k^{\prime}$ et $M=ma^{\prime}b^{\prime}k^{\prime}$ .

Ainsi $\mathrm{ppcm}(a\,;\,b)=ma^{\prime}b^{\prime}$ , et

$\displaystyle \mathrm{pgcd}(a\,;\,b)\times\mathrm{ppcm}(a\,;\,b)=m\times ma^{\prime}b^{\prime}=(ma^{\prime})(mb^{\prime})=ab. \qquad\square$

Corrigé, partie C : la question qui piège

7. Non. Le contre-exemple le plus court est $a=b=c=2$ : le PGCD vaut 2, le PPCM vaut 2, leur produit vaut 4, tandis que $abc=8$ .

Une identité vraie pour deux nombres n’a aucune raison de l’être pour trois. C’est l’une des habitudes de pensée les plus coûteuses en mathématiques, et elle ne se corrige que par l’exemple.

Il existe bien une formule correcte, mais elle est plus lourde :

$\displaystyle \mathrm{ppcm}(a\,;\,b\,;\,c)=\frac{abc\cdot\mathrm{pgcd}(a\,;\,b\,;\,c)}{\mathrm{pgcd}(a\,;\,b)\cdot\mathrm{pgcd}(b\,;\,c)\cdot\mathrm{pgcd}(c\,;\,a)}$

Elle se lit sur les exposants des facteurs premiers, où elle se réduit à l’identité $\max(x,y,z)=x+y+z-\min(x,y)-\min(y,z)-\min(z,x)+\min(x,y,z)$ , elle-même vérifiable en supposant $x\leq y\leq z$ .

Remonter l’algorithme

Reprenons l’exemple du premier article, $\mathrm{pgcd}(4\,991\,;\,1\,219)=23$ :

$\displaystyle \begin{array}{rcl} 4\,991 &=& 4\times 1\,219 + 115\\ 1\,219 &=& 10\times 115 + 69\\ 115 &=& 1\times 69 + 46\\ 69 &=& 1\times 46 + 23\\ 46 &=& 2\times 23 + 0 \end{array}$

Isolons le reste dans chaque ligne, puis remplaçons de proche en proche, en partant de l’avant-dernière :

$\displaystyle \begin{array}{rcl} 23 &=& 69 - 46\\ &=& 69 - (115 - 69) \;=\; 2\times 69 - 115\\ &=& 2(1\,219 - 10\times 115) - 115 \;=\; 2\times 1\,219 - 21\times 115\\ &=& 2\times 1\,219 - 21(4\,991 - 4\times 1\,219)\\ &=& 86\times 1\,219 - 21\times 4\,991 \end{array}$

Vérification : $86\times 1\,219=104\,834$ et $21\times 4\,991=104\,811$ , dont la différence vaut bien 23. Nous avons donc écrit le PGCD comme une combinaison des deux nombres de départ, avec des coefficients entiers.

L’identité et le théorème

Identité de Bézout. Pour tous entiers $a$ et $b$ non tous deux nuls, il existe des entiers relatifs $u$ et $v$ tels que $au+bv=\mathrm{pgcd}(a\,;\,b)$ .

La remontée ci-dessus n’est pas un tour de main propre à cet exemple : c’est la démonstration. À chaque ligne de l’algorithme, le reste s’écrit comme combinaison des deux termes précédents ; en descendant la liste, tout reste s’écrit donc comme combinaison de $a$ et de $b$ . Le dernier reste non nul — le PGCD — ne fait pas exception.

Attention au sens : l’identité affirme l’existence de $u$ et $v$ , elle ne les rend pas uniques. Le couple $(-21\,;\,86)$ convient, mais $(32\,;\,-131)$ aussi, et une infinité d’autres.

Théorème de Bézout. Deux entiers $a$ et $b$ sont premiers entre eux si, et seulement si, il existe des entiers $u$ et $v$ tels que $au+bv=1$ .

Le sens direct est le cas particulier $\mathrm{pgcd}(a\,;\,b)=1$ de l’identité. La réciproque est la partie utile : si $au+bv=1$ , alors tout diviseur commun de $a$ et $b$ divise 1, donc vaut 1. Autrement dit, une seule combinaison égale à 1 suffit à prouver la primalité entre deux nombres, sans rien connaître de leurs facteurs.

C’est aussi ce qui comble la lacune laissée à la question 6. Si $b^{\prime}$ divise $a^{\prime}k$ avec $a^{\prime}$ et $b^{\prime}$ premiers entre eux, écrivons $a^{\prime}u+b^{\prime}v=1$ , puis multiplions par $k$ :

$\displaystyle k=a^{\prime}ku+b^{\prime}kv$

Le nombre $b^{\prime}$ divise le premier terme, puisqu’il divise $a^{\prime}k$ , et le second de façon évidente. Il divise donc $k$ . Ce petit raisonnement porte un nom, et il fait l’objet de l’article suivant : c’est le théorème de Gauss.

L’équation $ax+by=c$

Toute solution entière rend $c$ multiple de $\mathrm{pgcd}(a\,;\,b)$ , puisque ce dernier divise $a$ et $b$ . Réciproquement, si $\mathrm{pgcd}(a\,;\,b)$ divise $c$ , l’identité de Bézout fournit une solution : il suffit de multiplier la combinaison par le quotient.

L’équation $ax+by=c$ admet des solutions entières si, et seulement si, $\mathrm{pgcd}(a\,;\,b)$ divise $c$ .

Prenons $4\,991x+1\,219y=92$ . Comme $92=4\times 23$ , l’équation a des solutions. En multipliant par 4 la combinaison obtenue plus haut :

$\displaystyle 4\,991\times(-84)+1\,219\times 344=92$

Le couple $(-84\,;\,344)$ est une solution particulière. Toutes les autres s’en déduisent, en divisant les coefficients par le PGCD :

$\displaystyle x=-84+53k, \qquad y=344-217k, \qquad k\in\mathbb{Z}$

puisque $1\,219/23=53$ et $4\,991/23=217$ . Pour $k=1$ , on obtient $(-31\,;\,127)$ , que le lecteur vérifiera. Que ces formules donnent toutes les solutions, et pas seulement des solutions, se démontre par le théorème de Gauss.

Note historique

Étienne Bézout (1730-1783) a laissé son nom à cette identité, qu’il établit pour les polynômes dans sa Théorie générale des équations algébriques, en 1779. Pour les entiers, le résultat lui est antérieur d’un siècle et demi : on le trouve chez Claude-Gaspard Bachet de Méziriac dès 1624, dans ses Problèmes plaisants et délectables qui se font par les nombres. L’usage français a tranché en faveur de Bézout ; l’exactitude historique pencherait plutôt pour Bachet.

L’identité de Bézout et les équations diophantiennes occupent le chapitre 3 de Mathématiques en terminales scientifiques, Tome 2 — Arithmétique : cours et exercices corrigés.

Formalis Mathematica

Rigueur et formalisme au cœur de l’apprentissage et de l’enseignement des mathématiques

L’identité de Bézout, ou comment remonter l’algorithme d’Euclide

Corrigé, partie A

Corrigé, partie B

Corrigé, partie C : la question qui piège

Remonter l’algorithme

L’identité et le théorème

L’équation $ax+by=c$

Note historique

3 réflexions sur “L’identité de Bézout, ou comment remonter l’algorithme d’Euclide”

Laisser un commentaire Annuler la réponse.

Corrigé, partie A

Corrigé, partie B

Corrigé, partie C : la question qui piège

Remonter l’algorithme

L’identité et le théorème

L’équation

Note historique

Partagez :

Similaire

3 réflexions sur “L’identité de Bézout, ou comment remonter l’algorithme d’Euclide”

Laisser un commentaire Annuler la réponse.

L’équation $ax+by=c$