Votre navigateur n'accepte pas le Javascript.La navigation sur ce site risque de ne pas fonctionner correctement.

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

Comment allez-vous calculer le PGCD noté $d$ de $230$ et de $42$ ? Comment allez-vous déterminer deux entiers $a$ et $b$ tels que $230a+46b = d$ ? 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=\mathrm{PGCD}(230,42).$

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

Comme $d\mid 42$ et $d \mid 20$, vous déduisez $d\leq \mathrm{PGCD}(42,20).$

Notez $d’=\mathrm{PGCD}(42,20).$

Comme $d’\mid 42$ et $d’\mid 20$, vous déduisez $d’\vert 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 \mathrm{PGCD}(230,42).$

De $d\leq d’$ et $d’\leq d$ vous déduisez $d=d’$ soit $\mathrm{PGCD}(230,42) = \mathrm{PGCD}(42,20).$

Analyse : comprenez la structure des coefficients de Bézout

Supposez que vous avez trouvé deux entiers $a$ et $b$ tels que $\mathrm{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 = \mathrm{PGCD}(230,43) = \mathrm{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*}
\mathrm{PGCD}(230,43) &= 230b+42c\\
&= (5\times 42 + 20)b+42c\\
&= 42(5b + c) +20b.
\end{align*}$

Or, vous avez déjà la relation $42a+20b = \mathrm{PGCD}(42,20) = \mathrm{PGCD}(230,43).$

Cela conduit à choisir $c$ pour que $5b+c = a$, 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 réels $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>0.$

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 $\mathrm{PGCD}(A,B) = \mathrm{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 = \mathrm{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|}
\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|}
\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|}
\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|}
\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|}
\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 = \mathrm{PGCD}(230,42) = -2\times 230+11\times 42.}$

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

Partagez !

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.

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 !