Схема Горнера
Теорема Безу
Рассмотрим более подробно процесс деления многочлена $P_n(x)$ на линейный двучлен вида $x - \alpha$. В этом случае деление упрощается и может быть проведено по специальной схеме, называемой обычно схемой Горнера.
Запишем основное равенство, определяющее частное и остаток, в случае делителя вида $x - \alpha$; частное имеет степень $n - 1$, а остаток - нулевую степень, т. е. просто является числом:
$a_0x^n + a_1x^{n-1} + \cdots + a_n = (x - \alpha)(b_0x^{n-1} + b_1 x^{n-2} + \cdots + b_{n-1}) + r$. (1)
Как уже указывалось, это равенство - тождественное, многочлены в его левой и правой частях совпадают; раскрыв скобки, получим равенства, выражающие совпадение коэффициентов при одинаковых степенях $x$:
$a_0 = b_0$,
$a_1 = - ab_0 + b_1$,
$a_2 = -ab_1 + b_2$,
$\cdots$
$a_{n-1} = - ab_{n-2} + b_{n-1} + r$.
Отсюда последовательно находим
$b_0 = a_0$,
$b_1 = a_1 + ab_0$,
$b_2 = a_2 + ab_1$,
$\cdots$
$b_{n-1} = a_{n-1} + ab_{n-2}$,
$r = a_n + ab_{n-1}$.
Вычисление коэффициентов частного и остатка располагают в такой таблице:
Верхняя строка таблицы заполняется сразу; в нижней строке помещаются коэффициенты частного и остаток; она заполняется постепенно, слева направо. В каждой клетке нижней строки записывается сумма коэффициентов из верхней строки и умноженного на а результата, записанного в соседней слева клетке нижней строки.
Замечательно, что остаток от деления многочлена на двучлен $x - \alpha$ может быть найден независимо от выполнения деления, без отыскания частного. Действительно, положим в равенстве
$P_{n} (x) = (x - \alpha)Q(x) + r$
$x = \alpha$. Так как равенство тождественное, то оно удовлетворится и мы найдем
$P_{n} ( \alpha ) = r$.
Остаток от деления многочлена $P_{n}(x)$ на двучлен вида $x - \alpha$ равен значению многочлена при $x = \alpha$:
$r = P_{n} (x)|_{x = \alpha}$.
Как следствие отсюда вытекает
Теорема Безу. Многочлен $P_{n}(x)$ делится без остатка на двучлен $x - \alpha$ в том и только в том случае, когда $\alpha$ - корень многочлена.
Пример. Найти остаток от деления многочлена $x^{3} + 6x^{2} - 2x + 5$ на двучлен $x - 3$ (не выполняя деления).
Решение. Значение остатка находим так:
$x^{3} + 6x^{2} - 2x + 5|_{x = 3} = 27 + 54 - 6 + 5 = 80$.
Пользуясь теоремой Безу, легко выяснить, при каких условиях выражения вида ($a \neq 0$)
$x^{n} - a^{n}, x^{n} + a^{n}$
будут делиться на $x - a, x + a$ без остатка.
1) $x^{n} - a^{n}$ делится на $x - a$ при любом $n$. Действительно,
$x^{n} - a^{n}|_{x=a} = a^{n} - a^{n} = 0$,
откуда делимость вытекает в силу теоремы Безу.
2) $x^{n} + a^{n}$ делится на $x + a$ при четном $n$ и не делится при нечетном $n$. Действительно, находим
$x^{n} - a^{n} |_{x = -a} = (-a)^{n} - a^{n} = \begin{cases} 0&, если \: n \: - \: четное, \\ -2a^{n}&, если \: n \: - \: нечетное, \end{cases}$
откуда и следует наше утверждение.
3) $x^{n} + a^{n}$ делится на $x + a$ при нечетном $n$ и не делится при четном $n; x^{n} + a^{n}$ не делится на $x - a$ ни при каком $n$.
Доказательство аналогично.