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|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 = \mathrm{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 le contenu rédigé dans l'article 308.
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 !