Présentation algorithmique de la démonstration de l'existence des polynômes Q et R
Si l'on reprend la division euclidienne de \(X^3-X^2+1\) par \(X+1\) et l'égalité évidente indiquée plus haut \(X^3-X^2+1=(X+1)X^2+(-2X^2+1)\) qui n'est pas l'identité de la division euclidienne, on peut transformer cette égalité en remarquant que \(-2X^2+1=-2X(1+X)+2X+1\). On obtient alors :
\(\begin{array}{ccc}X^3-X^2+1&=&(X+1)X^2-2X(1+X)+2X+1\\&=&(X+1)(X^2-2X)+2X+1\end{array}\)
Comme le polynôme \(2X+1\) est de degré 1, ce n'est pas le reste de cette division puisque son degré n'est pas strictement inférieur au degré du diviseur \(X+1\).
On peut écrire \(2X+1=2(X+1)-1\) et par conséquent : \(X^3-X^2+1=(X+1)(X^2-2X+2)(-1)\).
Le polynôme constant \(-1\) est de degré 0 et donc strictement inférieur à 1. Donc, là on a l'identité de la division euclidienne.
Quels enseignements peut-on tirer de cet exemple ?
On a obtenu par un moyen quelconque (ici du style bricolage) des polynômes \(Q\) et \(R\) satisfaisant aux conditions de l'identité de la division euclidienne. On a donc, du fait de leur unicité, le reste et le quotient de la division.
Effectivement, en théorie, tous les moyens mathématiquement corrects sont bons. Mais il est clair qu'il est nécessaire d'avoir une méthode de calcul systématique car il ne peut être question de bricolage comme dans l'exemple ci-dessus.
La réponse à cette question est l'algorithme suivant qui répond entièrement à la question posée. Il est basé sur le principe de la démonstration de l'existence et, techniquement, sur le lemme.
Si \(P\) est un polynôme non nul on note \(Dom(P)\) le monôme \(a_nX^n\) où \(n\) est le degré de \(P\) (i.e. \(a_n\neq 0\)).
Algorithme :
Entrer \(f, g\) ;
Initialiser : \(Q\leftarrow 0\), \(R\leftarrow f\);
(quotient par "divisions successives selon les puissances décroissantes")
Tant que \(R\neq 0\) et \(deg(R)\geq deg(g)\) faire :
Q partiel \(\leftarrow Dom(R)/Dom(g)\);
\(Q\leftarrow Q+(Q \textrm{ partiel})\);
\(R\leftarrow R-g(Q \textrm{ partiel})\);
Fin de l'algorithme
Explication : des notations pour les lecteurs non habitués à ce langage
La notation \(P\leftarrow P_1\) signifie que ce qui est à gauche prend pour valeur ce qui est à droite autrement dit sur cet exemple que \(P\) prend pour valeur \(P_1\).
Il faut bien remarquer qu'une nouvelle affectation écrase la précédente.
Si \(h\) et \(k\) sont deux polynômes non nuls, de termes dominants respectivement \(\alpha_rX^r\) et \(\beta_sX^s\), avec \(r\) supérieur ou égal à \(s\), la notation \(Dom(h)/Dom(k)\) représente le polynôme : \(\frac{\alpha_r}{\beta_s}X^{r-s}\).
Preuve :
primo : on a toujours (i.e à la fin de 2. et à la fin de chaque exécution de 3. \(f=gQ+R\);
secundo : l'algorithme se termine en un temps fini puisqu'à chaque exécution de 3. le degré de \(R\) diminue (en vertu du lemme) ;
tertio : lorsque l'algorithme est terminé, on a simultanément : \(f=gQ+R\) et \(R=0\) ou \(deg(R)<deg(g)\)