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

Нами доказано, что кольцо многочленов от х над полем P, т.о. P[x] – область целостности, евклидово кольцо, следовательно кольцо главных идеалов. Конкретизируем понятие общего делителя и наибольшего общего делителя в случае кольца P[x].

Определение 1. Если многочлен является делителем многочленов f(x) и g(x), то он называется общим делителем многочленов f(x) и g(x), т.е.

(f(x) ^g(x) )=> -общий делитель f(x) и g(x).

Определение 2. Общий делитель многочленов f(x) и g(x), который делится на любой общий делитель многочленов f(x) и g(x), называется наибольшим общим делителем многочленов f(x) и g(x) и обозначается (f,g)

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

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

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

Терема 2. Для любых двух многочленов f(x),g(x) P[x] существует наибольший общий делитель (f,x)= , который равен f(x)u(x) + g(x) (x)=1 (3)

, где и некоторые многочлены из P[x]. Говорят, что линейно выражается через многочлены f(x) и g(x).

Доказательство:

Доказательство этой теоремы вытекает из того, что ранее мы доказали, что кольцо P[x] – евклидово, а значит, кольцо главных идеалов, а в нём для любых двух его элементов существует наибольший общий делитель этих элементов, причём он линейно через них выражается, значит равенство (3) имеет место.

Следствие. Многочлены f(x) и g(x) P[x] взаимно просты тогда и только тогда, когда существует и P[x], такие что f(x) .

Из этого следствия следует ряд простых, но важных свойств простых многочленов:

1⁰ f(x) и g(x), h(x) P[x], ((f,g)=1^(f,h)=1) => (f,gh)=1

2⁰ f(x) и g(x), h(x) P[x], (f(x)g(x) h(x)^(f,h)=1) => f(x) h(x)

3⁰ f(x) и g(x), h(x) P[x], (f(x) g(x)^g(x) h(x)^(g,h)=1)=> f(x) g(x)h(x)

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

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

f(x) разделим на g(x)

f(x)= g(x)S₁(x) + (x)

f(x) разделим на (x) (4)

g(x) = (x)S₂ + (x)

(x) разделим на (x)

(x)= (x)S₃(x) + (x)

. . . . . . . . . . . . . . . . . . .

(x) = S_n(x) + (x)

(x)S_n+1(x)

Здесь мы исходим из того, что поле конечного числа делений остаток (x)=0

В самом деле, из определения деления с остатком следует, что степень (x) меньше степени g(x), степень (x) меньше степени (x), степень (x) меньше степени (x), степень (x) меньше степени (x)

И вообще степень _k(x) меньше степени _k-1(x); k=1,2,..,n. Это означает, что либо какой то из остатков _k = 0, либо степень остатка, уменьшилась при любом делении по крайней мере на 1, станет равной нулю. Если степень (x) = 0 , т.о. (x) = 0 (т.к. многочлен делится на многочлен нулевой степени без остатка). Таким образом во всех случаях алгоритм Евклида для многочленов сводится к конкретному числу делений с остатком. Если степень g(x) = m, то степень (x) меньше или равна m – 1, и значит число шагов в схеме (4) не может превышать .

В соответствии с общей теорией, последний, не равный нулю остаток в системе равенств (3) и является наибольшим общим делителем, т.е. (x) = (f,g)

Пример 7. Найти наибольший общий множитель (f,g) многочленов.

f(x) = ,

g(x)=

Решение:

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

x⁴ + x³ +x² + x + 1 4x³ + 3x² + 2x + 1

__ 4x⁴ + 4x³ +4x² + 4x + 4 x + 1

4x⁴ + 3x³ + 2x² + x

x³ + 2x² + 3x +4

__ 4x³ + 8x² + 3x +4

4x³ + 3x² + 2x +1

:5 5x² +10x +15

_ 4x³ + 3x² + 2x + 1 x² +2x + 3

4x³ + 8x² + 12x 4x -5

__ -5x² – 10x + 1

-5x² +10x - 15

16

_4x – 5 1

4x 4x - 5

_ -5

-5

0

т.о. наибольший общий делитель (f,g) = 1, т.е многочлены f(x) и g(x) взаимно простые. Система равенств (4) алгоритма Евклида позволяет не только найти наибольший общий делитель, но и выразить его линейно через многочлены f(x) и g(x).

Пример 8. Наибольший общий делитель многочленов f(x) и g(x) выразить через них линейно

f(x) = x⁴ + x³ + x² + x + 1,

g(x) = 4x³ + 3x² + 2x + 1.

Р ешение:

В данном случае не будем менять частные и остатки в алгоритме Евклида

1 ) f(x) = g(x)S₁(x) + ; _ x² + x³ + x² + x +1 4x³ + 3x² + 2x +1

x⁴ + x³ + x² + x x + = S₁(x)

x³ + x² + x + 1

x³ + x² + x +

2 ) g(x) = (x) S₂(x) + (x) __ 4x³ + 3x² +2x +1 x² + x + = (x)

4x³ + 8x² +12x x + =S₂(x)

_ -5x² – 10x + 1

-5x² – 10x – 15

x² + 16 = (x) ^. x² x² + x + = S₃(x)

3 ) (x) = (x)S₃(x)

0 = (x)

= > (f,g) = (x) = 16

Из второго равенства выразим (x) = g(x) - (x)S₂(x)

Из первого равенства выразим (x) = f(x) – g(x)S₁(x) => (x) = g(x) – (f(x) S₁(x)) S₂(x)=

(x) = g(x) – f(x) S₂(x) + g(x) S₁(x) S₂(x)=g(x) – f(x) S₂(x) + g(x) S₁(x) S₂(x) =

=f(x) (S₂(x))+g(x)(1+S₁ (x)S₂ (x));

( f,g)=f(x) [S₂(x)] +g(x) [1+S₁(x)S₂(x)] => 16 = (x⁴ + x³ +x² + x + 1) (- x + )+

(x) v(x)

+( 4x³ + 3x² + 2x + 1) (1+( x + ))( x - ))