Division synthétique

La valeur de ${\displaystyle P(x)}$ en ${\displaystyle a}$ est le reste de la division euclidienne de P par ${\displaystyle (x-a)}$, puisque ${\displaystyle P(x)=(x-a)Q(x)+R}$, et donc que ${\displaystyle P(a)=(a-a)Q(a)+R=R}$. Cette méthode de calcul de ${\displaystyle P(a)}$ demande environ moitié moins de multiplications que la méthode naïve.

La méthode précédente se généralise à la division par un polynôme unitaire D(x) quelconque, avec une légère modification indiquée ici en gras. Dans l'exemple

${\displaystyle {\frac {x^{3}-12x^{2}-42}{x^{2}+x-3}}}$,

on écrit les coefficients du dividende sur la première ligne

${\displaystyle {\begin{array}{|rrrr}\ 1&-12&0&-42\end{array}}}$,

et les coefficients de l'opposé du diviseur ${\displaystyle -D(x)=-x^{2}-x+3}$ (sauf le premier) dans une diagonale montant vers la droite, comme ci-dessous :

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\end{array}}&{\begin{array}{|rrrr}\ 1&-12&0&-42\\&&&\\&&&\\\hline \end{array}}\end{array}}}$

Comme précédemment, on descend ensuite le premier coefficient à gauche vers la dernière rangée :

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&&\\&&&\\\hline 1&&&\\\end{array}}\end{array}}}$.

On multiplie ensuite ce coefficient par toute la diagonale de gauche, et on place les résultats en diagonale et sur la droite du nombre descendu :

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&\\&-1&&\\\hline 1&&&\\\end{array}}\end{array}}}$

On additionne tous les nombres de la colonne immédiatement à droite.

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&\\&-1&&\\\hline 1&-13&&\\\end{array}}\end{array}}}$,

et on recommence ces deux étapes jusqu'au moment où la diagonale suivante dépasserait le dernier coefficient du dividende.

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&-39\\&-1&13&\\\hline 1&-13&16&\\\end{array}}\end{array}}}$

On termine d'additionner les colonnes restantes éventuelles :

${\displaystyle {\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&-39\\&-1&13&\\\hline 1&-13&16&-81\\\end{array}}\end{array}}}$

Le reste est formé du même nombre de colonnes que les diagonales (ici 2), ce qui donne ${\displaystyle x^{3}-12x^{2}-42=(x^{2}+x-3)(x-13)+16x-81}$, ou encore

${\displaystyle {\frac {x^{3}-12x^{2}-42}{x^{2}+x-3}}=x-13+{\frac {16x-81}{x^{2}+x-3}}}$

On peut évidemment commencer par diviser D(x) par son coefficient dominant a (lorsqu'on travaille dans un anneau, si a est inversible), puis en multipliant le quotient obtenu par 1/a (mais pas le reste) ; en pratique, il est plus efficace et plus sûr d'effectuer la division à chaque étape, après addition, mais avant de multiplier les diagonales, comme on le voit dans l'exemple suivant :

${\displaystyle {\frac {6x^{3}+5x^{2}-7}{3x^{2}-2x-1}}}$

On ajoute une ligne supplémentaire correspondant à la division (sans changer le signe, cette fois) :

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline &&&\\&&&\\\end{array}}\end{array}}}$

Après chaque étape de « descente », la valeur est divisée par a :

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline 6&&&\\2&&&\\\end{array}}\end{array}}}$

et c'est cette valeur qui est utilisée pour remplir la diagonale suivante :

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&\\&4&&\\\hline 6&&&\\2&&&\\\end{array}}\end{array}}}$

On recommence la séquence addition-division, dans la colonne suivante :

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&\\&4&&\\\hline 6&9&&\\2&3&&\\\end{array}}\end{array}}}$

puis on construit la nouvelle diagonale :

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&3\\&4&6&\\\hline 6&9&&\\2&3&&\\\end{array}}\end{array}}}$.

Lorsqu'on atteint les colonnes de droite, l'opération est terminée (on ne divise pas les coefficients du reste)

${\displaystyle {\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&3\\&4&6&\\\hline 6&9&8&-4\\2&3&&\\\end{array}}\end{array}}}$

En définitive, le résultat se lit ainsi :

${\displaystyle {\begin{array}{rr|rr}2x&+3&8x&-4\end{array}}}$

et on a donc

${\displaystyle {\frac {6x^{3}+5x^{2}-7}{3x^{2}-2x-1}}=2x+3+{\frac {8x-4}{3x^{2}-2x-1}}}$

Cependant, le format précédent devient trop encombrant lorsque le degré du diviseur est plus grand que la moitié du degré du dividende. Comme chaque produit peut être écrit dans une ligne quelconque, tant que la colonne est correcte, un algorithme glouton permet d'optimiser la place prise, comme l'illustre l'exemple suivant :

${\displaystyle {\dfrac {ax^{7}+bx^{6}+cx^{5}+dx^{4}+ex^{3}+fx^{2}+gx+h}{ix^{4}-jx^{3}-kx^{2}-lx-m}}=nx^{3}+ox^{2}+px+q+{\dfrac {rx^{3}+sx^{2}+tx+u}{ix^{4}-jx^{3}-kx^{2}-lx-m}}}$

${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\\\\\\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&&&&qj&&&\\&&&pj&pk&qk&&\\&&oj&ok&ol&pl&ql&\\&nj&nk&nl&nm&om&pm&qm\\a&b&c&d&e&f&g&h\\\hline a&o_{0}&p_{0}&q_{0}&r&s&t&u\\n&o&p&q&&&&\\\end{array}}\end{array}}}$

L'algorithme (comportant des étapes de division si i ≠ 1) est le suivant :

1. Écrire les coefficients du dividende

   ${\displaystyle {\begin{array}{cc}{\begin{array}{|rrrrrrrr}\ a&b&c&d&e&f&g&h\\\hline \end{array}}\end{array}}}$

2. Écrire à gauche les coefficients du diviseur changés de signe, à l'exception du coefficient dominant.

   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}j&k&l&m\\\end{array}}&{\begin{array}{|rrrrrrrr}\ a&b&c&d&e&f&g&h\\\hline \end{array}}\end{array}}}$

3. Marquer la séparation entre le quotient et le reste par une barre verticale, en laissant autant de colonnes pour le reste que le degré du diviseur.

   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}j&k&l&m\\\\\end{array}}&{\begin{array}{|rrrr|rrrr}a&b&c&d&e&f&g&h\\\hline &&&&&&&\\\end{array}}\end{array}}}$

4. « Descendre » le premier coefficient du dividende.

   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}j&k&l&m\\\\\end{array}}&{\begin{array}{|rrrr|rrrr}a&b&c&d&e&f&g&h\\\hline a&&&&&&&\\\end{array}}\end{array}}}$

   • Si le diviseur n'est pas unitaire, diviser le terme qui vient d'être descendu ou sommé par le coefficient dominant du diviseur, et le placer sur la ligne suivante. À la première étape, on a donc ${\displaystyle n={\dfrac {a}{i}}}$.
   • Multiplier ce nombre par chaque coefficient de gauche (les coefficients du diviseur changés de signe). Placer chaque produit au sommet des colonnes suivantes.

   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&nj&nk&nl&nm&&&\\a&b&c&d&e&f&g&h\\\hline a&&&&&&&\\n&&&&&&&\\\end{array}}\end{array}}}$

5. Additionner colonne par colonne ; on a donc ${\displaystyle o_{0}=b+nj}$.

   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&nj&nk&nl&nm&&&\\a&b&c&d&e&f&g&h\\\hline a&o_{0}&&&&&&\\n&&&&&&&\\\end{array}}\end{array}}}$

6. Répéter les deux étapes précédentes, jusqu'à atteindre la barre de séparation. Soit ${\displaystyle o={\dfrac {o_{0}}{i}}}$.

   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&&oj&ok&ol&&&\\&nj&nk&nl&nm&om&&\\a&b&c&d&e&f&g&h\\\hline a&o_{0}&p_{0}&&&&&\\n&o&&&&&&\\\end{array}}\end{array}}}$

   on a donc ${\displaystyle p_{0}=c+nk+oj}$. Soit ${\displaystyle p={\dfrac {p_{0}}{i}}}$.

   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\\\\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&&&pj&pk&&&\\&&oj&ok&ol&pl&&\\&nj&nk&nl&nm&om&pm&\\a&b&c&d&e&f&g&h\\\hline a&o_{0}&p_{0}&q_{0}&&&&\\n&o&p&&&&&\\\end{array}}\end{array}}}$

   on a donc ${\displaystyle q_{0}=d+nl+ok+pj}$. Soit ${\displaystyle q={\dfrac {q_{0}}{i}}}$.

   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\\\\\\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&&&&qj&&&\\&&&pj&pk&qk&&\\&&oj&ok&ol&pl&ql&\\&nj&nk&nl&nm&om&pm&qm\\a&b&c&d&e&f&g&h\\\hline a&o_{0}&p_{0}&q_{0}&r&&&\\n&o&p&q&&&&\\\end{array}}\end{array}}}$

7. Le calcul des coefficients du reste s'obtient en additionnant les colonnes restantes sans effectuer de nouveaux calculs (par exemple, ${\displaystyle r=e+nm+ol+pk+qj}$, ${\displaystyle s=f+om+pl+qk}$).

   ${\displaystyle {\begin{array}{cc}{\begin{array}{rrrr}\\\\\\\\j&k&l&m\\\end{array}}&{\begin{array}{|rrrr|rrrr}&&&&qj&&&\\&&&pj&pk&qk&&\\&&oj&ok&ol&pl&ql&\\&nj&nk&nl&nm&om&pm&qm\\a&b&c&d&e&f&g&h\\\hline a&o_{0}&p_{0}&q_{0}&r&s&t&u\\n&o&p&q&&&&\\\end{array}}\end{array}}}$

8. Comme précédemment, l'interprétation est donc :

   ${\displaystyle {\dfrac {ax^{7}+bx^{6}+cx^{5}+dx^{4}+ex^{3}+fx^{2}+gx+h}{ix^{4}-jx^{3}-kx^{2}-lx-m}}=nx^{3}+ox^{2}+px+q+{\dfrac {rx^{3}+sx^{2}+tx+u}{ix^{4}-jx^{3}-kx^{2}-lx-m}}}$