Курсовая работа: Многочлены над кольцом классов вычетов

Если для полиномов f(x) и g(x) из K[x] существует такой полином , что f(x) = g(x)h(x), то говорят, что полином f(x) делится на полином g(x). Наша ближайшая задача заключается в выяснении вопроса о делимости  на линейный двучлен x - c при .

Прежде всего установим, что всегда осуществимо так называемое деление с остатком:  при . Здесь полином h(x) называется неполным частным, а r - остатком.

Теорема 2. Пусть  и . Найдутся полином  и элемент  такие, что . При этом .

Доказательство.  Естественно искать h(x) в форме . Сравнение коэффициентов многочлена в левой части равенства  = = с коэффициентами многочлена, полученного после раскрытия скобок и приведения подобных, в правой части этого равенства приводит к цепочке равенств

откуда последовательно определяют коэффициенты h(x) и остаток r:

                                                (8)

Равенство  непосредственно следует из равенства  после подстановки в последнее вместо x элемент c.

Теорема доказана. Кроме того, получен очень удобный способ вычисления коэффициентов h(x) и остатка r. Этот способ носит название схемы Горнера. Вычисления удобно располагать в виде таблицы:

Элементы нижней строки вычисляются последовательно по формулам (8): b0 = a0, a каждый последующий элемент равен сумме элемента, находящегося над ним, и предыдущего элемента нижней строки, умноженного на x0.

Элемент c кольца K называется корнем полинома f(x), если .

Следствие (теорема Безу). Многочлен f(x) делится на  в кольце K[x]  тогда и только тогда, когда c - его корень.

Доказательство. Пусть f(x) делится на , т.е. . Тогда .

Пусть . Тогда в равенстве  будет , т.е. . Следствие полностью доказано.

Теорема 3. Число корней ненулевого многочлена не превосходит его степени.

Доказательство. Докажем это утверждение с помощью индукции по степени многочлена. Многочлен нулевой степени вообще не имеет корней, так что для него утверждение теоремы справедливо. Предположим теперь, что утверждение теоремы справедливо для всех многочленов степени , и докажем его для любого многочлена f(x) степени n. Предположим, рассуждая от противного, что x1, x2, ..., xm - корни многочлена f(x), причем . По теореме Безу, f(x) делится на , т.е. , где g(x) - некоторый многочлен степени . Элементы x2, ..., xm кольца K являются корнями многочлена g(x). В самом деле, при  имеем: . Так как , а кольцо K не имеет делителей нуля, то . Таким образом, многочлен g(x) имеет не менее чем  корней, что противоречит предположению индукции, поскольку . Теорема доказана.

Следствие. Многочлен степени не выше n однозначно определяется своими значениями в  точках.

Иначе говоря, существует не более одного многочлена степени не выше n, принимающего в данных (различных) точках  данные значения y1, y2, ..., yn+1.

Доказательство. Предположим, что f(x), g(x) - два многочлена степени не выше n, принимающие одинаковые значения в точках . Рассмотрим многочлен . Степень этого многочлена также не выше, чем n. Так как , то  при , т.е.  - корни многочлена h(x). Согласно теореме 3 h(x) = 0, т.е. f(x) = g(x).

Теорема 4. Если кольцо K бесконечно, то равенство функций, определяемых двумя многочленами из кольца K[x], влечет за собой равенство самих многочленов.

Доказательство. Пусть многочлены  определяют одинаковые функции. Это означает, что  для любого . Обозначим через n наивысшую из степеней многочленов f(x), g(x). Так как кольцо K бесконечно, то в нем найдутся  различных элементов . Согласно нашему предположению, многочлены f(x) и g(x) принимают одинаковые значения в каждой из точек  (как и вообще в любой точке). Следствие теоремы 3 позволяет сделать отсюда вывод, что .

Для конечного кольца K утверждение теоремы 4 неверно. Однако при некоторых дополнительных предположениях и в этом случае оказывается возможным из равенства функций, определяемых двумя многочленами, сделать вывод о равенстве самих многочленов.

6. Вычисление наибольшего общего делителя.

Наибольший общий делитель двух многочленов f и g из кольца R[x] многочленов над полем R может быть найден при помощи алгоритма Евклида. Алгоритм Евклида нахождения наибольшего общего делителя состоит в следующем. Сначала делят с остатком многочлен f на многочлен g, затем многочлен g - на остаток от первого деления, затем остаток от первого деления - на остаток от второго деления и т.д., пока не получится нулевой остаток. Это дает следующую цепочку равенств:

                                                     (9)

причем , поэтому процесс деления конечен. Пусть , т.е. f и g принадлежат одному и тому же главному идеалу . Поэтому их разность , т.е. . Аналогично можно доказать, что ,  и т.д. Таким образом, . Из последнего равенства (21) следует, что , тогда . Поэтому . Следовательно, по теореме 14 , т.е. . Таким образом, последний ненулевой остаток (т.е. rk) и есть наибольший общий делитель многочленов f и g.

Пример. В кольце  многочленов с действительными коэффициентами найдем наибольший общий делитель многочленов ,  . Делим f на g:

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

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

-, -, т. е. , .

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

,

,

.

Отсюда видно, что разность  делится на  при любой операции . Следовательно ,

Теорема 9. Если  - общий делитель многочленов  и , то

,

т.е. обе части сравнения и многочлен можно делить и умножать на один и тот же многочлен.

Доказательство. Так как  - общий делитель многочленов , ,  то существуют многочлены , ,  такие, что: , , . Отсюда и из определения делимости многочленов, учитывая отсутствие делителей нуля в кольце, получим:

.

И теперь эта теорема следует непосредственно из теоремы 7.

9. Классы вычетов.

Определение. Класс всех многочленов, сравнимых с многочленом  по многочлену , называют классом вычетов по многочлену  и обозначают через . Множество всех классов вычетов по многочлену  обозначим

Определим на множестве  операции сложения и умножения.

Определение. Для любых ,  положим:

+=, =.

Таким образом, чтобы сложить (перемножить) классы ,  нужно выбрать из них по одному представителю, сложить (перемножить) их как многочлены и взять класс, содержащий полученный многочлен. В определении в качестве таких представителей выбраны многочлены  и . Однако в классах ,  содержится много других многочленов, и мы заранее не уверены в том, что результат сложения (умножения) классов не зависит от выбора представителей. Если бы результат зависел от выбора представителей, то складывая одни и те же классы, мы могли бы получать разные результаты. Это бы означало, что операции определены некорректно.

Докажем, что определение корректно.

Действительно, пусть, , . Тогда ,  и по теореме 8 имеем:

, ,

т. е. .

Следовательно, результаты операций над классами не зависят от выбора представителей, т. е. операции определены корректно.