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

Даны

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

Множество общих делителей не пустое, так как будет общим делителем любых многочленов.

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

Существует ли для любых двух многочленов НОД, если существует, то однозначен или нет, как их находить? Ответ на эти вопросы – алгоритм Евклида.

Даны .

Сравним степени n и m. Многочлен большей степени делим на многочлен меньшей степени. Если их степени равны, то неважно, какой многочлен, на какой делить. По теореме о делении с остатком такие, что .

Если то процесс останавливается.

Если то делим на .

ст. < ст. <

делим на

, ст. < ст. <

Процесс деления конечен

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

, - общий делитель.

(из последнего)

(из предпоследнего)

и т. д.

, - общий делитель.

Покажем, что - НОД

Пусть - общий делитель многочленов и

Из (1)

Из (2)

...

- НОД и .

Свойства НОД

1. НОД двух многочленов находится однозначно с точностью до числового множителя. (1)

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

– общий делитель.

- общий делитель.

По свойству делимости – два многочлена делятся друг на друга тогда и только тогда, когда они отличаются числовым множителем.

НОД и среди всех брать тот, у которого старший коэффициент равен 1 (нормированные).

Замечание: Учитывая свойство (1) при нахождении НОД с помощью алгоритма Евклида многочлены , , , , …, можно заменять другими многочленами, отличными числовыми множителями.

«Теорема о линейном представлении НОД двух многочленов»

Если , то

Над P: 1)

2) ст

ст

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

Доказательство существования вытекает из алг. Евклида

из получаем

,

Из 2 равенства:

,

и т.д.

Из предпоследнего:

подставим, сгруппируем и получим:

На практике будем находить , начиная с конца. При этом допускать умножения на числа нельзя.

Докажем, что ст.

ст.

Пусть - одна из пар, удовлетворяет теореме

.

Пусть ст. , разделим по теореме о делении с остатком . Найдем часть .

ст.

подставим

Покажем, что степень многочлена ст.

Если бы степень этого многочлена была ст. , тогда степень пр-я на этот многочлен была бы .

ст.

ст. ,

d – делитель.

ст.

ст.

получаем противоречие

ст.

Через возьмем , а через .

Получим ,

где ст. , а ст. .