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

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

Определение.Многочлен d(x) называется наибольшим общим делителем многочленов f(x) и g(x), если d(x) является делителем f(x) и g(x) и, если многочлен h(x) делит f(x) и g(x), то h(x) делит d(x). (Обозначение: d(x) = НОД(f(x), g(x))).

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

Если НОД(f(x), g(x)) есть число, то многочлены f(x) и g(x) называются взаимно простыми.

Рассмотрим алгоритм Евклида, позволяющий находить наибольший общий делитель двух многочленов. Пусть deg f(x) deg g(x). Разделим многочлен f(x) на многочлен g(x), получим остаток Затем g(x) разделим на , получим остаток Затем каждый многочлен делим на , обозначая остаток через . Так как степени остатков убывают, то на некотором шаге остаток будет равен нулю. Таким образом, имеем:

f(x) = g(x) (x) + (x), deg (x) deg g(x);

g(x)= (x) (x)+ (x), deg (x) deg (x); (x)= (x) (x)+ (x), deg (x) deg (x); ……………………………………………………………. (x) = (x) (x) + (x), deg (x) deg (x); (x) = (x) (x).

Утверждение.Последний отличный от нуля остаток (x) в алгоритме Евклида является наибольшим общим делителем многочленов f(x) и g(x).

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

Применим алгоритм Евклида:

_ |

| 2

(x)= 2 ;

_ | | + 0,25 0,5 0,5

(x)= ;

(x)= 0. Значит НОД(f(x), g(x))= .

Так как наибольший общий делитель определяется с точностью до постоянного множителя, то удобно считать что НОД(f(x), g(x))= .

Утверждение.Если d(x) наибольший общий делитель многочленов f(x) и g(x), то найдутся такие многочлены u(x) и v(x), что d(x) = u(x) f(x) + v(x) g(x), где степень u(x) меньше степени g(x), а степень v(x) меньше степени f(x).

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

u(x) f(x) + v(x) g(x) = 1, где deg f(x) deg v(x) и deg g(x) deg u(x).

Пример.Применяя алгоритм Евклида, найти такие многочлены u(x) и v(x), чтобы НОД(f(x), g(x)) = u(x) f(x) + v(x) g(x), где

f(x)= , g(x)= .

_ | | + 3

f(x) = g(x)( + 3) + .

= ( )( + 1).

Таким образом, НОД(f(x), g(x)) = .

Далее, двигаясь по алгоритму Евклида снизу вверх, имеем:

( )( ) + ( ,

= g(x)+ )( Следовательно,

( ) + ( .

Поскольку g(x)( + 3) f(x), получаем

( ) + g(x)( + 3) f(x), или

= f(x) + g(x) Окончательно имеем:

= f(x)( g(x)( , т.е.

u(x)= ( , v(x)= (

Пример.Не применяя алгоритм Евклида, найти такие многочлены u(x) и v(x), чтобы

u(x) f(x) + v(x) g(x) = 1, где f(x) = , g(x)= .

Учитывая, что deg f(x) deg v(x) и deg g(x) deg u(x), имеем:

f(x)( + g(x)( или

(

Для нахождения неопределенных коэффициентов А,В,С.К, приравниваем коэффициенты при одинаковых степенях в левой и правой частях этого равенства. Имеем систему: , откуда находим А= К = , В= = С= . Окончательно получаем u(x)= v(x)= .