Pour rappel, $\K$ désignant un corps, le théorème de Bézout pour les polynômes avec la condition de degré se traduit formellement ainsi :
\boxed{\begin{align*} \forall (A,B)\in(\K[X]\setminus \K)^2,& (A\text{ et }B\text{ premiers entre eux})\Longleftrightarrow(\exists ! (U,V)\in \K_{\deg B-1}[X]\times \K_{\deg A-1}[X], AU+BV=1.) \end{align*}}
Dans le contenu rédigé dans l'article 326 il a été proposé sur un exemple de trouver les coefficients des polynômes $U$ et $V$ en résolvant un système.
Il sera proposé ici une approche complémentaire, basée sur l’algorithme d’Euclide, qui sera améliorée afin d’aboutir à un calcul effectif des polynômes $U$ et $V$ qui sont aussi appelés polynômes de Bézout. L’ensemble des calculs proposés repose sur ce qui est nommé algorithme d’Euclide étendu. Cet article aborde de façon approfondie le processus.
L’algorithme d’Euclide pour des polynômes
Soient $A$ et $B$ deux polynômes à coefficients dans $\K$, non constants, tels que $\boxed{\deg B\leq\deg A.}$
Note. L’idée est de commencer un algorithme en effectuant la division de $A$ par $B.$ Il ne serait pas efficace de procéder à cette division si la condition des degrés susmentionnée n’était pas vérifiée, on obtiendrait un quotient nul et un reste égal au polynôme $A.$
Vous posez $\boxed{R_0 = A}$, $\boxed{R_1 = B.}$ Puis, pour tout entier naturel $n$ :
- si $R_{n+1}$ n’est pas le polynôme nul et si $R_n$ et $R_{n+1}$ sont à coefficients dans $\K$, vous effectuez la division euclidienne dans $\K[X]$ du polynôme $R_n$ par le polynôme $R_{n+1}.$ Vous notez $Q_n\in\K[X]$ le quotient de cette division et $R_{n+2}\in\K[X]$ le reste obtenu, qui vérifie la condition $\deg R_{n+2}<\deg R_{n+1}.$
- dans les autres cas, vous posez $R_{n+2} = 0.$
Vous avez ainsi défini par récurrence une suite $(R_n)_{n\geq 0}.$
Note. Certains préfèrent « arrêter » l’algorithme dès que le polynôme nul apparaît. Afin d’élaborer une démarche théorique à partir d’une suite complète, il a été décidé d’opter pour la définition d’une suite $(R_n)_{n\in\N}.$
Démontrez que les polynômes de la suite $(R_n)_{n\geq 0}$ sont à coefficients dans $\K$
Pour tout entier naturel $n$, vous notez $\mathscr{P}(n)$ la propriété : « le polynôme $R_n$ appartient à $\K[X]$. »
Initialisation. Comme $A$ et $B$ sont à coefficients dans $\K$, vous déduisez qu’il en est de même pour les polynômes $R_0$ et $R_1.$ Du coup les propriétés $\mathscr{P}(0)$ et $\mathscr{P}(1)$ sont vérifiées.
Hérédité. Soit $n$ un entier naturel tel que les propriétés $\mathscr{P}(n)$ et $\mathscr{P}(n+1)$ soient vérifiées.
1er cas. $R_{n+1}$ est le polynôme nul. Alors il vient $R_{n+2}=0$ et $R_{n+2}$ est bien à coefficients dans $\K.$
2ème cas. $R_{n+1}$ n’est pas le polynôme nul. Par hypothèse de récurrence, les polynômes $R_n$ et $R_{n+1}$ sont à coefficients dans $\K.$ Le polynôme $R_{n+2}$ est défini comme étant le reste de la division euclidienne de $R_n$ par $R_{n+1}$ dans $\K[X].$ En notant $Q_n\in\K[X]$ le quotient associé, vous avez les égalités suivantes :
\left\{\begin{align*} &R_n = R_{n+1}Q_n + R_{n+2}\\ &R_{n+2} = R_n - R_{n+1}Q_n. \end{align*} \right.
Du coup $R_{n+2}$ est à coefficients dans $\K$ et la propriété $\mathscr{P}(n+2)$ est vérifiée.
Conclusion. Il a été montré par récurrence que :
\boxed{\forall n\in\N, R_n\in\K[X].}
Démontrez que le polynôme nul apparaît dans la suite $(R_n)_{n\geq 0}$
Raisonnez par l’absurde
Supposez que pour tout entier naturel $n$, $R_n$ ne soit pas le polynôme nul. Cela fournit :
\forall n\in\N, \deg R_n \geq 0.
Pour tout entier naturel $n$, en notant $Q_n$ le quotient de la division euclidienne de $R_n$ par $R_{n+1}$ il vient :
\forall n\in\N, \left\{\begin{align*} R_n = R_{n+1}Q_n + R_{n+2}\\ \deg R_{n+2}<\deg R_{n+1}. \end{align*}\right.
Ainsi, pour tout entier naturel $n$ non nul :
0\leq \deg R_{n+1}<\deg R_{n}.
Avant de poursuivre, un lemme sera utile.
Lemme : il n’existe pas de suite d’entiers naturels strictement décroissante
Vous raisonnez par l’absurde pour prouver ce résultat.
Soit $m$ un entier naturel.
Soit $(u_n)_{n\geq m}$ une suite d’entiers naturels strictement décroissante.
Vous considérez l’ensemble des valeurs prises par tous les termes de cette suite, en posant :
E = \{u_n, n\geq m \}.
D’une part, $E$ est une partie de $\N.$
D’autre part, $u_m\in E$ donc $E$ est non vide.
Vous déduisez que $E$ possède un minimum, qui sera noté $\alpha.$
Comme $\alpha\in E$, il existe $p\in\N$ tel que $\alpha = u_p$ avec $p\geq m.$
Or $p+1\in\N$ et $p+1\geq m$ donc $u_{p+1}\in E.$ Comme $\alpha$ est le minimum de $E$, il vient $\alpha \leq u_{p+1}.$
Cependant, par stricte décroissance de la suite $(u_n)_{n\geq m}$ vous avez aussi $u_{p+1}< u_p.$ Comme $\alpha = u_p$ vous en tirez que $u_{p+1}< \alpha$, ce qui contredit l’inégalité $\alpha \leq u_{p+1}$ précédemment établie.
Terminez le raisonnement par l’absurde pour la suite $(R_n)_{n\geq 0}$
La propriété :
\forall n\in\N, \deg R_n \geq 0.
a permis de montrer que :
\forall n\in\N^{*}, 0\leq \deg R_{n+1}<\deg R_{n}.
Du coup, la suite $(\deg R_n)_{n\geq 1}$ est une suite d’entiers naturels strictement décroissante, ce qui est absurde. Vous avez donc démontré qu’il existe un entier naturel $i$ tel que $R_i = 0.$
\boxed{\exists i\in\N, R_i = 0.}
Démontrez que $A$ et $B$ admettent un diviseur commun qui apparaît dans la suite $(R_n)_{n\geq 0}$
Introduisez un minimum
D’après le résultat précédemment établi, l’ensemble $F$ défini par :
F = \{ n\in\N, R_n = 0\}
qui contient l’entier $i$ est non vide. Comme $F$ est inclus dans $\N$ il admet un minimum noté $N$ avec $N\in\N.$
Comme $R_0$ et $R_1$ sont deux polynômes non constants, vous avez $R_0\neq 0$ et $R_1\neq 0$ donc $0\notin F$ et $1\notin F.$ Du coup, $N\geq 2.$
Comme $N-1\geq 1$ vous allez considérer le polynôme $R_{N-1}.$ Comme $N-1\in\N$ est strictement inférieur à $N$ qui est le minimum de $F$ vous déduisez $N-1\notin F$ donc $R_{N-1}\neq 0.$
Démontrez que $R_{N-1}$ est un diviseur commun des polynômes $A$ et $B$
Pour tout entier naturel $n$ compris entre $0$ et $N-2$, en notant $Q_n$ le quotient de la division euclidienne de $R_n$ par $R_{n+1}$ vous avez :
R_n = R_{n+1}Q_n + R_{n+2}.
Comme $R_N = 0$ vous déduisez :
R_{N-2} = R_{N-1}Q_{N-2}.
Ainsi $R_{N-1}$ divise $R_{N-2}.$
Vous allez démontrer par récurrence limitée et descendante que, pour tout $n\in \llbracket 0, N\rrbracket$ le polynôme $R_{N-1}$ divise le polynôme $R_n.$
Pour tout entier $n\in \llbracket 0, N\rrbracket$ vous notez $\mathscr{Q}(n)$ la propriété « $R_{N-1} \mid R_n$. »
Initialisation. Comme $R_N = 0$, vous avez $R_{N-1} \mid R_{N}$ la propriété $\mathscr{Q}(N)$ est vérifiée.
Comme $R_{N-1}$ divise lui-même, la propriété $\mathscr{Q}(N-1)$ est encore vérifiée.
Hérédité. Soit $n\in\llbracket 2, N\rrbracket.$ Supposez que les propriétés $\mathscr{Q}(n)$ et $\mathscr{Q}(n-1)$ soient vérifiées.
Par hypothèse de récurrence :
\begin{align*} &R_{N-1} \mid R_{n-1}\\ &R_{N-1} \mid R_{n}. \end{align*}
Or :
R_{n-2} = R_{n-1}Q_{n-2} + R_{n}.
Ainsi :
R_{N-1} \mid R_{n-2}.
La propriété $\mathscr{Q}(n-2)$ est vérifiée.
Conclusion. Par récurrence limitée et descendante, les propriétés $\mathscr{Q}(0)$ et $\mathscr{Q}(1)$ sont vérifiées, ce qui prouve que $R_{N-1}$ est un diviseur commun des polynômes $A$ et $B.$
En définitive, si $N$ est le plus petit entier naturel tel que $R_N = 0$, alors $N\geq 2$ et le polynôme $R_{N-1}$ est un diviseur commun des polynômes $A$ et $B.$
La méthode de remontée dans l’algorithme d’Euclide fournit les polynômes de Bézout recherchés
Par définition de l’entier $N$, pour tout entier $n\in\llbracket 0, N-1\rrbracket$ le polynôme $R_n$ est non nul. Pour tout entier $n\in\llbracket 0, N-2\rrbracket$ vous notez $Q_n$ le quotient de la division euclidienne de $R_n$ par $R_{n+1}$, ce qui fournit :
R_n =R_{n+1}Q_n+R_{n+2}.
Grâce à tous les quotients, vous définissez une suite finie $(U_n)_{n\in\llbracket 0, N\rrbracket}$ de polynômes de la façon suivante. Vous posez :
\boxed{\left\{\begin{align*} &U_N = 1\\ &U_{N-1} = 0\\ &\forall n\in\llbracket 0, N-2\rrbracket, U_n = U_{n+2}-Q_nU_{n+1}. \end{align*} \right. }
C’est la définition de cette suite qui constitue la méthode de remontée.
Note. Cette façon de procéder est aussi attribuée à Aryabhata, mathématicien et astronome.
Pour tout entier $n\in \llbracket 0, N-1\rrbracket$ vous notez $\mathscr{R}(n)$ la propriété « $R_nU_{n+1}+R_{n+1}U_n = R_{N-1}$ » et vous allez de nouveau utiliser une récurrence descendante.
Initialisation. Vous choisissez $n = N-1$ et vous avez :
\begin{align*} R_{N-1}U_{N}+R_{N}U_{N-1} &= R_{N-1}\times 1 + 0\times 0\\ &=R_{N-1}. \end{align*}
Vous en déduisez que la propriété $\mathscr{R}(N-1)$ est vérifiée.
Hérédité. Soit $n\in \llbracket 1, N-1\rrbracket$ tel que $\mathscr{R}(n)$ soit vérifiée.
Comme $n-1\in\llbracket 0, N-2\rrbracket$ vous avez :
\begin{align*} &U_{n-1} = U_{n+1}-Q_{n-1}U_{n}\\ &R_{n-1} =R_{n}Q_{n-1}+R_{n+1}. \end{align*}
Vous calculez l’expression :
\begin{align*} R_{n-1}U_{n}+R_{n}U_{n-1} &= R_{n-1}U_{n}+R_{n}(U_{n+1}-Q_{n-1}U_{n})\\ &=(R_{n-1}-Q_{n-1}R_n)U_n+R_nU_{n+1}\\ &=R_{n+1}U_n+R_nU_{n+1}\\ &=R_{N-1}. \end{align*}
Vous en déduisez que la propriété $\mathscr{R}(n-1)$ est vérifiée.
Conclusion. Par récurrence limitée, il est prouvé que la propriété $\mathscr{R}(0)$ est vérifiée. Autrement dit, $R_0U_{1}+R_{1}U_0 = R_{N-1}$ soit :
\boxed{R_{N-1} = AU_1+BU_0.}
Démontrez que tout diviseur commun des polynômes $A$ et $B$ est un diviseur de $R_{N-1}$
Soit $D\in\K[X]$ un diviseur commun des polynômes $A$ et $B.$ Alors $D\mid A$ puis $D\mid U_1.$
De même, $D\mid B$ donc $D\mid BU_0.$ Par somme il vient $D\mid AU_1+BU_0$ donc $D\mid R_{N-1}.$
Une condition nécessaire et suffisante pour savoir si $A$ et $B$ sont premiers entre eux
Supposez que $A$ et $B$ ne soient pas premiers entre eux. Alors ils admettent un diviseur non constant noté $D.$ Il a été vu que $D\mid R_{N-1}.$ Comme $R_{N-1}$ n’est pas le polynôme nul, vous déduisez que $\deg R_{N-1}\geq \deg D.$ Or $\deg D \geq 1$ donc $R_{N-1}$ n’est pas constant.
Supposez que le polynôme $R_{N-1}$ ne soit pas constant. Comme $R_{N-1}$ est un diviseur commun non constant des polynômes $A$ et $B$, les polynômes $A$ et $B$ ne sont pas premiers entre eux.
Pour résumer :
\boxed{A\text{ et }B\text{ sont premiers entre eux}\Longleftrightarrow R_{N-1}\text{ est constant}.}
Les polynômes $U_0$ et $U_1$ satisfont les conditions de degré
Etudiez un exemple dans $\Q[X]$
Ce paragraphe est un aparté. Vous posez :
\begin{align*} A(X) &= X^6+X^5+X^4-X^3-14X^2-6X+6\\ B(X) &= X^6-X^5+X^4+X^3-14X^2+6X+6. \end{align*}
Calculez les quotients et les restes
Vous allez calculer successivement les premiers termes de la suite $(R_n)_{n\in\N}$ jusqu’à trouver $N$ qui est le plus petit entier naturel pour lequel $R_N = 0.$
Pour le moment :
\begin{align*} R_0(X) &= X^6+X^5+X^4-X^3-14X^2-6X+6\\ R_1(X) &= X^6-X^5+X^4+X^3-14X^2+6X+6. \end{align*}
Vous effectuez la division euclidienne du polynôme $R_0$ par le polynôme $R_1.$
\begin{array}{lllllll | l} X^6&+X^5&+X^4&-X^3&-14X^2&-6X&+6 & X^6-X^5+X^4+X^3-14X^2+6X+6\\ \hline X^6&-X^5&+X^4&+X^3&-14X^2&+6X&+6 & 1\\ &\hphantom{+}2X^5&&-2X^3&&-12X \end{array}
Vous obtenez :
\begin{align*} &Q_0(X)=1\\ &R_2(X)=2X^5-2X^3-12X. \end{align*}
Vous effectuez la division euclidienne du polynôme $R_1$ par le polynôme $R_2.$
\begin{array}{lllllll | l} X^6&-X^5&+X^4&+X^3&-14X^2&+6X&+6 & 2X^5-2X^3-12X\\ \hline X^6&&-X^4&&-6X^2 &&& \frac{X}{2}-\frac{1}{2}\\ &-X^5&+2X^4&+X^3&-8X^2&+6X&+6\\ \hline &-X^5&&+X^3&&+6X\\ &&2X^4&&-8X^2&&+6 \end{array}
Vous avez :
\begin{align*} &Q_1(X)=\frac{X-1}{2}\\ &R_3(X)=2X^4-8X^2+6. \end{align*}
Vous effectuez la division euclidienne du polynôme $R_2$ par le polynôme $R_3.$
\begin{array}{lll | l} 2X^5&-2X^3&-12X & 2X^4-8X^2+6 \\ \hline 2X^5&-8X^3&+6X & X\\ &\hphantom{-}6X^3&-18X \end{array}
Vous obtenez :
\begin{align*} &Q_2(X)=X\\ &R_4(X)=6X^3-18X. \end{align*}
Vous effectuez la division euclidienne du polynôme $R_3$ par le polynôme $R_4.$
\begin{array}{ll | l} 2X^4&-8X^2+6 & 6X^3-18X \\ \hline 2X^4&-6X^2&\frac{X}{3}\\ &-2X^2+6 \end{array}
Ainsi :
\begin{align*} &Q_3(X)=\frac{X}{3}\\ &R_5(X)=-2X^2+6. \end{align*}
Vous effectuez la division euclidienne du polynôme $R_4$ par le polynôme $R_5.$
\begin{array}{ l | l} 6X^3-18X & -2X^2+6\\ \hline 6X^3-18X& -3X\\ 0 \end{array}
Finalement :
\begin{align*} &Q_4(X)=-3X\\ &R_6(X)=0. \end{align*}
De ce qui précède, vous déduisez que $N = 6.$
Calculez les polynômes de la suite $(U_n)_{0\leq n\leq 6}$
Vous avez déjà :
\begin{align*} &U_6(X) = 1\\ &U_5(X) = 0. \end{align*}
Vous procédez au calcul de $U_4.$
\begin{align*} U_4(X) &= U_{6}(X)-Q_4(X)U_{5}(X)\\ &=1-(-3X)\times 0. \end{align*}
Du coup :
U_4(X)=1.
Vous procédez au calcul de $U_3.$
\begin{align*} U_3(X) &= U_{5}(X)-Q_3(X)U_{4}(X)\\ &=0-\frac{X}{3}\times 1. \end{align*}
Ainsi :
U_3(X)=-\frac{X}{3}.
Vous procédez au calcul de $U_2.$
\begin{align*} U_2(X) &= U_{4}(X)-Q_2(X)U_{3}(X)\\ &=1-X\times \frac{-X}{3}\\ &=1+\frac{X^2}{3}. \end{align*}
Donc :
U_2(X)=\frac{X^2+3}{3}.
Vous procédez au calcul de $U_1.$
\begin{align*} U_1(X) &= U_{3}(X)-Q_1(X)U_{2}(X)\\ &=-\frac{X}{3}-\frac{X-1}{2}\times\frac{X^2+3}{3}\\ &=\frac{-2X}{6}+\frac{(-X+1)(X^2+3)}{6}\\ &=\frac{-2X-X^3-3X+X^2+3}{6}. \end{align*}
Vous obtenez :
U_1(X) = \frac{-X^3+X^2-5X+3}{6}.
Vous procédez au calcul de $U_0.$
\begin{align*} U_0(X) &= U_{2}(X)-Q_0(X)U_{1}(X)\\ &=\frac{X^2+3}{3}- 1\times \frac{-X^3+X^2-5X+3}{6} \\ &=\frac{2X^2+6}{6}+\frac{X^3-X^2+5X-3}{6}. \end{align*}
Finalement :
U_0(X) = \frac{X^3+X^2+5X+3}{6}.
Résumez l’ensemble dans un tableau
Sur la colonne de gauche vous faites figurer le début de la suite $(R_n)$, sur celle du milieu vous mettez le début de la suite $(Q_n)$ et enfin sur la colonne de droite vous mettez la suite $(U_n).$
\begin{array}{ l | l | l} R_0(X)=X^6+X^5+X^4-X^3-14X^2-6X+6 & & U_0(X)=\frac{X^3+X^2+5X+3}{6}\\ \hline R_1(X)=X^6-X^5+X^4+X^3-14X^2+6X+6 & Q_0(X)=1 & U_1(X)=\frac{-X^3+X^2-5X+3}{6}\\ \hline R_2(X)=2X^5-2X^3-12X & Q_1(X)=\frac{X-1}{2} & U_2(X)=\frac{X^2+3}{3}\\ \hline R_3(X)=2X^4-8X^2+6 & Q_2(X)=X& U_3(X)=-\frac{X}{3}\\ \hline R_4(X)=6X^3-18X & Q_3(X)=\frac{X}{3}& U_4(X)=1\\ \hline R_5(X)=-2X^2+6 & Q_4(X)=-3X & U_5(X)=0\\ \hline R_6(X)=0 & & U_6(X)=1 \end{array}
Maintenant vous formez le même tableau mais avec les degrés des polynômes.
\begin{array}{ l | l | l} \deg R_0 = 6 & & \deg U_0 = 3\\ \hline \deg R_1 = 6 & \deg Q_0=0 & \deg U_1=3\\ \hline \deg R_2 = 5 & \deg Q_1=1 & \deg U_2=2\\ \hline \deg R_3 = 4& \deg Q_2=1& \deg U_3=1\\ \hline \deg R_4= 3 & \deg Q_3=1& \deg U_4=0\\ \hline \deg R_5 = 2 & \deg Q_4=1 & \deg U_5=-\infty\\ \hline \deg R_6 = -\infty & & \deg U_6=0 \end{array}
L’étude de cet exemple met en évidence les propriétés suivantes :
- Pour tout $i\in\llbracket 1,4\rrbracket$ le degré de $R_i$ est strictement supérieur à celui de $R_{i+1}$ et $R_{i+1}$ n’est pas le polynôme nul.
- Pour tout $i\in\llbracket 0,4\rrbracket$ le degré de $Q_i$ est égal à $\deg R_i – \deg R_{i+1}.$
- Pour tout $i\in\llbracket 0,4\rrbracket$ le degré de $U_i$ est égal à $\deg R_i – \deg R_4.$
Vous pouvez maintenant aborder la démonstration finale, à savoir montrer que $U_0$ est un polynôme qui a un degré strictement inférieur à celui de $A$ et $U_1$ un polynôme qui a un degré strictement inférieur à celui de $B.$
Le cas où $N=2$
D’une part :
\begin{align*} &R_0=A\\ &R_1=B\\ &R_2=0. \end{align*}
D’autre part :
\begin{align*} U_2&= 1\\ U_1&= 0\\ U_0 &= U_2-Q_0U_1\\ &=1-Q_0\times 0\\ &=1. \end{align*}
Les polynômes $U_0$ et $U_1$ sont constants. D’autre part, comme $A$ et $B$ ne sont pas constants, il en résulte que :
\boxed{\begin{align*} \deg U_0 &\leq \deg A - 1\\ \deg U_1 &\leq \deg B - 1. \end{align*} }
Cas où $N\geq 3$ : démontrez que $\forall n\in\llbracket 1,N-2\rrbracket, \deg R_n> \deg R_{n+1}\geq 0$
Soit $n$ un entier appartenant à l’intervalle $\llbracket 1, N-2\rrbracket.$
L’entier $n$ est positif et il est inférieur ou égal à $N-1.$ Par définition de l’entier $N$, le polynôme $R_{n}$ n’est pas le polynôme nul.
L’entier $n-1$ est positif ou nul. En effectuant la division euclidienne du polynôme $R_{n-1}$ par le polynôme $R_{n}$, vous obtenez un quotient $Q_{n-1}$ et un reste $R_{n+1}$ avec :
\begin{align*} &R_{n-1} = Q_{n-1}R_{n}+R_{n+1}\\ &\deg R_{n+1} < \deg R_{n}. \end{align*}
Notez que $n+1$ est un entier positif inférieur ou égal à $N-1.$ Toujours par la définition de $N$, le polynôme $R_{n+1}$ n’est pas le polynôme nul et $\deg R_{n+1}\geq 0.$
Il vient d’être établi que :
\boxed{\forall n\in\llbracket 1,N-2\rrbracket, \deg R_n> \deg R_{n+1}\geq 0.}
Note. On ne peut généraliser avec $n=0$ puisqu’il est possible d’avoir $\deg A = \deg B.$
Cas où $N\geq 3$ : Démontrez que $\forall n\in\llbracket 0,N-2\rrbracket, \deg Q_n = \deg R_n – \deg R_{n+1}$
Soit $n$ un entier appartenant à l’intervalle $\llbracket 0, N-2\rrbracket.$ L’entier $n+1$ est alors positif et inférieur ou égal à $N-1.$ Par définition de l’entier $N$, $R_{n+1}$ n’est pas le polynôme nul.
Vous effectuez la division euclidienne de $R_n$ par $R_{n+1}$ et notez $Q_n$ le quotient associé. Vous avez :
\begin{align*} &R_n = Q_nR_{n+1}+R_{n+2}\\ &\deg R_{n+2} < \deg R_{n+1}. \end{align*}
Si $Q_n$ est le polynôme nul, alors $R_n = R_{n+2}.$ Deux cas se présentent.
Premier cas. Si $n\geq 1$, alors $n\in\llbracket 1, N-2\rrbracket$ et il a été montré que $\deg R_{n+1} < \deg R_n.$ Donc $\deg R_{n+2} < \deg R_{n+1} < \deg R_n$ donc $\deg R_n \neq \deg R_{n+2}.$ Ainsi $R_n\neq R_{n+2}.$ Contradiction.
Second cas. Si $n=0$ alors $R_0 = A = R_2$ et $R_1 = B$, avec $\deg R_2 < \deg B.$ Cependant, par hypothèse $\deg B\leq \deg A$ ce qui entraîne $\deg R_2 < \deg A$ et par suite $A\neq R_2.$ Contradiction.
Donc $Q_n$ n’est pas le polynôme nul. Or, $R_{n+1}$ n’est pas le polynôme nul non plus. Donc $Q_nR_{n+1}$ n’est pas le polynôme nul et $\deg Q_nR_{n+1} = \deg Q_n+\deg R_{n+1}.$
Comme $\deg R_{n+2}< \deg R_{n+1}$, vous déduisez $\deg R_{n+2} < \deg Q_nR_{n+1}$ et par suite :
\begin{align*} \deg R_n &= \deg (Q_nR_{n+1}+R_{n+2}) \\ &= \deg Q_nR_{n+1}\\ &= \deg Q_n+\deg R_{n+1}. \end{align*}
Vous avez montré que :
\boxed{\forall n\in\llbracket 0,N-2\rrbracket, \deg Q_n = \deg R_n - \deg R_{n+1}.}
Cas où $N\geq 3$ : démontrez que $\forall n\in\llbracket 0,N-2\rrbracket, \deg U_n = \deg R_n – \deg R_{N-2}$
Pour tout entier $n$ de l’intervalle $\llbracket 0,N-2\rrbracket$ vous notez $\mathscr{S}(n)$ la propriété : « $\deg U_n = \deg R_n – \deg R_{N-2}.$ »
Initialisation. La suite $(U_n)_{0\leq n\leq N}$ est définie par :
\boxed{\left\{\begin{align*} &U_N = 1\\ &U_{N-1} = 0\\ &\forall n\in\llbracket 0, N-2\rrbracket, U_n = U_{n+2}-Q_nU_{n+1}. \end{align*} \right. }
Il vient :
\begin{align*} U_{N-2} &= U_N-Q_{N-2}U_{N-1}\\ &= 1 - Q_{N-2}\times 0\\ &=1. \end{align*}
Ainsi $\deg U_{N-2} = 0 = \deg R_{N-2} – \deg R_{N-2}.$ Donc la propriété $\mathscr{S}(N-2)$ est vérifiée.
Vous continuez.
\begin{align*} U_{N-3} &= U_{N-1}-Q_{N-3}U_{N-2}\\ &= 0 - Q_{N-3}\times 1\\ &=-Q_{N-3}. \end{align*}
Il vient :
\begin{align*} \deg U_{N-3} &= \deg Q_{N-3}\\ &= \deg R_{N-3} - \deg R_{N-2}. \end{align*}
Donc la propriété $\mathscr{S}(N-3)$ est vérifiée.
Hérédité. Soit $n$ un entier appartenant à l’intervalle $\llbracket 2,N-2\rrbracket$ tel que les propriétés $\mathscr{S}(n)$ et $\mathscr{S}(n-1)$ soient vérifiées.
Vous avez :
U_{n-2} = U_n - Q_{n-2}U_{n-1}.
Or :
\deg Q_{n-2} = \deg R_{n-2}-\deg R_{n-1}\\ \deg U_{n-1} = \deg R_{n-1} - \deg R_{N-2}.
Du coup :
\deg Q_{n-2}U_{n-1} = \deg R_{n-2}-\deg R_{N-2}.
Mais :
\deg U_n = \deg R_n - \deg R_{N-2}.
Si $n=2$, alors vous avez :
\deg R_2 < \deg R_1 \leq \deg R_0.
Par suite $\deg R_{n} < \deg R_{n-2}.$
Si $n>2$, alors $n\in \llbracket 3, N-2\rrbracket$ donc $\deg R_{n-1} > \deg R_{n}$ et $\deg R_{n-2} > \deg R_{n-1}$ d’où $\deg R_{n} < \deg R_{n-2}.$
Dans tous les cas vous avez :
\deg U_n < \deg Q_{n-2}U_{n-1}.
Vous déduisez :
\begin{align*} \deg U_{n-2} &= \deg (U_n - Q_{n-2}U_{n-1})\\ &= \deg Q_{n-2}U_{n-1}\\ &=\deg R_{n-2}-\deg R_{N-2}. \end{align*}
Donc la propriété $\mathscr{S}(n-2)$ est vérifiée.
Conclusion. Par récurrence limitée et descendante, les propriétés $\mathscr{S}(0)$ et $\mathscr{S}(1)$ sont vérifiées.
\boxed{\begin{align*} \deg U_0 &= \deg R_0 - \deg R_{N-2} = \deg A - \deg R_{N-2} \\ \deg U_1 &= \deg R_1 - \deg R_{N-2} = \deg B - \deg R_{N-2}. \end{align*} }
Concluez
ll a été établi que $\deg R_{N-2} > \deg R_{N-1}.$ Or le polynôme $R_{N-1}$ n’est pas le polynôme nul donc $\deg R_{N-1}\geq 0.$ Du coup, $\deg R_{N-2}\geq 1.$
Les polynômes $U_0$ et $U_1$ obtenus par l’algorithme d’Euclide étendu sont les polynômes de Bézout. Ils vérifient les propriétés suivantes :
\boxed{\begin{align*} &R_{N-1} = AU_1+BU_0\\ &\deg U_0 \leq \deg A - 1\\ &\deg U_1 \leq \deg B - 1. \end{align*} }
Prolongement
Dans le contenu rédigé dans l'article 326 il est établi que les polynômes de Bézout vérifiant la condition de degré sont uniques.
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 !