Наибольший общий делитель многочленов. Алгоритм Евклида

Многочлен <р(х) называется общим делителем для заданных многочленов /(х) и д(х), если он является делителем для каждого из этих многочленов.

Согласно пятому свойству делимости многочленов можно заключить, что к числу общих делителей многочленов /(х) и д(х) принадлежат все многочлены нулевой степени (т.е. числа).

Два многочлена /(х) и д(х) называются взаимно простыми, если они не имеют никаких общих делителей кроме многочленов нулевой степени.

Наибольшим общим делителем (коротко НОД) отличных от нуля многочленов /(х) и д(х)над полем Р называется многочлен, который делится на все общие делители многочленов /(х) и д(х).

Обозначение: НОД (Д(х), д(х)) - наибольший общий делитель многочленов /(х) и д(х).

Для отыскания НОД удобно пользоваться алгоритмом Евклида (или алгоритмом последовательного деления).

Алгоритм Евклида

Суть алгоритма Евклида, с помощью которого находится наибольший общий делитель заданных многочленов /(х) и д(х) -(J(x), д(х)), состоит в последовательном делении сначала многочлена /(х) на <д(х), затем многочлена д(х) на полученный от первого деления остаток?^(х), затем г_г(х) на полученный от второго деления остаток г₂(х) и т.д. Поскольку степени остатков все время понижаются, то эта цепочка последовательных делений остановится в тот момент, когда деление совершится нацело. Тот остаток?^(х), на который нацело разделится предыдущий Tfc-i(x), и будет наибольшим общим делителем многочленов /(х) и д(х).

Запишем алгоритм Евклида следующей цепочкой неравенств:

/(х) = ^(х)(?₁(х)4-г₁(х), gW = r₁Mq₂(x) + r₂(x), П(х) = r₂(x)q₃(x) + r₃(x),

(1.38)

r_k_₃(x) = r_fc_₂(x)q_k_₁(x) + r_k_i(x), r_k-2 (x) = ^-i(x)q_k(%) + r_fe(x), ^k-i(x) = rfc(x)q_k+1(x).

Последнее равенство показывает, что ^г/с(х) служит делителем для ^rk-iM. Отсюда следует, что оба слагаемых правой части предпоследнего равенства делятся на г_к(х), а поэтому ^rk(x) будет делителем И ДЛЯ ^гк-г(х). Далее, таким же путем, поднимаясь вверх, мы получим, что 7/с(х) является делителем и для ^гк-з(^х), ..., ^r2(^x), ^ri(^x). Отсюда, ввиду второго равенства, будет следовать, что ^гкМ служит делителем для д(х а поэтому, на основании первого равенства, - и для/(х).

Таким образом, 7>(х) является общим делителем для/(х) и #(х).

Возьмем теперь произвольный общий делитель <р(х) многочленов /(х) и ^(х). Так как левая часть и первое слагаемое правой части первого из равенств (1.38) делятся на <р(х), то ^ri(^x) также будет делиться на <р(х). Переходя ко второму и следующему равенствам, мы таким же способом получим, что на <р(х) делятся многочлены г₂(х),г₃(х),....

Наконец, если уже будет доказано, что ^Гк-2М и ^rk-i(x) делятся на rk(x) делится наrk(x) на самом деле будет наибольшим общим делителем для /(х) ий'Сх).

Следствия алгоритма Евклида-.

• 1. Любые два многочлена обладают наибольшим общим делителем.
• 2. Если многочлены /(х) и $(х) имеют оба рациональные или действительные коэффициенты, то и коэффициенты их наибольшего общего делителя также будут рациональными или, соответственно, действительными.
• 3. Наибольший общий делитель двух многочленов определен лишь с точностью до множителя нулевой степени, т.е. если d(x) есть(/(х),_<д(х)),то и многочлен cd(x) также является (/(х),д(х)) в связи с третьим утверждением. Условимся, что старший коэффициент наибольшего общего делителя двух многочленов будет всегда считаться равным единице, а значит два многочлена тогда и только тогда взаимно просты, если их наибольший общий делитель равен единице.

Теорема 1.18

Если с/(х) есть наибольший общий делитель многочленов /(х) и $(%), то можно найти такие многочлены ц(х) и v(x), что

f(x)u(x) + g(x)v(x) = d(x). (1-39)

Доказательство. Можно считать при этом, если степени многочленов /(х) и д(х) больше нуля, то степень и(х) меньше степени д(х), а степень v(x) меньше степени/(х).

Доказательство основано на равенствах (1.38). Если мы учтем, что r_k(x) = d(x), и положим?^ (х) = 1, v₁(x) = —q_k(x), то предпоследнее из равенств (1.38) даст:

d(x) = г_к_Дх)иДх~) + r_k_i(x)v₁(x).

Подставляя сюда выражение г_/с_₁(х)через Г/с-з(х) и г_к_₂(х) из предшествующего равенства, мы получим:

d(x) = г_к_₃(х)и₂(х) + r_k_₂ (x)v₂(x),

где, очевидно, и₂(х) = Vi(x), v₂(x) = иДх) - v₁(x)q_k_₁(x).

Продолжая подниматься вверх по равенствам, мы придем, наконец, к доказываемому равенству.

Далее, теперь предположим, что многочлены и(х) и v(x), удовлетворяющие равенству (1.39), уже найдены, но, например, степень и(х) больше или равна степени <9(^х).

Делим п(х) на д(х):

и(х) = g(x)q(x) + г(х),

где степень г(х)меньше степени <9(^х), и подставляем это выражение в (1.39). Мы получим равенство

/(x)(#(x)q(x) + г(х)) + ^(x)v(x) = d(x), или

/(х)г(х) + g(x)[v(x) + /(x)q(x)] = d(x)

Степень множителя, стоящего при /(*), уже меньше степени ЯО). Степень многочлена, стоящего в квадратных скобках, будет в свою очередь меньше степени так как иначе степень второго слагаемого левой части была бы не меньше степени произведения <9(^х)/(^х), а так как степень первого слагаемого меньше степени этого произведения, то вся левая часть имела бы степень, большую или равную степени g(x)f(x), тогда как многочлен d(x) заведомо имеет, при наших предположениях, меньшую степень.

Ч.т.д.

Одновременно мы получаем, что если многочлены fM и дМ имеют рациональные или действительные коэффициенты, то и многочлены и(х) и

V(x), удовлетворяющие равенству (1.39) можно подобрать так, что их коэффициенты будут рациональными или, соответственно, действительными.

Представление (1.39) называется представлениемд.(х) (наибольшего общего делителя /(%) и д(хУ) в линейной форме.

Например, найдем наибольший общий делитель многочленов

/(х) = х³ — 5х² — Зх + 17 и д(х) = х⁵ — 5х⁴ — 2х³ + 12х² — 2х + 12, а затем представим его в линейной форме.

Применим к многочленам /(х) и д(х) алгоритм Евклида х⁵ - 5х⁴ - 2х³ + 12х² - 2х + 12 х³ - 5х² - Зх + 17 =f (х)

х⁵ - 5х⁴ - Зх³ + 17х² х² + 1 = (х)

х³ — 5х² — 2х + 12

~х³ - 5х² - Зх + 17

х - 5 =Гі(х)

х³ — 5х² — Зх + 17 х — 5= Гт (х) х³ — 5х² х² — 3 = q₂ (х) _-Зх + 17

• -Зх + 15
• 2 = r₂(x)=d(x)

х - 5І2 =г₂(х)____________

х —5 1/2х-5/2 = q₃(x) О

Таким образом (/(х), g(x'))=d(x') = г₂(х) = 2

Запишем равенства алгоритма Евклида:

' д(х) =f(x)q₁(x) + r₁(x)

• f(x) = q₂ (х)ії(х) + r₂(x)

. П(х) = <7з(*)п(Х) + ⁰

Выразим d(x) в линейной форме:

d(x) = /(х) - r_t(x)q₂ (х) = /(х) - ((^(х) - f^q₁(x^>))q₂ (х)}

= f W(1 + Qi Wq₂ (х)) + (-2 (х)^(х))

Находим и(х) и v(x):

u(x) = 1 + q₁(.x)q₂ (х) = 1 + (х² + 1)(х² - 3) = 1 + (х⁴ - 2х² - 3)

= х⁴ - 2х² - 2

v(x) = — q₂ (х) = —х² + 3

Получили

ц(х) = х⁴ - 2х² - 2; v(x) = —х² + 3.

Имеем

2 = (х⁴ — 2х² — 2)/(х) + (—X² + З)д(х)

Проверка:

2=(х⁴ — 2х² — 2)(х³ — 5х² — Зх + 17) + (—х² + 3)(х⁵ — 5х⁴ — 2х³ 4-+12х² — 2х + 12) = х³ + х⁷ — Зх⁵ + х⁵ — Зх³ — 5х² — 5х⁶ + 15х⁴ — 5х⁴ + +15х² - Зх - Зх⁵ + 9х³ - Зх³ + 9х + 17 + 17х⁴ - 51х² + 17х² - 51 -—х⁷ + 5х⁶ + 2х⁵ — 12х⁴ + 2х³ — 12х² + Зх⁵ — 15х⁴ — 6х³ + 36х² — 6% + +36 = 2

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

2 =(х⁴ — 2х² — 2)/(х) + (—х² + 3),д(х)

Многочлены /(х)и _<д(х)назовем взаимно простыми над полем Р, если их наибольший общий делитель состоит из многочленов нулевой степени в кольце Р[х].

Следствие. Многочлены /(х) и д(х) тогда и только тогда взаимно просты, если можно найти многочлены п(х) и v(x), удовлетворяющие равенству

/(x)u(x) + ,g(x)v(x) = 1. (1.40)

Теоремы о взаимно простых многочленах

• 1.19 Если многочлен f(x) взаимно прост с каждым из многочленов <р(х)иф(х), то он взаимно прост и с их произведением.
• (ЛОЖ*)) = 1-
• 1.20 Если произведение многочленов /(х) и 5'(х),_<д(х) делится на <р(х), но/(х) и <р(х) взаимно просты, то д(х) делится на <р(х).
• 1.21 Если многочлен /(х) делится на каждый из многочленов <р(х) иі/>(х), которые между собой взаимно просты, то /(х) делится и на их произведение.
• 1.22 Наибольший общий делитель многочленов А(х),/₂(х),... ,Д(х) равен наибольшему общему делителю многочлена Д(х)и наибольшего общего делителя многочленов /1(х),/₂(*)» А-1(*)-