Деление многочленов столбиком

В алгебре деление многочленов столбиком — алгоритм деления многочлена $f(x)$ на многочлен $g(x)$, степень которого меньше или равна степени многочлена $f(x)$. Алгоритм представляет собой обобщенную форму деления чисел столбиком, легко реализуемую вручную.

Для любых многочленов $f(x)$ и $g(x)$, $g(x) \ne 0$, существуют единственные полиномы $q(x)$ и $r(x)$, такие что

$\frac{f(x)}{g(x)}=q(x) + \frac{r(x)}{g(x)}$,

причем $r(x)$ имеет более низкую степень, чем $g(x)$.

Целью алгоритма деления многочленов в столбик является нахождение частного $q(x)$ и остатка $r(x)$ для заданных делимого $f(x)$ и ненулевого делителя $g(x)$.

Пример

Покажем, что частное и остаток от деления могут быть найдены в ходе выполнения следующих шагов:

1. Делим первый элемент делимого на старший элемент делителя, помещаем результат под чертой $\left( x^3 / x = x^2 \right)$.

$\begin{matrix} x^3 - 12x^2 + 0x - 42 \underline{\vert x-3}\\ \qquad\qquad\qquad\quad\; \vert x^2\\ \end{matrix}$

2. Умножаем делитель на полученный выше результат деления (на первый элемент частного). Записываем результат под первыми двумя элементами делимого $\left( x^2 \cdot \left( x-3 \right) = x^3 - 3x^2 \right)$.

$\begin{matrix} x^3 - 12x^2 + 0x - 42 \underline{\vert x-3}\\ x^3 \;\; - 3x^2 \qquad\qquad\;\; \vert x^2 \quad\; \\ \end{matrix}$

3. Вычитаем полученный после умножения многочлен из делимого, записываем результат под чертой $\left( x^3 - 12x^2 + 0x - 42 - \left( x^3 - 3x^2 \right) = - 9x^2 + 0x - 42 \right)$.

$\begin{matrix} x^3 - 12x^2 + 0x - 42 \underline{\vert x-3}\\ \underline{x^3 \;\; - 3x^2 \qquad\qquad\;\;} \vert x^2 \quad\; \\ - 9x^2 + 0x - 42 \;\; \end{matrix}$

4. Повторяем предыдущие 3 шага, используя в качестве делимого многочлен, записанный под чертой.

$\begin{matrix} x^3 - 12x^2 + \;\; 0x - 42 \vert x-3 \quad \\ \underline{x^3 \;\; - 3x^2 \qquad\qquad\;\;\;\;} \overline{\vert x^2 - 9x} \\ - 9x^2 \;\; + 0x - 42 \quad\;\; \\ \underline{- 9x^2 + 27x \qquad\;} \quad\;\; \\ \quad\; - 27x - 42 \end{matrix}$

5. Повторяем шаг 4.

$\begin{matrix} x^3 - 12x^2 + \;\; 0x - 42 \vert x-3 \qquad\quad\; \\ \underline{x^3 \;\; - 3x^2 \qquad\qquad\;\;\;\;} \overline{\vert x^2 - 9x - 27} \\ - 9x^2 \;\; + 0x - 42 \qquad\quad\;\;\; \\ \underline{- 9x^2 + 27x \qquad\;} \qquad\quad\;\;\; \\ - 27x - 42 \quad \\ \underline{- 27x + 81} \quad \\ \quad\; - 123 \end{matrix}$

6. Конец алгоритма.

Таким образом, многочлен $q(x) = x^2 - 9x - 27$ — частное деления, а $r(x) = - 123$ — остаток.

См. также

• Схема Горнера
• Теорема Безу
• Правило Руффини (англ.)
• Евклидово кольцо
• Базис Грёбнера
• Наибольший общий делитель двух многочленов (англ.)
• Синтетическое деление (англ.)