Алгебра многочленов
Рассмотрим многочлен $$ f(x)=a_0+a_1x^1+a_2x^2+\ldots +a_nx^n $$ степени $n$ с коэффициентами из некоторого поля $\mathbb{F}$, не важно какого, это может быть $\mathbb{Q}$, $\mathbb{R}$ или $\mathbb{C}$. Степень многочлена $\deg f= n$ — это максимальный индекс ненулевого коэффициента $a_n\neq 0$ так, что $a_m=0$ при $m>n$. Такой коэффициент многочлена называют старшим. Обозначение степени многочлена в виде $\deg f$ идёт от английского термина degree, который естественно переводится как степень.
Множество всех многочленов с коэффициентами из $\mathbb{F}$ обозначают в виде $\mathbb{F}[x]$.
Для произвольных многочленов $f$ и $g$, например $$ g(x)=b_{0}+b_{1}x^{1}+b_{2}x^{2}+\ldots+b_{n}x^{n}+\ldots+b_{m}x^{m} $$ можно определить операции сложения $$ \left(f+ g\right)(x)= f(x)+ g(x)= a_{0}+b_{0}+\left(a_{1}+b_{1}\right)x^{1}+\left(a_{2}+b_{2}\right)x^{2}+\ldots +\left(a_{n}+b_{n}\right)x^{n}+b_{n+1}x^{n+1}+\ldots+b_{m}x^{m} $$ и умножения $$ \left(f\cdot g\right)(x)= f(x)\cdot g(x)= c_{0}+c_{1}x^{1}+\ldots+c_{n+m}x^{n+m}, $$ где коэффициенты $c_k$ определяются по формуле $$ c_0=a_0b_0, \ c_1=a_1b_0+a_0b_1, \ \ldots , \ c_{k}=\sum_{i+j=k}a_{i}b_{j}. $$ Очевидно, что степень суммы многочленов $\deg (f+g)\leq \max (\deg f ,\deg g)$ не превосходит максимальной степени входящих многочленов. Меньше может быть, например, при $m=n$ и $b_n=-a_n$. Степень произведения многочленов $\deg (f\cdot g)=\deg (f) \cdot \deg (g)$.
Введя сложение многочленов, естественно определить и нейтральный по сложению многочлен — он тривиальный $f_0=0.$ Обратный к $f$ по сложению будет $-f$. Таким образом, по сложению многочлены образуют абелеву группу $\left\langle \mathbb{F}[x];+,-, 0 \right\rangle $.
С умножением не всё так хорошо. Многое выполняется, например, ассоциативность и коммутативность, как следствие их выполнения для элементов самих многочленов, которые, как вы помните, мы рассматриваем из поля $\mathbb{F}$. Можем определить даже нейтральный по умножению многочлен $f_1=1$, но вот с обратным многочленом — проблема. Даже деление не всегда возможно. Единственно, что мы можем утверждать, так это то, что для любых многочленов $f(x)$ и $g(x)$ при условии $\deg f > \deg g$ имеется представление первого многочлена в виде $$ f(x)=g(x)\cdot q(x) + r(x), $$ причём $\deg r < \deg g$. Если остаток (Обозначают буквой $r$ от английского remainder — остаток.) $r(x)=0$, то получим обычное деление многочлена $f(x)$ на $g(x)$ с частным от такого деления — многочленом $q(x)$. Если же остаток ненулевой $r(x)\neq 0$, то это деление с остатком.
Деление многочленов
В качестве примера деления многочленов рассмотрим простой пример с конкретными многочленами $f(x)=x^5-2x^4+3x^3-4x^2+5x-6$ и $g(x)=x^2+x+1$. Как обычно воспользуемся делением столбиком и запишем оба уравнения: делимое — $f(x)$ и делитель — $g(x)$ рядом, разделяя их чертами: $$ \begin{array}{rrrrrr@{\,}r|l} x^5&{}-2x^4&{}+3x^3&{}-4x^2&{}+5x&{}-6&&\,x^2+x+1\\ \end{array} $$ Для того что бы в делимом убрать старший член надо делитель домножить на множитель $x^3$ и вычесть их произведение:
$$ \begin{array}{rrrrrr@{\,}r|l} x^5&{}-2x^4&{}+3x^3&{}-4x^2&{}+5x&{}-6&&\,x^2+x+1\\ {x^5}&{+\ \ x^4}&{+\ \ x^3}&&&&&\,{x^3}\\ &{{}-3x^4}&{{}-2x^3}&{{}-4x^2}&{{}+5x}&{{}-6}\\ \end{array} $$ Хотя все слагаемые не имеет смысл переписывать, ведь всё равно они остались в первой строке. Упростим запись $$ \begin{array}{rrrrrr@{\,}r|l} x^5&{}-2x^4&{}+3x^3&{{}-4x^2}&{{}+5x}&{{}-6}&&\,x^2+x+1\\ {x^5}&{+\ \ x^4}&{+\ \ x^3}&&&&&\,{x^3}\\ &{{}-3x^4}&{{}-2x^3}&&&\\ \end{array} $$ Теперь у нас старший член с коэффициентом $-3$ значит домножаем полином $g(x)$ на $-3x^2$ и вычитаем $$ \begin{array}{rrrrrr@{\,}r|l} x^5&{}-2x^4&{}+3x^3&{}-4x^2&{{}+5x}&{{}-6}&&\,x^2+x+1\\ x^5&+\ \ x^4&+\ \ x^3&&&&&\,x^3{-3x^2}\\ &{}-3x^4&{}-2x^3&&&\\ &{{}-3x^4}&{{}-3x^3}&{{}-3x^2}&&\\ &&{x^3}&{-\ \ x^2}&& \end{array} $$ Теперь старший член это $x^3$ с коэффициентом $1$, значит домножаем только на $x$ и вычитаем
$$ \begin{array}{rrrrrr@{\,}r|l} x^5&{}-2x^4&{}+3x^3&{}-4x^2&{}+5x&{{}-6}&&\,x^2+x+1\\ x^5&+\ \ x^4&+\ \ x^3&&&&&\,x^3-3x^2{+x}\\ &{}-3x^4&{}-2x^3&&&\\ &{}-3x^4&{}-3x^3&{}-3x^2&&\\ &&x^3&-\ \ x^2&&\\ &&{x^3}&{+\ \ x^2}&{+\ \ x}&\\ &&&{{} - 2 x^2}&{{}+4x}& \end{array} $$ Остался последний шаг. Теперь старший член с коэффициентом $-2$, значит домножаем наш полином на этот коэффициент и снова вычитаем $$ \begin{array}{rrrrrr@{\,}r|l} x^5&{}-2x^4&{}+3x^3&{}-4x^2&{}+5x&{}-6&&\,x^2+x+1\\ x^5&+\ \ x^4&+\ \ x^3&&&&&\,x^3-3x^2+x{-2}\\ &{}-3x^4&{}-2x^3&&&\\ &{}-3x^4&{}-3x^3&{}-3x^2&&\\ &&x^3&-\ \ x^2&&\\ &&x^3&+\ \ x^2&+\ \ x&\\ &&&{} - 2 x^2&{}+4x&\\ &&&{{} - 2 x^2}&{{} - 2 x}&{{} - 2} \\ &&&&{{}6x}&{{}-4} \end{array} $$ В итоге деления многочленов с остатком получили равенство $$ x^5-2x^4+3x^3-4x^2+5x-6= (x^3-3x^2+x-2)(x^2+x+1)+(6x-4). $$
Схема Горнера
Приведённый пример деления многочленов конечно подойдёт и для многочлена первой степени $g(x)=ax+b$, но всё же удобней воспользоваться схемой Горнера.
Давайте начнём с конкретного примера: $$ f(x)=5x^4+4x^3+x^2-2={5}{x^4}+{4}{x^3}+{1}{x^2}+{0}{x}{-2} $$ и $$g(x)=x-1=x-{1}.$$ Запишем коэффициенты многочленов в таблицу: $$ \begin{array} {c|c|c|c|c|c} & {5} & {4} & {1} & {0} & {-2} \\ \hline {1} & & & & & \end{array} $$ Начнём заполнять пустые ячейки. Во вторую ячейку второй строки запишем число 5, просто перенеся его вниз из второй ячейки первой строки: $$ \begin{array} {c|c|c|c|c|c} & {5} &{4} & {1} & {0} & {-2} \\ \hline {1} &{5} & & & & \end{array} $$ Следующую ячейку заполним по принципу ${1}\cdot{5}+{4}={9} $: $$ \begin{array} {c|c|c|c|c|c} & {5} & {4} &{1} & {0} & {-2} \\ \hline {1} &{5} & {9} & & & \end{array} $$ Далее аналогично со сдвигом на один столбец ${1}\cdot{9}+{1}={10} $: $$ \begin{array} {c|c|c|c|c|c} & {5} & {4} & {1} & {0} &{-2} \\ \hline {1} &{5} & {9} & {10} & & \end{array} $$ Следующий шаг ${1}\cdot{10}+{0}={10} $: $$ \begin{array} {c|c|c|c|c|c} &{5} & {4} &{1} & {0} & {-2} \\ \hline {1} &{5} & {9} & {10} & {10} & \end{array} $$ Завершающее действие ${1}\cdot{10}+{(-2)}={8} $: $$ \begin{array} {c|c|c|c|c|c} & {5} & {4} & {1} & {0} & {-2} \\ \hline {1} &{5} &{9} & {10} & {10} & {8} \end{array} $$ В результате можем записать:
$$ f(x) =5x^4+4x^3+x^2-2= (x-{1})\cdot\left({5}\cdot{x^4}+{9}\cdot{x^3}+{10}\cdot{x^2}+{10}\cdot{x}\right)+ (x-1)\left(5x^3+9x^2+10x+10\right)+8. $$ Последняя найденная цифра — это значение многочлена $f({1})={8}$.
Обобщим теперь на произвольный случай и разделим многочлен $$ f(x)=\sum\limits_{i=0}^{n}a_{i}x^{i}=a_{n}x^{n}+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\ldots+a_{1}x+a_0= {a_{n}}x^{n}+{a_{n-1}}x^{n-1}+{a_{n-2}}x^{n-2}+\ldots+{a_{1}}x+{a_0}. $$ на двучлен $g(x)=x-{a}$. Опять построим таблицу: $$ \begin{array} {c|c|c|c|c|c|c} & {a_{n}} & {a_{n-1}} & {a_{n-2}} & \ldots &{a_{1}} & {a_0} \\ \hline {a} & & & & & & \end{array} $$ и начнём её заполнять по алгоритму ${b_n}={a_{n}}$, ${b_{n-1}}={a}\cdot {b_{n}}+{a_{n-1}}, \ldots , {b_{n-k}}={a}\cdot {b_{n-k+1}}+{a_{n-k}} , \ldots , {b_0}$: $$ \begin{array} {c|l|l|l|l|l} & {a_{n}} & {a_{n-1}} & \ldots & {a_{1}} & {a_0} \\ \hline {a} &{b_n}={a_{n}} &{b_{n-1}}={a}\cdot {b_{n}}+{a_{n-1}} & \ldots &{b_{1}}={a}\cdot {b_{2}}+{a_{1}} &{b_{0}}={a}\cdot{b_{1}}+{a_{0}} \end{array} $$ В итоге получили выражение $$ f(x)= {a_{n}}x^{n}+{a_{n-1}}x^{n-1}+{a_{n-2}}x^{n-2}+\ldots+{a_{1}}x+{a_0}= \left( x-{a}\right) \left( {b_{n}}x^{n-1}+{b_{n-1}}x^{n-2}+\ldots+{b_{2}}x+{b_{1}}\right) +{b_0}. $$ Последний найденный коэффициент, как и ранее, совпадает со значением многочлена $f({a})={b_0}$.