Главная | Обратная связь

Наибольший общий делитель

Пусть даны произвольные много­члены f(x) и g(x) из P[x]. Многочлен (x)ÎP[x] будет называться общим дели­телем f(x) и g(x), если он служит делителем каждого из этих многочленов. Свойство V (см. выше) показывает, что к числу общих делителей многочленов f(x) и g(x) принадлежат все много­члены нулевой степени. Если других общих делителей эти два много­члена не имеют, то они называются взаимно простыми.

В общем же случае многочлены f(x) и g(x) могут обладать общими делителями, зависящими от х, и мы хотим ввести понятие о наибольшем общем делителе этих многочленов.

Если это делать по аналогии с целыми числами, то наибольшим общим делителем f(x) и g(x) надо называть их общий делитель, который больше всех остальных; но для многочленов (и даже для комплексных чисел) нельзя ввести естественным образом понятия > и <. Поэтому мы поступим иначе.

Определение 1. Наибольшим общим делителем отличных от нуля многочленов f(x) и g(x) из P[x] называется такой многочлен d(x) из P[x], который является их общим делителем и сам делится на любой общий делитель этих многочленов.

Обозначается наибольший общий делитель многочленов f(х) и g(x) символом (f(х), g(x)) и пишется: d(x) = (f(х), g(x)).

Это определение оставляет открытым вопрос, существует ли наи­больший общий делитель для любых ненулевых многочленов f(x) и g(x). Ниже на этот вопрос будет дан положительный ответ. Одновременно будет дан метод для практического разыскания наибольшего общего дели­теля данных многочленов. Понятно, что мы не можем перенести сюда тот способ, каким обычно разыскивается наибольший общий делитель целых чисел (связанный с разложением на простые множители), так как пока не имеем для многочленов ничего ана­логичного такому разложению целого числа. Для целых чисел существует и другой способ, назы­ваемый алгоритмом последовательного деления или алгоритмом Евклида; этот способ вполне применим и к многочленам.

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

Алгоритм Евклида для многочленов состоит в следующем: Пусть даны многочлены f(x) и g(x) из P[x]. Делим f(x) на g(x) и получаем некоторый остаток r₁(х) Î P[x]. Если r₁(х)¹0, то делим затем g(x) на r₁(х) и получаем остаток r₂ (х) Î P[x]; делим r₁(х) на r₂ (х) и и т. д. Так как сте­пени остатков все время понижаются, то в этой цепочке последова­тельных делений мы должны дойти до такого места, на котором деление совершится нацело и поэтому процесс остановится.

Докажем, что тот остаток r_k(х), на который нацело делится предыдущий остаток r_k-1(x), и будет наибольшим общим делителем многочленов f(x) и g(x), т.е. r_k(х)=( f(x), g(x)). (1)

Для доказательства запишем указанные выше деления с остатком в виде следующей цепочки равенств:

. (2)

I. Покажем, что r_k(x) – общий делитель f(x) и g(x).

Последнее из равенств (2) показывает, что r_k(x) служит делителем для r_k-1(x). Отсюда следует, что оба слагаемых правой части предпо­следнего равенства делятся на r_k(x), а поэтому r_k(x) будет делителем и для r_k-2(x). Далее, таким же путем, поднимаясь вверх, мы полу­чим, что r_k(x) является делителем и для r_k-3(x), ..., r₂(x), r₁(x). Отсюда, ввиду второго (сверху) из равенств (2), будет следовать, что r_k(x) служит делителем для g(x), а поэтому, на основании первого равенства, – и для f(x). Таким образом, r_k(x) является общим делителем f(x) и g(x).

II. Докажем теперь, что произвольный общий делитель q(x) Î P[x] многочленов f(х) и g(x) является делителем r_k(x).

Так как левая часть и первое слагаемое правой части первого из равенств (2) делятся на q(x), то r₁(x) также будет делиться на q(х) (в этом легко убедиться, если в правой части этого равенства оставить только r₁(x)). Переходя ко второму и следующему равенствам, мы таким же способом получим, что на q(х) делятся многочлены r₂(x), r₃(x),……. Наконец, если уже будет доказано, что r_k-2(x) и r_k-1(x) делятся на q(x), то из предпоследнего равенства мы получим, что r_k(x) делится на q(х).

Таким образом, r_k(x) на самом деле будет наибольшим общим делителем f(x) и g(x), причем r_k(x) Î P[x]. Равенство (1) доказано.

Следовательно, мы доказали, что любые два многочлена обладают наибольшим общим делителем, и получили способ для его вычисления. Отметим, что хотя у многочленов могут существовать и общие делители из S[x], где S – некоторое расширение P, но (f(x),g(x)) все равно принадлежит P[x]. Так, много­члены с рациональными коэффициентами f(x)=x³-3x²-2x+6, g(x)= x³+x²-2x-2

имеют наибольшим общим делителем многочлен из кольца Q[x]

(x²-2), хотя у них есть общий делитель (x ) из кольца R[x] .

Сколько наибольших делителей имеет пара многочленов f(x), g(x)?

Если d(x) есть их наибольший общий делитель, то, как показывают свойство IX из §3 этой главы, в качестве наибольшего общего делителя этих многочленов можно было бы выбрать также многочлен cd(x), где с – произвольное число из поля P, отличное от нуля. Обратно, если d(x) и d₁(x) – два наибольших общих делителя f(x) и g(x), то по свойству VIII d₁(x)=cd(x) для некоторого с Î P\0.

Значит, cd(x) – все наибольшие общие делители f(x) и g(x). Иными словами, наибольший общий делитель двух много­членов определен лишь с точностью до множителя нулевой степени. Ввиду этого можно условиться, что старший коэф­фициент наибольшего общего делителя двух много­членов будет всегда считаться равным единице. Используя это условие, можно сказать, что два многочлена тогда и только тогда взаимно просты, если их наибольший общий делитель равен единице.