174. Les coefficients de Bézout par l’algorithme d’Euclide étendu renversé

Comment calculer le $\pgcd\comma$ noté $d\comma$ des entiers $230$ et $42$ ? Comment déterminer deux entiers $a$ et $b$ tels que l’égalité $230a+42b = d$ soit vérifiée ? Pour rappel, ces nombres sont appelés coefficients de Bézout.

Utilisez des divisions euclidiennes successives

Divisez $230$ par $42.$ Vous pouvez partir de $5\times 50 = 250$ donc $5\times 42 = 5(50-8) = 250-40 = 210.$

Ce qui fournit $230 = 5\times 42 + 20.$

Vous inscrivez ce résultat dans le tableau ci-dessous.

\begin{array}{|c|c|} \hline 230 & \\ \hline 42 & 5 \\ \hline 20 & \\ \hline \end{array}

Ce tableau ayant la structure suivante :

\begin{array}{|c|c|} \hline \text{dividende} & \\ \hline \text{diviseur} & \text{quotient} \\ \hline \text{reste} & \\ \hline \end{array}

Remarquez que les divisions euclidiennes préservent le $\pgcd$

Notez $d=\pgcd(230,42).$

Alors $d\mid 230$ et $d\mid 42\comma$ donc $d\mid 230$ et $d\mid 5\times 42\comma$ donc par différence $d\mid 20.$

Comme $d\mid 42$ et $d \mid 20\comma$ vous déduisez $d\leq \pgcd(42,20).$

Notez $d’=\pgcd(42,20).$

Comme $d’\mid 42$ et $d’\mid 20\comma$ vous déduisez $d’\mid 5\times 42$ et $d’\mid 20$ donc par somme $d’\mid 230.$

Comme $d’\mid 42$ et $d’\mid 230$ vous en tirez que $d’\leq \pgcd(230,42).$

De $d\leq d’$ et $d’\leq d$ vous déduisez $d=d’$ soit $\pgcd(230,42) = \pgcd(42,20).$

Analyse : comprenez la structure des coefficients de Bézout

Supposez que vous avez trouvé deux entiers $a$ et $b$ tels que $\pgcd(42,20) = 42a+20b.$

Vous inscrivez ces nombres dans une troisième colonne supplémentaire.

\begin{array}{|c|c|c|} \hline 230 & &\\ \hline 42 & 5 &b\\ \hline 20 & & a\\ \hline \end{array}

Vous cherchez un nombre $c$ tel que $230b+42c = \pgcd(230,42) = \pgcd(42,20)$ de façon à remplir la case manquante à côté de $230.$

\begin{array}{|c|c|c|} \hline 230 & &c\\ \hline 42 & 5 &b\\ \hline 20 & & a\\ \hline \end{array}

Remarquez que :

\begin{align*} \pgcd(230,42) &= 230b+42c\\ &= (5\times 42 + 20)b+42c\\ &= 42(5b + c) +20b. \end{align*}

Or, vous avez déjà la relation $42a+20b = \pgcd(42,20) = \pgcd(230,42).$

Cela conduit à choisir $c$ pour que $5b+c = a\comma$ soit $c = a-5b.$

Synthèse : la construction des coefficients de Bézout du bas vers le haut

Supposez donc que vous avez trouvé deux entiers $a$ et $b$ tels que $42a+20b = d.$

\begin{array}{|c|c|c|} \hline 230 & &\\ \hline 42 & 5 &b\\ \hline 20 & & a\\ \hline \end{array}

Vous posez $c = a-5b.$

Alors vous obtenez successivement :

\begin{align*} d &= 42a+20b\\ &=42a+(230-5\times 42)b\\ &=42(a-5b)+230b\\ &=230b+42c. \end{align*}

Visualisez le cas général

Soient $A$ et $B$ deux nombres entiers avec $B\gt0.$

Vous effectuez la division euclidienne de $A$ par $B$ et déduisez l’existence d’un quotient $Q$ entier et d’un reste $R$ positif strictement inférieur à $B$ tels que : $A=BQ+R.$

En suivant le même raisonnement que celui opéré ci-dessus, vous avez $\pgcd(A,B) = \pgcd(B,R).$ Notez-le $D.$

\begin{array}{|c|c|c|} \hline A & & c\\ \hline B & Q &b\\ \hline R & & a\\ \hline \end{array}

Supposez que vous avez trouvé deux coefficients de Bézout tels que $aB + bR = D.$

Vous posez $\boxed{c = a-bQ.}$

Vous avez successivement :

\begin{align*} D &= aB+bR\\ &=aB+b(A-BQ)\\ &=(a-bQ)B+bA\\ &=bA + cB. \end{align*}

Ainsi, à chaque étape, vous avez les coefficients de Bézout.

Concluez sur l’exemple complet

Pour calculer le $\pgcd$ entre $230$ et $42$ et trouver deux coefficients de Bézout associés, vous effectuez la suite des divisions euclidiennes jusqu’à trouver un reste nul.

\begin{align*} 230 &= 5\times 42 + 20\\ 42 &= 2\times 20 + 2\\ 20 &= 10\times 2 +0. \end{align*}

Si bien que $d = \pgcd(230,42)=2.$

Le $\pgcd$ est l’avant-dernier nombre du bas se trouvant dans la première colonne du tableau ci-dessous.

\begin{array}{|c|c|c|} \hline 230 & \\ \hline 42 & 5 \\ \hline 20 & 2 \\ \hline 2 & 10 \\ \hline 0 & \\ \hline \end{array}

Vous placez le $1$ et le $0$ en bas du tableau comme suit pour que la relation de Bézout fournisse $d = 1\times 2 + 0\times 0.$

\begin{array}{|c|c|c|} \hline 230 & &\\ \hline 42 & 5 &\\ \hline 20 & 2 &\\ \hline 2 & 10 & 0\\ \hline 0 & & 1 \\ \hline \end{array}

Le coefficient du dessus se calcule en effectuant $1-10\times 0 = 1.$

\begin{array}{|c|c|c|} \hline 230 & & \\ \hline 42 & 5 & \\ \hline 20 & 2 & 1 \\ \hline 2 & 10 & 0\\ \hline 0 & & 1 \\ \hline \end{array}

Le coefficient du dessus se calcule en effectuant $0-2\times 1 = -2.$

\begin{array}{|c|c|c|} \hline 230 & & \\ \hline 42 & 5 & -2 \\ \hline 20 & 2 & 1 \\ \hline 2 & 10 & 0\\ \hline 0 & & 1 \\ \hline \end{array}

Le coefficient du dessus se calcule en effectuant $1-5\times (-2) = 11.$

\begin{array}{|c|c|c|} \hline 230 & & 11\\ \hline 42 & 5 & -2 \\ \hline 20 & 2 & 1 \\ \hline 2 & 10 & 0\\ \hline 0 & & 1 \\ \hline \end{array}

Conclusion : vous obtenez $\boxed{2 = \pgcd(230,42) = -2\times 230+11\times 42.}$

Cela fonctionne bien : $2\times 230 = 460$ et $11\times 42 = 462.$

Prolongement

Vous souhaitez savoir pourquoi les coefficients de Bézout existent ? Reportez-vous à une preuve directe qui se trouve dans un autre article.

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