Ділення многочленів

В алгебрі ділення многочленів стовпчиком — алгоритм ділення многочлена ${\displaystyle f(x)}$ на многочлен ${\displaystyle g(x)}$, степінь якого менше або дорівнює степеню многочлена ${\displaystyle f(x)}$. Алгоритм являє собою узагальнену форму ділення чисел стовпчиком, легко реалізується вручну. Для будь-яких многочленів ${\displaystyle f(x)}$ та ${\displaystyle g(x)}$, ${\displaystyle g(x)\neq 0}$, існують єдині поліноми ${\displaystyle q(x)}$ та ${\displaystyle r(x)}$, такі що

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

причому ${\displaystyle r(x)}$ має нижчий степінь, ніж ${\displaystyle g(x)}$.

Метою алгоритму ділення многочленів у стовпчик є знаходження частки ${\displaystyle q(x)}$ й остачі ${\displaystyle r(x)}$ для заданих діленого ${\displaystyle f(x)}$ та ненульового дільника ${\displaystyle g(x)}$.

Ділити многочлени в стовпчик можна алгоритмом, аналогічним до того, як діляться натуральні числа.

1. Спочатку треба перевірити, чи обидва многочлени впорядковані за спадними степенями тієї самої змінної; якщо ні, то впорядкувати їх, дописуючи також ті члени, яких немає (наприклад, замість ${\displaystyle 1-x^{3}}$ писатиметься ${\displaystyle -x^{3}+0x^{2}+0x+1}$).
2. «Підготувати» многочлени до ділення.
3. Поділити найстарший член діленого на найстарший член дільника.
4. Помножити отриманий одночлен на дільник.
5. Відняти отриманий многочлен від діленого.
6. Продовжувати так само, поки не отримаємо нуль або многочлен зі степенем меншим за степінь дільника. Це і є остача даного ділення.

Покажемо, що

${\displaystyle {\frac {x^{3}-12x^{2}-42}{x-3}}=x^{2}-9x-27-{\frac {123}{x-3}}}$

Частка і остача від ділення можуть бути знайдені при виконанні наступних кроків:

1. Ділимо перший елемент діленого на старший елемент дільника, розташовуємо результат під рисою ${\displaystyle \left(x^{3}/x=x^{2}\right)}$.

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

2. Множимо дільник на отриманий вище результат ділення (на перший елемент частки). Записуємо результат під першими двома елементами діленого ${\displaystyle \left(x^{2}\cdot \left(x-3\right)=x^{3}-3x^{2}\right)}$.

${\displaystyle {\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. Віднімаємо, отриманий після множення, многочлен від діленого, записуємо результат під рискою ${\displaystyle \left(x^{3}-12x^{2}+0x-42-\left(x^{3}-3x^{2}\right)=-9x^{2}+0x-42\right)}$.

${\displaystyle {\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 кроки, використовуючи як ділене многочлен, записаний під рискою.

${\displaystyle {\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.

${\displaystyle {\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. Кінець алгоритму.

Таким чином, многочлен ${\displaystyle q(x)=x^{2}-9x-27}$ — частка від ділення, а ${\displaystyle r(x)=-123}$ — остача.

• Теорема Безу
• Синтетичне ділення
• Правило Руффіні
• Евклідове кільце

• Завало С. Т. (1985). Курс алгебри. Київ: Вища школа. с. 503. (укр.)
• Прасолов В. В. Многочлены. — 2-е. — Москва : МЦНМО, 2001. — 336 с. — ISBN 5-94057-077-1.(рос.)
• Дональд Кнут. Seminumerical Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 2. — 762 с. — ISBN 0-201-89684-2.(англ.)