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

30. М — общ делитель а и b. Покажем: .

Рассмотрим равенство алгоритма начиная с первого (т. к. М- общий делитель) ,т. е

Из

Аналогично получаем, что .

Значит М-НОД чисел a и b

Теорема4: Если то

ОПР: Общим кратным целых чисел отличных от нуля, наз-ют такое целое число c, которое делится на каждое из чисел

ОПР.

Число М наз НОК чисел a и b, если: 10 М>0,

20

30 где K-общ кратное a и b

Теорема5: Если НОК существует, то он единственный.

Теорема6:НОК целых чисел равно НОК их модулей.

Д-ва Т 5 и 6 анал-ны док-ам Т 1 и 2. Т6 позволяет рассм-ть НОК только натур. чисел. След. Т дает способ отыскания НОК 2-х натур. чисел.

Теорема7: НОК двух натур чисел равно частному от деления произведения этих чисел на НОД. [a, b]=

Док.: покажем, что число удовл-ет всем трем усл-ям опр-ия НОК целых чисел.

1) , т. к. a, b,

2) Покажем, что число есть общее кратное чисел a и b.

Обозначим , причем числа q и t взаимно просты, т. е. (q, t)=1. Имеем:

3) Покажем, что любое общее кратное чисел a и b дел-ся на число . Пусть m — произв. общее кратное чисел a и b., т. е. m и m.

m. Теперь имеем:

Теорема8: Если , то

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

Пусть P[x].- кольцо мн-ов одной перем-ой х над полем Р.

ОПР. f, g P[x]. Многочлены f, g наз ассоциированными f~g, если

Теорема9: f~g или .

Д-во: 1)(=>) f~gf=cg (1) .

(1)

2)(<=) ,

=>f~g

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

Док:

Импликация док-ся анал-но

ОПР: Пусть . Мн-н d(x) наз-ся НОД мн-ов, если: 1) d(x) – общий дел-ль , т. е. 2) d(x) дел-ся на любой общий дел-ль мн-ов . Обозн-ся

Теорема11: Пусть . Если и , то и ассоц-ны.

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

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

.разделим мн/чл f на g с остатком.

,.

Делим g на r1 , ,

Делим r1 на r2 ,.

Заметим, что степени остатков ,являются целыми неотрицательными числами и , поэтому на каком-то шаге деление выполнится без остатка.

, ,

.

Теорема12: НОД мн-ов f и g равен последнему отличному от нуля остатку в алгоритме Евклида, составленному для многочленов f, g, т. е (f, g)=r k

Теорема13: (о линейном предст-ии НОД двух мн-ов)

Пусть Если , то

Опр.: Пусть Мн-н m(x) наз-ся НОК мн-ов, если: 1) m(x) и m(x); 2) m(x) явл-ся дел-ем любого общего кратного мн-ов и . Обозн-ся m(x)=[ ]

Теорема14. [f(x),g(x)]=