Алгоритм евклида для многочленов

п.2. Алгоритм Евклида для многочленов

Пусть — кольцо многочленов одной переменной х над полем Р.

Опр.4. Многочлены называются ассоциированными, если . Обозначается .

Теорема 9. Ненулевые многочлены ассоциированы и .

Доказательство: 1) Пусть .

.

Значит

▲.

Теорема 10. Пусть и тогда .

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

.

Импликация доказывается аналогично. ▲.

Опр.5. Пусть , . Многочлен называется наибольшим общим делителем многочленов , если:

1) — общий делитель , то есть ;

2) делится на любой общий делитель многочленов .

Обозначается .

Теорема 11. Пусть и . Если и , то .

Доказательство: Пусть и . Тогда, по определению НОД многочленов и ассоциированы. ▲.

Замечание: Ясно, что если — НОД , то также является НОД . То есть, если НОД двух многочленов существует, то он определен однозначно с точностью до ассоциированности.

Алгоритм Евклида для многочленов

Пусть и . Делим с остатком:

, где