Démonstration du théorème de la division euclidienne
La preuve se décompose en deux parties : la démonstration de l'unicité, qui se fait par l'absurde et la démonstration de l'existence. Nous donnons dans ce paragraphe deux démonstrations de l'existence, l'une basée sur le raisonnement par récurrence, l'autre, plus abstraite en apparence, sur une propriété fondamentale des parties de \(N\).
Unicité
La démonstration se fait par l'absurde.
Soient \((Q,R)\) et \((Q',R')\) satisfaisant aux conditions du théorème.
On a donc à la fois \(f=gQ+R\) et \(f=gQ'+R'\) avec \(R=0\) ou \(degR<deg(g)\) et \(R'=0\) ou \(degR'<deg(g)\). Il vient alors
\(g(Q-Q')=R'-R\)
Si \(Q\neq Q'\), comme \(K[X]\) est intègre, \(g(Q-Q')\) est non nul, \(R'-R\) aussi et l'on peut donc considérer les degrés de ces polynômes.
Cela donne : \(deg(R-R')=deg(g(Q-Q'))=deg(g)+deg(Q-Q')\)
D'où l'inégalité : \(deg(R'-R)\geq deg(g)\).
Mais, le polynôme \(R'-R\) étant non nul, l'un au moins des deux polynômes \(R\) ou \(R'\) est non nul et on aura donc (à partir des propriétés \(R=0\) ou \(degR<deg(g)\), \(R'=0\) ou \(degR'<deg(g)\) et dans tous les cas possibles) : \(deg(R'-R)<deg(g)\).
(Si \(R\) et \(R'\) sont tous les deux non nuls, on applique le résultat général sur le degré d'une somme de polynômes.)
D'où la contradiction.
Donc \(Q=Q'\) et par conséquent \(R=R'\).
Existence
Les deux démonstrations données, ainsi qu'une présentation algorithmique, utilisent de façon essentielle le lemme suivant. C'est l'outil clé y compris pour le calcul effectif du reste et du quotient.
Lemme : Comment diminuer le degré
Soient \(f\) et \(g\) deux polynômes non nuls de \(K[X]\).
On suppose que : \(f(X)=a_nX^n+\ldots+a_1X+a_0\) et \(g(X)=b_pX^p+\ldots+b_1X+b_0\),
avec \(n\geq p\), \(a_n \neq 0\), \(b_p\neq 0\).
Alors le polynôme \(f_1(X)=f(X)-\frac{a_n}{b_p}X^{n-p}g(X)\) est soit nul, soit de degré strictement inférieur au degré de \(f\).
Le résultat est immédiat : le monôme dominant du polynôme \(f\) est \(a_nX^n\), celui de \(g\) est \(b_pX^p\).
Donc lorsque l'on calcule l'expression \(f_1(X)=f(X)-\frac{a_n}{b_p}X^{n-p}g(X)\), on voit apparaître :
\((a_nX^n+a_{n-1}X^{n-1}+\ldots+a_1X+a_0)-\frac{a_n}{b_p}X^{n-p}(b_pX^p+b_{p-1}X^{p-1}+\ldots+b_1X+b_0)\)
Comme \(\frac{a_n}{b_p}X^{n-p}(b_pX^p)=a_nX^n\), le coefficient de \(X^n\) dans le polynôme \(f_1\) est nul. Alors, soit \(f_1\)est le polynôme nul, soit c'est un polynôme de degré au plus égal à \(n-1\). D'où le résultat.
Exemple :
Soient les polynômes \(f(X)=2X^3+X+2\) et \(g(X)=5X^2+3X+1\). Alors,
\(\begin{array}{ccc}f_1(X)&=&(2X^3+X+2)-\frac25 X^{3-2}(5X^2+3X+1)\\&=&2X^3+X+2-(2X^3+\frac65 X^2+\frac25 X)\\&=&-\frac65X^2+\frac35 X+2\end{array}\)
qui est bien un polynôme de degré strictement inférieur au degré de \(f\).
Première démonstration de l'existence d'un quotient et d'un reste
Elle est basée sur une démonstration par récurrence.
Soit \(f\) et \(g\) deux polynômes de \(K[X]\), avec \(g\) non nul ; soit \(p\) le degré de \(g\).
Premier cas :\(f=0\)
La propriété \(f=0g+0\), avec \(f=0\) est évidente et l'on a bien trouvé des polynômes \(Q\) et \(R\) vérifiant les conditions de la division euclidienne (le quotient \(Q\) et le reste \(R\) sont tous les deux égaux au polynôme nul). La propriété est donc vraie dans ce cas.
Deuxième cas : Les polynômes \(f\) considérés sont non nuls.
On va faire une démonstration par récurrence sur le degré des polynômes \(f\).
Soit \(H_n\) la propriété : L'identité de la division est vérifiée pour tout polynôme \(f\) de degré inférieur ou égal à \(n\)
On va montrer que pour tout entier \(n\) supérieur ou égal à \(p-1\), on a la propriété \(H_n\) (Rappel : \(p\) est le degré de \(g\))
Première étape : Démonstration de \(H_{p-1}\)
Si \(deg(f)\leq p-1\), l'identité de la division euclidienne est vérifiée avec \(Q=0\) et \(R=f\) car on a \(f=g.0+f\) et \(degf<deg(g)\).
Deuxième étape : Démonstration de \(H_n\Rightarrow H_{n+1}\).
Soit \(f\) un polynôme de degré inférieur ou égal à \(n+1\). S'il est de degré inférieur ou égal à \(n\), l'application de la propriété \(H_n\)donne le résultat. Il suffit donc d'étudier le cas où \(f\) est de degré exactement égal à \(n+1\).
Soit donc \(f\) de degré égal à \(n+1\), \(f(X)=a_{n+1}X^{n+1}+\ldots+a_1X+a_0\), avec \(a_{n+1}\neq 0\).
Comme \(deg(g)=p\), on a : \(g(X)=b_pX^p+\ldots+b_1X+b_0\), avec \(b_p\neq 0\).
Alors, l'application du lemme prouve que le polynôme \(f_1(X)=f(X)-\frac{a_{n+1}}{b_p}X^{n+1-p}g(X)\) ne possède plus de terme de degré \((n+1)\); il est égal soit au polynôme nul, soit à un polynôme de degré inférieur ou égal à \(n\).
Alors on a, pour les polynômes \(f_1\) et \(m\), l'identité de la division euclidienne (soit en appliquant le premier cas, soit en appliquant l'hypothèse \(H_n\)).
Il existe donc \(Q_1\) et \(R_1\) tel que : \(f_1=gQ_1+R_1\), avec \(R_1=0\) ou \(deg(R_1)<deg(g)\).
On en déduit immédiatement :
\(f(X)=\left[\frac{a_{n+1}}{b_p}X^{n+1-p}+Q_1(X)\right]g(X)+R_1(X)\) avec \(R_1=0\) ou \(deg(R_1)<deg(g)\).
Ceci est l'identité de la division euclidienne pour les polynômes \(f\) et \(g\) avec :
\(Q(X)=\frac{a_{n+1}}{b_p}X^{n+1-p}+Q_1(X)\) et \(R(X)=R_1(X)\)
Remarque : 1
La propriété fondamentale qui a permis la démonstration est la suivante : dans le corps \(K\) si un élément \(a\) est non nul, il a un inverse (noté ici \(\frac 1a\)) pour la multiplication dans \(K\).
Remarque : 2
Cette démonstration a été choisie car elle introduit le traitement algorithmique de la division qui permet de calculer effectivement reste et quotient.
Mais il existe une autre démonstration de l'existence, plus abstraite et plus élégante, qui utilise de manière plus visible les propriétés de \(N\) relativement à la relation d'ordre.
Démonstration : théorique de la partie existence du théorème de la division euclidienne
Soit \(f\) et \(g\) deux polynômes de \(K[X]\), avec \(g\) non nul.
Si \(f=0\) ou si \(deg(f)<deg(g)\), l'identité de la division euclidienne est vérifiée avec \(Q=0\) et \(R=f\) car on a \(f=g.0+f\) et \(f=0\) ou \(degf<deg(g)\).
Si \(f\neq 0\)et si \(deg(f)\geq deg(g)\), on considère l'ensemble
\(E=\{P\in K[X], \exists S\in K[X], P=f-Sg\}\)
Premier cas : \(E\) contient le polynôme nul ; il existe donc un polynôme \(Q\) tel
que \(f=Qg\), l'identité de la division euclidienne est vérifiée avec \(R=0\)
Deuxième cas : \(E\) ne contient pas le polynôme nul
Cet ensemble est non vide (il contient par exemple \(f\) en prenant \(S=0\)).
On peut alors considérer l'ensemble des degrés des éléments de \(E\).
C'est une partie non vide de \(N\). Compte tenu des propriétés de \(N\), cet ensemble admet un plus petit élément, soit \(n_0\). Cela signifie que
\(\forall P\in E\), \(P\neq 0\), \(degP\geq n_0\)
\(\exists P_0\in E\), \(n_0=deg(P_0)\)
Il existe un polynôme \(S_0\) appartenant à \(K[X]\) tel que \(P_0=f-S_0g\),
soit \(f=S_0g+P_0\). Les polynômes \(S_0\) et \(P_0\) satisfont à une égalité du
type \(f=Qg+R\). Pour s'assurer que l'on a l'identité de la division euclidienne, il faut étudier le degré du polynôme \(P_0\)qui joue le rôle de reste.
On note \(f(X)=a_nX^n+\ldots+a_1X+a_0\), \(g(X)=b_pX^p+\ldots+b_1X+b_0\)
et \(P_0(X)=c_{n_0}X^{n_0}\). Ces trois polynômes sont non nuls.
Si le degré de \(P_0\) est supérieur ou égal au degré du polynôme \(g\), on peut utiliser le lemme.
Alors le polynôme \(P_1(X)=P_0(X)-\frac{c_{n_0}}{b_p}X^{n_0-p}g(X)\) est soit nul, soit de degré strictement inférieur au degré de \(P_0\).
Or il s'écrit : \(P_1(X)=f(X)-\left[S_0(X)+\frac{C_{n_0}}{b_p}X^{n_0-p}\right]g(X)\).
Il appartient donc à l'ensemble \(E\). Donc, comme \(E\) ne contient pas le polynôme nul, \(P_1\) n'est pas nul. On a donc trouvé un élément de \(E\) dont le degré est plus petit que \(n_0\).
Cela contredit la définition de \(n_0\).
Donc, le degré de \(P_0\) est strictement inférieur au degré du polynôme \(g\).