École AVOSZ

Connectez-vous

327. Le théorème de Bézout pour les polynômes avec les conditions de degré (2/2)

Yannis TRIANTAPHYLIDES

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{\forall (A,B)\in(\K[X]\setminus \K)^2,\ (A\text{ et }B\text{ premiers entre eux})\Longleftrightarrow\left(\exists! (U,V)\in \K_{\deg B-1}[X]\times \K_{\deg A-1}[X], AU+BV=1\right).}

Dans un autre article, il a été proposé sur un exemple de trouver les coefficients des polynômes $U$ et $V$ en résolvant un système.

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

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. Ce contenu aborde le processus de façon approfondie.

L’algorithme d’Euclide pour des polynômes

Soient $A$ et $B$ deux polynômes à coefficients dans $\K\comma$ 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 : vous obtiendriez un quotient nul et un reste égal au polynôme $A.$

Vous posez $\boxed{R_0 = A}$ et $\boxed{R_1 = B.}$ Puis, pour tout entier naturel $n\comma$ vous procédez ainsi :

  • si $R_{n+1}$ n’est pas le polynôme nul et si $R_n$ et $R_{n+1}$ sont à coefficients dans $\K\comma$ 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}\lt\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\comma$ 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\comma$ 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.

Premier cas. Le polynôme $R_{n+1}$ est nul. Alors il vient $R_{n+2}=0$ et $R_{n+2}$ est bien à coefficients dans $\K.$

Second cas. Le polynôme $R_{n+1}$ n’est pas 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\comma$ le polynôme $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\comma$ 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}\lt\deg R_{n+1}. \end{align*}\right.

Ainsi, pour tout entier naturel $n$ non nul :

0\leq \deg R_{n+1}\lt\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.

Supposez qu’il existe une suite $(u_n)_{n\geq m}$ 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\comma$ 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\comma$ 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}\lt u_p.$ Comme $\alpha = u_p$ vous en tirez que $u_{p+1}\lt \alpha\comma$ ce qui contredit l’inégalité $\alpha \leq u_{p+1}$ précédemment établie.

Il n’existe donc aucune suite d’entiers naturels strictement décroissante.

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}\lt\deg R_{n}.

Du coup, la suite $(\deg R_n)_{n\geq 1}$ est une suite d’entiers naturels strictement décroissante, ce qui contredit le lemme. 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.$ Plus généralement, pour tout $n\in\llbracket 0, N-1\rrbracket$ le polynôme $R_n$ n’est pas nul.

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\comma$ 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\comma$ vous avez $R_{N-1} \mid R_{N}$ et la propriété $\mathscr{Q}(N)$ est vérifiée.
Comme $R_{N-1}$ se 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, comme $n-2\in\llbracket 0, N-2\rrbracket\comma$ vous avez :

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\comma$ 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\comma$ 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}\comma$ 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 suivante, en utilisant $\mathscr{R}(n)$ à la dernière étape :

\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 AU_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 commun 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.

Réciproquement, 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\comma$ 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é

Étudiez 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.$

Le polynôme $R_5 = -2X^2+6 = -2(X^2-3)$ n’étant pas constant, les polynômes $A$ et $B$ ne sont pas premiers entre eux : ils admettent $X^2-3$ pour diviseur commun.

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}.

Un calcul direct permet de vérifier l’égalité $AU_1+BU_0 = -2X^2+6 = R_5.$

Résumez l’ensemble dans un tableau

Sur la colonne de gauche vous faites figurer le début de la suite $(R_n)\comma$ 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 au degré de $R_i$ diminué du degré de $R_{i+1}$ qui le suit ;
  • 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. 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*} }

Démontrez que $\forall n\in\llbracket 1,N-2\rrbracket, \deg R_n\gt \deg R_{n+1}\geq 0$ lorsque $N\geq 3$

Dans cette section et les deux suivantes, l’entier $N$ est supposé supérieur ou égal à $3.$

Soit $n$ un entier appartenant à l’ensemble $\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\comma$ 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}\comma$ 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} \lt \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\comma$ 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\gt \deg R_{n+1}\geq 0.}

Note. Vous ne pouvez pas étendre ce résultat au cas $n=0\comma$ puisqu’il est possible d’avoir $\deg A = \deg B.$

Démontrez que $\forall n\in\llbracket 0,N-2\rrbracket, \deg Q_n = \deg R_n – \deg R_{n+1}$ lorsque $N\geq 3$

Soit $n$ un entier appartenant à l’ensemble $\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\comma$ le polynôme $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} \lt \deg R_{n+1}. \end{align*}

Supposez que $Q_n$ soit le polynôme nul. Alors $R_n = R_{n+2}.$ Deux cas se présentent.

Premier cas. Si $n\geq 1\comma$ alors $n\in\llbracket 1, N-2\rrbracket$ et il a été montré que $\deg R_{n+1} \lt \deg R_n.$ Donc $\deg R_{n+2} \lt \deg R_{n+1} \lt \deg R_n$ donc $\deg R_n \neq \deg R_{n+2}.$ Ainsi $R_n\neq R_{n+2}\comma$ ce qui est une contradiction.

Second cas. Si $n=0$ alors $R_0 = A = R_2$ et $R_1 = B\comma$ avec $\deg R_2 \lt \deg B.$ Cependant, par hypothèse $\deg B\leq \deg A$ ce qui entraîne $\deg R_2 \lt \deg A$ et par suite $A\neq R_2\comma$ ce qui est une 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}\lt \deg R_{n+1}\comma$ vous déduisez $\deg R_{n+2} \lt \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}.}

Démontrez que $\forall n\in\llbracket 0,N-2\rrbracket, \deg U_n = \deg R_n – \deg R_{N-2}$ lorsque $N\geq 3$

Pour tout entier $n$ de l’ensemble $\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, ce qui est possible puisque $N-3\geq 0.$

\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’ensemble $\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 :

\begin{align*} \deg Q_{n-2} &= \deg R_{n-2}-\deg R_{n-1}\\ \deg U_{n-1} &= \deg R_{n-1} – \deg R_{N-2}. \end{align*}

Ces deux degrés sont des entiers naturels : les polynômes $Q_{n-2}$ et $U_{n-1}$ ne sont donc pas nuls, et le degré de leur produit est la somme de leurs degrés. 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\comma$ alors vous avez :

\deg R_2 \lt \deg R_1 \leq \deg R_0.

Par suite $\deg R_{n} \lt \deg R_{n-2}.$

Si $n\gt2\comma$ alors $n\in \llbracket 3, N-2\rrbracket$ donc $\deg R_{n-1} \gt \deg R_{n}$ et $\deg R_{n-2} \gt \deg R_{n-1}$ d’où $\deg R_{n} \lt \deg R_{n-2}.$

Dans tous les cas vous avez :

\deg U_n \lt \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

Lorsque $N\geq 3\comma$ l’entier $N-2$ appartient à $\llbracket 1, N-2\rrbracket$ et il a été établi que $\deg R_{N-2} \gt \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\comma$ ce qui fournit $\deg U_0 \leq \deg A – 1$ et $\deg U_1 \leq \deg B – 1.$ Lorsque $N=2\comma$ ces inégalités ont été établies directement.

Les polynômes $U_0$ et $U_1$ obtenus par l’algorithme d’Euclide étendu vérifient donc, dans tous les cas, 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*} }

Si les polynômes $A$ et $B$ sont premiers entre eux, le polynôme $R_{N-1}$ est une constante $c$ non nulle. En posant $U = \frac{1}{c}U_1$ et $V = \frac{1}{c}U_0\comma$ vous obtenez les polynômes de Bézout avec la condition de degré :

\boxed{\begin{align*} &AU+BV = 1\\ &\deg U \leq \deg B – 1\\ &\deg V \leq \deg A – 1. \end{align*} }

Prolongement

Dans un autre article, il est établi que les polynômes de Bézout vérifiant la condition de degré sont uniques.

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