Алгоритм евклида для многочленов
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)]=