Division euclidienne polynomiale

 Cette article fait suite aux articles suivants et reprend leurs notations : 

• [P1] Polynômes et fonctions polynomiales
• [P2] Polynômes : degré, racines, division par $X-a$.

Soit $P$ et $Q$ deux polynômes à coefficients réels, c'est-à-dire des éléments de $\mathbb R[X]$.

On veut diviser $P$ par $Q$, c'est-à-dire trouver un polynôme $B$ et un polynôme $R$ tels que :

• (E1) $P=QF+R$
• (E2) $\deg R< \deg Q$

Commençons par faire quelques observations à partir d'un exemple.

Un exemple

Soit $P=X^3-2X$ et $Q=3X^2+1$.

Supposons qu'il existe $H$ et $R$ vérifiant les conditions (E1) et (E2). 

Le polynôme $H$ que l'on cherche doit vérifier : $\deg(P)=\deg(QH+R)=\deg(QH)=\deg(H)+\deg(Q)$ car $\deg(R)<\deg(Q)<\deg(QH)$.

Donc $\deg H = \deg(P)-\deg(Q)=3-2=1$. On a donc $H=h_1X+h_0$.

On utilise la définition de coefficient dominant donnée dans [P2].

Les coefficients dominants de $Q$ et de $X-2$ sont respectivement $\ell(Q)=3$ et $\ell(H)=h_1$. 

D'après la propriété 1 et la propriété 2 de l'article [P1], $\ell(P)=\ell(QH+R)=\ell(QH)=\ell(Q)\ell(H)=3h_1$. Comme $\ell(P)=1$, on a nécessairement $h_1=\frac 1 3$.

On a donc $H=\frac 1 3 X +h_0$. 

Remarquons que $P-Q\frac 1 3 X  = P -QH-Qh_0=R-Qh_0$ est un polynôme de degré strictement inférieur à $\deg P$. Nous retiendrons cette idée pour le cas général.

Nous avons $P-\frac 1 3 X Q =R-Qh_0$ soit $X^3-2X-\frac 1 3 X(3X^2+1)=-2X-\frac 1 3X=-\frac 7 3 X=R-Qh_0$. 

En regardant les degrés des polynômes dans la dernière égalité, on en déduit que $\deg(R-Qh_0)=1$. 

On a nécessairement $h_0=0$ car si $h_0\neq 0$, on aurait $\deg Qh_0=2$, et comme $\deg R<2$, cela impliquerait $\deg(R-Qh_0)=\deg(Qh_0)=2$. 

Ainsi on a $H=\frac 1 3X$ et $R=P-\frac 1 3 X =-\frac 7 3 X$.

Méthode générale

De l'exemple nous avons retenu une idée.

Propriété 1. 

Soit $P$ et $Q$ deux polynômes de degrés respectifs $n$ et $m$, avec $m\leq n$. 

Alors $P-\frac{\ell(P)}{\ell(Q)}X^{n-m}Q$ est de degré strictement inférieur à $\deg P$.

Preuve. On note $P=a_nX^n+a_{n-1}X^{n-1}+\ldots+a_0$ et $Q=b_mX^m+\ldots+b_0$. 

On a $$\frac{\ell(P)}{\ell(Q)}X^{n-m}Q=\frac{a_n}{b_m}X^{n-m}\left(b_mX^m+b_{m-1}X^{m-1}\ldots+b_0\right)=a_nX^n+\frac{a_n}{b_m}X^{n-1}+\ldots+\frac{a_n}{b_m}b_0X^{n-m}$$

d'où 

$$P-\frac{\ell(P)}{\ell(Q)}X^{n-m}Q=a_nX^n+a_{n-1}X^{n-1}\ldots+a_0-\left(a_nX^n+\frac{a_n}{b_m}b_{m-1}X^{n-1}+\ldots+\frac{a_n}{b_m}b_0X^{n-m} \right)$$

Il n'est pas nécessaire de faire le calcul explicitement pour voir que le polynôme obtenu n'est plus de degré $n$, il sera au plus de degré $n-1$.

Algorithme

Soit $P$ et $Q$ deux polynômes de degrés respectifs $n$ et $m$, avec $m\leq n$. 

a) On pose :

• $P_0=P$
• $n_0=\deg P=n$
• $P_1=P_0-\frac{\ell(P_0)}{\ell(Q)}X^{n_0-m}Q$
• $H_0=\frac{\ell(P_0)}{\ell(Q)}X^{n_0-m}$         
• $n_1=\deg P_1<n_0$

b) Pour tout $k\geq 2$ tel que $n_k\geq \deg Q=m$ :

On définit :

• $P_{k+1}=P_k-\frac{\ell(P_k)}{\ell(Q)}X^{n_k-m}Q$
• $H_k=H_{k-1}+\frac{\ell(P_k)}{\ell(Q)}X^{n_k-m}$
• $n_{k+1}=\deg P_{k+1}$

On note $R$ le dernier polynôme $P_r$ calculé (c'est-à-dire le dernier $P_{k+1}$ tel que $n_k=\deg P_k\geq \deg Q$, on a en particulier $n_{r+1}<\deg Q$).

On note $H=H_{r-1}$ (c'est-à-dire le dernier $H_k$ tel que $\deg P_k\geq \deg Q$).

Alors $P=QH+R$ avec $\deg R<\deg Q$.

Preuve de l'algorithme.

Il faut prouver que cet algorithme s'arrête et que les polynômes $H$ et $R$ obtenus vérifient bien (E1) et (E2). 

Tout d'abord l'algorithme s'arrête car la suite $(n_k)_k$ est strictement décroissante. Il existe donc un entier naturel $r$ tel que $n_r\geq \deg Q$ et $n_{r+1}<\deg Q$.

On a $\deg R< Q$ car l'inégalité $n_k\geq \deg Q$ est fausse à partir de $k=r+1$.

Reste à montrer que $P-R=QH$.

Faisons une démonstration par récurrence.

On a 

•     $P_1=P_0-H_0Q$ d'où  $$H_0Q=P_0-P_1$$
•     $P_2=P_1-(H_1-H_0)Q$ d'où 

    $$H_1Q=P_1-P_2+H_0Q=P_0-H_0Q-P_2+H_0Q=P_0-P_2$$

Et plus généralement pour tout $k\geq 2$ tel que $n_k\geq \deg Q=m$ : $P_{k+1}=P_k-(H_k-H_{k-1})Q$ d'où

  $$(\sharp) \ \ \ \ H_kQ=P_k-P_{k+1}+H_{k-1}Q$$

Si pour un certain $k\geq 2$ tel que $n_k\geq \deg Q$, on a $H_{k-1}Q=P_0-P_{k}$, alors d'après $(\sharp)$, on a 

$$H_kQ=P_k-P_{k+1}+H_{k-1}Q=P_k-P_{k+1}+P_0-P_k=P_0-P_{k+1}$$

On a donc montré par récurrence que pour tout $k\geq 2$ tel que $n_k\geq \deg Q$ : $H_kQ=P_0-P_{k+1}$. 

En particulier pour $k=r-1$, on obtient $H_{r-1}Q=P_0-P_{r}$, soit $HQ=P-R$.

On a donc prouvé l'existence de $Q$ et de $H$ tels que (E1) et (E2).

Énonçons maintenant le théorème de la division euclidienne dans $\mathbb R[X]$.

Théorème. 

Soient $P$ et $Q$ deux polynômes à coefficients réels. Alors il existe un unique couple $(H,R)$ de polynômes à coefficients dans $\mathbb R$ tels que $P=QH+R$ et avec $\deg R<\deg Q$.

Preuve. 

L'algorithme précédent permet d'établir que si $\deg Q\leq\deg P$, alors un couple $(H,R)$ existe. 

Si $\deg Q > \deg P$, alors $P=0\times Q + P$, le couple $(0,P)$ convient.

Il reste maintenant à montrer l'unicité du couple $(H,R)$. 

Supposons qu'il existe un autre couple $(L,S)$ vérifiant : $P=LQ+S$, avec $\deg S<\deg Q$.

Dans ce cas, on a $HQ+R=LQ+S$ d'où $(H-L)Q=S-R$. 

Si $H-L\neq 0$, alors, on aboutit à une contradiction car alors 

$$\deg Q \leq \deg(H-L)+\deg Q=\deg(S-R)\leq \max(\deg S, \deg R) < \deg Q$$

Donc $H=L$, puis nécessairement $S=R$.

Le théorème est donc démontré.

Et ensuite

Dans un prochain article, nous verrons un algorithme Python permettant d'effectuer une division polynomiale ainsi qu'un exemple de division euclidienne posée.