Деление многочленов уголком: алгоритм¶

Деление многочленов уголком (также деление столбиком) — это алгоритм евклидова деления одного многочлена на другой, при котором степень делителя не превышает степень делимого. Результатом операции являются два многочлена: неполное частное и остаток, степень которого строго меньше степени делителя. Метод является прямым аналогом деления многозначных чисел столбиком и широко применяется в алгебре для разложения многочленов на множители, решения уравнений и упрощения рациональных выражений.

¶Описание алгоритма

Пусть даны многочлены \(P(x)\) (делимое) и \(S(x)\) (делитель), причём \(\deg P \ge \deg S\) и \(S(x) \neq 0\). Алгоритм состоит из повторяющихся шагов, на каждом из которых старший член делимого (или текущего остатка) делится на старший член делителя.

1. Начальный шаг. Записывают делимое и делитель по убыванию степеней. Если в делимом отсутствуют некоторые степени, их место заполняют нулевыми коэффициентами.
2. Деление старших членов. Старший член делимого \(a_n x^n\) делят на старший член делителя \(b_m x^m\). Полученный одночлен \(\frac{a_n}{b_m} x^{n-m}\) записывают как первый член частного.
3. Умножение и вычитание. Делитель умножают на найденный член частного, результат вычитают из делимого. Получается новый многочлен (промежуточный остаток), степень которого меньше степени предыдущего делимого.
4. Повторение. Процедуру повторяют с новым многочленом до тех пор, пока степень остатка не станет строго меньше степени делителя.

Итоговая запись имеет вид: \[ P(x) = S(x) \cdot Q(x) + R(x), \] где \(Q(x)\) — неполное частное, \(R(x)\) — остаток, причём \(\deg R < \deg S\). Если остаток равен нулю, то \(S(x)\) является делителем \(P(x)\).

¶Пример

Разделим \(P(x) = 2x^4 + 3x^3 - x^2 + 5x - 1\) на \(S(x) = x^2 - 2x + 1\).

1. Старший член делимого \(2x^4\) делим на \(x^2\): получаем \(2x^2\). Умножаем делитель на \(2x^2\): \(2x^4 - 4x^3 + 2x^2\). Вычитаем из делимого: остаток \(7x^3 - 3x^2 + 5x - 1\).
2. Делим \(7x^3\) на \(x^2\): получаем \(7x\). Умножаем делитель на \(7x\): \(7x^3 - 14x^2 + 7x\). Вычитаем: остаток \(11x^2 - 2x - 1\).
3. Делим \(11x^2\) на \(x^2\): получаем \(11\). Умножаем делитель на \(11\): \(11x^2 - 22x + 11\). Вычитаем: остаток \(20x - 12\).

Степень остатка \(20x - 12\) равна 1, что меньше степени делителя (2). Частное: \(Q(x) = 2x^2 + 7x + 11\), остаток: \(R(x) = 20x - 12\). Проверка: \((x^2 - 2x + 1)(2x^2 + 7x + 11) + 20x - 12 = 2x^4 + 3x^3 - x^2 + 5x - 1\).

¶Схема Горнера как частный случай

При делении многочлена на линейный двучлен вида \(x - c\) алгоритм уголком можно существенно упростить. В этом случае используется схема Горнера — табличный метод, требующий лишь операций умножения и сложения над коэффициентами. Деление на \(x - c\) всегда даёт остаток \(R = P(c)\) (теорема Безу), а частное имеет степень на единицу меньше исходного многочлена.

¶Применение

• Разложение на множители. Если известен один корень многочлена \(x = c\), деление на \(x - c\) позволяет понизить степень уравнения и найти остальные корни.
• Сокращение дробей. В рациональных выражениях деление уголком выделяет целую часть неправильной дроби, что упрощает интегрирование и построение графиков.
• Кодирование и теория чисел. В конечных полях (например, в криптографии и теории кодов, исправляющих ошибки) деление многочленов является базовой операцией для вычисления контрольных сумм и порождающих полиномов.
• Численные методы. Алгоритм лежит в основе методов поиска корней, таких как метод Лобачевского — Греффе и итеративные схемы уточнения корней.

¶Особые случаи

• Если делимый многочлен имеет пропущенные степени (например, \(x^4 + 1\)), при делении уголком необходимо явно записывать нулевые коэффициенты, иначе алгоритм даёт неверный результат.
• Если старший коэффициент делителя не равен 1, на каждом шаге возникает деление с дробными коэффициентами. Чтобы избежать дробей, можно предварительно умножить делимое на подходящую константу или использовать деление с рациональными коэффициентами.
• Если степень делимого меньше степени делителя, частное равно нулю, а остаток равен самому делимому.

¶Связь с другими методами

Деление уголком эквивалентно последовательному применению алгоритма Евклида к многочленам. Этот же принцип используется для нахождения наибольшего общего делителя многочленов: выполняется цепочка делений, пока остаток не станет нулевым. В отличие от разложения на элементарные дроби, метод не требует предварительного нахождения корней и работает в любом поле, включая поля рациональных, действительных и комплексных чисел.

¶Источники

• Курош А. Г. «Курс высшей алгебры», глава о многочленах.
• Винберг Э. Б. «Алгебра», раздел о евклидовом делении.
• Фаддеев Д. К., Соминский И. С. «Задачи по высшей алгебре».