Многочлены над кольцом классов вычетов
![]()
![]()
![]()
Для удобства умножим полученный остаток на
. При этом
последующие остатки также умножатся на некоторые числа, отличные от нуля, что
несущественно при нахождении наибольшего общего делителя, так как он находится
с точностью до константы. Выполним второе деление:
![]()
![]()
![]()
![]()
![]()
![]()
![]()
Полученный остаток разделим на 9 и выполним третье деление:
![]()
![]()
![]()
![]()
![]()
![]()
0
Поскольку остаток равен нулю, то
.
Наибольший общий делитель нескольких многочленов f1, f2, ..., fm может быть найден индуктивным способом на основании следующей формулы:
. (10)
Для того чтобы найти наибольший общий делитель
многочленов
, следует,
согласно этой формуле, найти сначала
, затем
и т.д.;
и будет искомым наибольшим делителем.
Докажем формулу (10). Согласно определению наибольшего
общего делителя, делители многочлена
- это в точности общие делители многочленов
. Поэтому
совокупность всех общих делителей многочленов
и fm совпадает с совокупностью всех общих
делителей многочленов
и fm; отсюда и следует формула (10).
Наибольший общий делитель d двух многочленов
над полем R, а также всякий многочлен, кратный
d, может быть представлен в виде
, где
. Такое
представление мы называем линейным выражением данного многочлена через
многочлены f и g.
Для нахождения линейного выражения наибольшего общего
делителя d можно воспользоваться алгоритмом Евклида. В самом деле, первое из
равенств (9) дает следующее линейное выражение многочлена r1 через f и g:
. Подставляя
его во второе равенство, получаем линейное выражение многочлена r2:
. Продолжая
так дальше, получаем, в конце концов, линейное выражение наибольшего общего
делителя
.
Пример. Найдем линейное выражение наибольшего общего делителя d многочленов f и g из примера 14.
Результаты делений с остатком, выполненных при решении
предыдущего примера, показывают, что
,
. Отсюда
находим:
,
. Таким
образом,
,
.
Линейное выражение любого многочлена h, кратного d,
может быть найдено, исходя из линейного выражения d. А именно: пусть
и
. Тогда
.
На практике линейное выражение многочлена h удобнее
искать не с помощью алгоритма Евклида, а методом неопределенных коэффициентов.
Запишем искомые многочлены u и v в общем виде с неопределенными (неизвестными)
коэффициентами. Приравнивая коэффициенты при одинаковых степенях x в равенстве
, получим
систему уравнений для коэффициентов многочленов u и v. Легко видеть, что эти
уравнения будут линейными.
7. Наименьшее общее кратное.
Наименьшим общим кратным многочленов
над полем R называется многочлен h, обладающий
следующими свойствами: 1) h делится на каждый из многочленов
, т.е.
является их общим кратным; 2) h делит любое общее кратное многочленов
.
Теорема Для двух многочленов f и g наименьшее общее кратное [f, g] связано с наибольшим общим делителем (f, g) соотношением
(11)
Доказательство. Для доказательства формулы (23)
положим
,
,
,
и рассмотрим многочлен
(12)
Многочлен
является общим кратным многочленов f, g и,
следовательно, делится на h. Теперь рассмотрим многочлен
. Равенства
,
показывают, что
- общий делитель многочленов f, g;
следовательно,
делит d, т.е.
, где q -
некоторый многочлен. Отсюда получаем:
, т.е.
. Стало быть,
h делится на
. Таким
образом, h и
ассоциированы, т.е.
, где
,
. Из (24)
получаем тогда, что
, что и
требовалось доказать.
Из формулы (12) вытекает
Следствие. Наименьшее общее кратное двух взаимно простых многочленов равно их произведению.
8. Сравнения многочленов по многочлену.
Пусть, например,
- кольцо вычетов по простому модулю p. Два
многочлена
будем называть эквивалентными, если они
определяют одну и ту же функцию на
. Так как в
кольце
имеется p элементов, то из следствия теоремы 3
непосредственно вытекает следующее утверждение:
Теорема 6. Если многочлены
, имеющие
степень не выше чем
,
эквивалентны, то они равны.
Определение. Два многочлена
и
называются сравнимыми по многочлену
, если они при
делении на
дают одинаковые остатки
.
Пример. Многочлены
и
сравнимы по многочлену
, так как они
имеют одинаковый остаток при делении это 1.
Теорема 7. Для любых многочленов
и
:
.
Доказательство. Разделим многочлены
и
с остатком на
:
,
,
.
Если
, то
и разность
-![]()
делится на
. Обратно,
если
, то из
равенства
-![]()
следует, что
. А так как
, то по
свойству отношения делимости в кольце имеем
, т.е.
, или
.
Теорема 8. Для
многочленов
,
,
, ![]()
,
,
Где
- любая из операций
(т.е. сравнения можно почленно складывать,
вычитать и перемножать).
Доказательство. Из условия, согласно теореме 7, имеем
-![]()
,
-![]()
, т. е.
,
.
Складывая, вычитая и перемножая последние равенства, получим: