L’objectif de cet article est de construire une preuve directe du résultat suivant. Etant donnés deux nombres entiers relatifs $a$ et $b$ non simultanément nuls, il existe deux nombres entiers relatifs $u$ et $v$, appelés coefficients de Bézout, tels que :
\mathrm{PGCD}(a,b) = au+bv.Ce résultat sera appelé théorème de Bézout. Très souvent, ce théorème est démontré à partir de l’algorithme d’Euclide. Une approche différente est proposée ici.
De façon formelle, ce théorème s’écrit ainsi :
\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \exists(u,v)\in\Z^2,\mathrm{PGCD}(a,b) =au+bv.}Note. En aucun cas les nombres $u$ et $v$ ne sont uniquement déterminés par $a$ et $b.$ Seule l’existence de ces deux nombres importe dans le théorème susmentionné.
Note. Vous souhaitez calculer effectivement des coefficients de Bézout ? Reportez-vous au contenu rédigé dans l'article 174.
Vous vous rappelez que, quels que soient les entiers $a$ et $b$ non simultanément nuls, le $\mathrm{PGCD}$ de $a$ et de $b$, noté $\mathrm{PGCD}(a,b)$ désigne le maximum de l’ensemble suivant :
\{n\in\NN, n\mid a \text{ et } n\mid b\}.Ainsi :
\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \mathrm{PGCD}(a,b) = \max \{n\in\NN, n\mid a \text{ et } n\mid b\}.Note. Le $\mathrm{PGCD}$ de deux nombres nuls n’est pas défini, c’est la raison pour laquelle on suppose $(a,b)\neq (0,0).$
Dans toute la suite, $a$ et $b$ désignent deux entiers fixés, non simultanément nuls.
Etudiez un ensemble
Soit $A$ l’ensemble suivant :
A = \{n\in\NN, \exists(u,v)\in\Z^2, n=au+bv\}.Vous allez dans un premier temps justifier que $A$ est non vide.
Supposez que $a$ soit non nul. Si $a$ est positif, en prenant $u=1$ et $v=0$ vous constatez que $au+bv\in\NN$ donc $au+bv\in A.$
Si $a$ est négatif, vous prenez $u=-1$ et $v=0.$ Vous constatez encore que $au+bv\in\NN$ donc $au+bv\in A.$
Si $a$ est nul, vous déduisez que $b\neq 0.$ Cela provient du fait que $(a,b)\neq (0,0).$ De même, si $b$ est positif, alors en posant $u=0$ et $v=1$, vous avez $au+bv\in\NN$ donc $au+bv\in A.$ Si $b$ est négatif, alors vous posez $u=0$ et $v=-1$ et il vient $au+bv\in\NN$ donc $au+bv\in A.$
Comme $A$ est une partie de $\N$ qui est non vide, elle admet un plus petit élément, qui sera noté $k.$
Justifiez que $k$ est le $\mathrm{PGCD}$ des nombres $a$ et $b$
Comme $k\in A$ vous déduisez que $k\in\NN$ et qu’il existe un couple $(u,v)\in\Z^2$ tel que $k=au+bv.$
Le nombre $k$ est un diviseur commun à $a$ et à $b$
Vous effectuez la division euclidienne de $a$ par $k.$ Il existe $q\in\Z$ et $r\in\llbracket 0, k-1\rrbracket$ tels que :
a = kq+r.
Si $r$ est différent de $0$, alors vous avez :
\begin{align*}
r &= a-kq\\
&=a-(au+bv)q\\
&=a(1-uq)+b(-vq).
\end{align*}Comme $(1-uq, -vq)\in\Z^2$, avec $r>0$ vous déduisez que $r\in A.$ Or $r< k$ et $k$ est le plus petit élément de $A$ ce qui est impossible.
Donc $r = 0$ et par suite $a = kq$ donc $k\mid a.$
De même, vous effectuez la division euclidienne de $b$ par $k.$ Il existe $q’\in\Z$ et $r’\in\llbracket 0, k-1\rrbracket$ tels que :
b = kq'+r'.
Si $r’$ est différent de $0$, alors vous avez :
\begin{align*}
r' &= b-kq'\\
&=b-(au+bv)q'\\
&=a(-uq')+b(1-vq').
\end{align*}Comme $(-uq’, 1-vq’)\in\Z^2$, avec $r’>0$ vous déduisez que $r’\in A.$ Or $r'< k$ et $k$ est le plus petit élément de $A$ ce qui est impossible.
Donc $r’ = 0$ et par suite $b = kq’$ donc $k\mid b.$
Comme $k\in\NN$ avec $k\mid a$ et $k\mid b$ vous déduisez $\boxed{k\leq \mathrm{PGCD}(a,b).}$
Le $\mathrm{PGCD}$ de $a$ et de $b$ est inférieur à $k$
Posez $m = \mathrm{PGCD}(a,b).$ Alors $m$ est nombre entier naturel non nul tel que $m\mid a $ et $m\mid b.$
Alors il existe deux entiers relatifs $a’$ et $b’$ tels que :
\begin{align*}
a &= ma'\\
b &= mb'.
\end{align*}Or, la relation $k =au+bv$ fournit :
\begin{align*}
k &= ma'u+mb'v\\
&= m(a'u+b'v).
\end{align*}
La stricte positivité de $k$ et de $m$ fournit $a’u+b’v \in\NN.$
Cela s’écrit :
\begin{align*}
a'u+b'v &\geq 1\\
m(a'u+b'v) &\geq m\\
k &\geq m.
\end{align*}Ainsi, $\boxed{\mathrm{PGCD}(a,b)\leq k.}$
Concluez
Il vient d’être démontré que $k = \mathrm{PGCD}(a,b)$ et que :
\mathrm{PGCD }(a,b)=\min \{n\in\NN, \exists(p,q)\in\Z^2, n=ap+bq\}.En particulier :
\mathrm{PGCD}(a,b)\in\{n\in\NN, \exists(p,q)\in\Z^2, n=ap+bq\}.Le théorème de Bézout est bien démontré.
\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \exists(u,v)\in\Z^2,\mathrm{PGCD}(a,b) =au+bv.}Partagez maintenant !
Aidez vos amis à découvrir cet article et à mieux comprendre le sujet.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !