Xreferat.com » Рефераты по математике » Многочлены над кольцом классов вычетов

Многочлены над кольцом классов вычетов

над кольцом классов вычетов" width="141" height="41" />        Многочлены над кольцом классов вычетов

Многочлены над кольцом классов вычетов                                    Многочлены над кольцом классов вычетов

Многочлены над кольцом классов вычетов                                    Многочлены над кольцом классов вычетов

                                                Многочлены над кольцом классов вычетов

Для удобства умножим полученный остаток на Многочлены над кольцом классов вычетов. При этом последующие остатки также умножатся на некоторые числа, отличные от нуля, что несущественно при нахождении наибольшего общего делителя, так как он находится с точностью до константы. Выполним второе деление:

Многочлены над кольцом классов вычетов                                   Многочлены над кольцом классов вычетов     Многочлены над кольцом классов вычетов

Многочлены над кольцом классов вычетовМногочлены над кольцом классов вычетовМногочлены над кольцом классов вычетов                                   Многочлены над кольцом классов вычетов          Многочлены над кольцом классов вычетов

Многочлены над кольцом классов вычетов                                             Многочлены над кольцом классов вычетов

Многочлены над кольцом классов вычетов                                             Многочлены над кольцом классов вычетов

                                                            Многочлены над кольцом классов вычетов

Полученный остаток разделим на 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, имеем

Многочлены над кольцом классов вычетов-Многочлены над кольцом классов вычетовМногочлены над кольцом классов вычетов, Многочлены над кольцом классов вычетов-Многочлены над кольцом классов вычетовМногочлены над кольцом классов вычетов, т. е. Многочлены над кольцом классов вычетов, Многочлены над кольцом классов вычетов.

Складывая, вычитая и перемножая последние равенства, получим:

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: