308. Le théorème de Bézout sans l’algorithme d’Euclide

L’objectif de ce contenu est de construire une preuve directe du résultat suivant. Étant donnés deux nombres entiers relatifs $a$ et $b$ non simultanément nuls, il existe deux nombres entiers relatifs $u$ et $v\comma$ appelés coefficients de Bézout, tels que :

\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,\pgcd(a,b) =au+bv.}

Note. Les nombres $u$ et $v$ ne sont pas déterminés de façon unique 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 à un autre article qui traite cette question.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 174.

Pour rappel, quels que soient les entiers $a$ et $b$ non simultanément nuls, le $\pgcd$ de $a$ et de $b\comma$ noté $\pgcd(a,b)\comma$ 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)\}, \pgcd(a,b) = \max \{n\in\NN, n\mid a \text{ et } n\mid b\}.

Note. Le $\pgcd$ de deux nombres nuls n’est pas défini, puisque tout entier naturel non nul divise zéro : c’est la raison pour laquelle vous supposez $(a,b)\neq (0,0).$

Dans toute la suite, $a$ et $b$ désignent deux entiers fixés, non simultanément nuls.

Étudiez 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 strictement positif, en prenant $u=1$ et $v=0$ vous constatez que $au+bv\in\NN$ donc $au+bv\in A.$

Si $a$ est strictement 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\comma$ puisque $(a,b)\neq (0,0).$ De même, si $b$ est strictement positif, alors en posant $u=0$ et $v=1\comma$ vous avez $au+bv\in\NN$ donc $au+bv\in A.$ Si $b$ est strictement 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 $\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\comma$ 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\comma$ avec $r\gt0$ vous déduisez que $r\in A.$ Or $r\lt k$ et $k$ est le plus petit élément de $A\comma$ 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\comma$ 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\comma$ avec $r’\gt0$ vous déduisez que $r’\in A.$ Or $r’\lt k$ et $k$ est le plus petit élément de $A\comma$ 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\comma$ par définition du $\pgcd$ vous déduisez $\boxed{k\leq \pgcd(a,b).}$

Le $\pgcd$ de $a$ et de $b$ est inférieur ou égal à $k$

Posez $m = \pgcd(a,b).$ Alors $m$ est un nombre entier naturel non nul tel que $m\mid a$ et $m\mid b.$

Il existe donc 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{\pgcd(a,b)\leq k.}$

Concluez

Il vient d’être démontré que $k = \pgcd(a,b)$ et que :

\pgcd(a,b)=\min \{n\in\NN, \exists(p,q)\in\Z^2, n=ap+bq\}.

En particulier :

\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,\pgcd(a,b) =au+bv.}