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


Примечание	от автора: писали на заказ, пользуйтесь на здоровье, просьба кто будет использовать написать сколько получили
	Загрузить архив:
	Файл: ref-22679.zip (247kb [zip], Скачиваний: 51) скачать

Содержание

1.Определение многочлена. 3

2.Операции над многочленами. 4

3.Кольцо многочленов над область целостности. 8

4.Схема Горнера и теорема Безу. 10

5.Делимость многочленов. 13

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

7.Наименьшее общее кратное. 18

8.Сравнения многочленов по многочлену. 19

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

1. Определение многочлена.

В школьной алгебре одночленом от некоторой буквы x называется алгебраическое выражение вида a - некоторое число, x - буква, m - целое неотрицательное число. Одночлен отождествляется с числом a, так что числа рассматриваются как одночлены. Далее, одночлены называются подобными, если показатели при букве x одинаковы. Подобные одночлены складываются по правилу

Буква x обычно обозначает произвольное число. Иногда x считают переменной, тогда полином задает функцию от x, называемую целой рациональной функцией.

Два полинома называются формально равными, если они, в канонической записи, составлены из одинаковых одночленов. Ясно, что формально равные полиномы равны тождественно, т.е. принимают одинаковые значения при каждом значении буквы x. Обратное утверждение, вообще говоря, неверно.

Наша задача сейчас состоит в том, чтобы несколько расширить понятие полинома. Пусть K - некоторое коммутативное ассоциативное кольцо с единицей, и пусть x - буква, посторонняя для кольца K. Одночленом от буквы x с коэффициентом из K называется выражение m - целое неотрицательное число. Считается, что K являются одночленами частного вида. Выражение рассматривается как формальная запись. Для одночленов естественным образом определяются действие приведения подобных членов и действия умножения многочленом или полиномом от x с коэффициентами из K. Предполагается, что порядок следования одночленов безразличен, подобные одночлены можно соединять, а также вставлять и выбрасывать одночлены с нулевыми коэффициентами. Без нарушения общности можно считать полином записанным в канонической форме (т.е. в порядке убывания степеней) или в порядке возрастания степеней

2. Операции над многочленами.

Два полинома считаются равными, если они составлены в канонической записи из одинаковых одночленов, т.е. в том и только в том случае, если

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

(1)

легко видеть, что операция суммирования (сложения) многочленов обладает такими же свойствами, что и операция сложения элементов кольца K, т.е. ассоциативна, коммутативна; полином, все коэффициенты которого нули, является нейтральным элементом сложения полиномов; для каждого полинома существует ему противоположный, противоположный к полиному является полином

Произведением двух полиномов называется полином, составленный из произведений всех членов первого сомножителя на все члены второго. Здесь снова возможно приведение подобных членов. Таким образом, при равен при и при прост: приводятся такие подобные слагаемые при произведении одночленов и т.е. и при

(2)

Умножение многочленов ассоциативно. Это доказывается следующим образом: если помимо многочленов и дан еще многочлен в произведении будет служить элемент - равное ему число

Умножение многочленов дистрибутивно относительно сложения, это вытекает из равенства в многочлене в многочлене

Нетрудно видеть, что многочлен (где 1 - единица кольца K) играет роль единицы при умножении многочленов. Таким образом, множество полиномов от буквы x с коэффициентами из кольца составляет кольцо по отношению к выше определенным операциям сложения и умножения полиномов (относительно сложения - это коммутативная группа; умножение ассоциативно и дистрибутивно относительно сложения; существует единичный многочлен). Кольцо это коммутативно и ассоциативно. Оно называется кольцом полиномов от буквы x над кольцом K и обозначается K[x].

В данном выше определении одночлена и полинома имеется одно сомнительное место. Именно, было сказано, что x есть буква, посторонняя для кольца K, и не было объяснено, что это значит. Сказать, что x не принадлежит кольцу K - это сказать слишком мало, так как при этом не исключаются нежелательные возможности или и т.д. Однако мы можем избавиться от "сомнительной" буквы x. Для этого рассмотрим бесконечные последовательности элементов кольца K, в которых все элементы, начиная с некоторого, равны нулю. Вводим теперь определения равенства и основных действий.

1. тогда и только тогда, когда i = 0, 1, ..., k, ...

Легко проверяется коммутативность и ассоциативность сложения и умножения и дистрибутивность умножения со сложением. Далее ясно, что и

4. отождествляется с последовательностью

Рассмотрим теперь последовательность (0, 1, 0, ..., 0, ...), обозначив ее буквой x. Тогда x² = (0, 0, 1, 0, ..., 0, ...) и т.д. Поэтому K[x] полиномов.

Итак, при определении многочлена

(3)

существенны лишь коэффициенты

Пусть называется высшим (старшим) членом полинома f(x) и показатель n называется степенью f(x) и обозначается degf. Нулевой полином не имеет высшего члена в смысле данного определения и считается, что он равен нулю. Коэффициент называется свободным членом. Многочлен, старший коэффициент которого равен единице, называется нормированным.

При сложении многочленов и по формуле (1) мы видим, что формула для суммы не содержит членов, степень которых выше, чем n + m. Отсюда следует, что

(4)

(5)

3. Кольцо многочленов над областью целостности.

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

При произведении многочленов степени n и степени m старший член, как следует из формулы (2), равен (это коэффициент при и, значит,

(6)

Эта формула является уточнением неравенства (5) для случая, когда в кольце K нет делителей нуля. Формула (6) также справедлива и тогда, когда один из многочленов f(x), g(x) или они оба равны нулю. Итак, произведение двух ненулевых многочленов - ненулевой многочлен, поэтому справедлива следующая теорема:

Теорема 1. Кольцо многочленов над областью целостности само является областью целостности.

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

Пусть - многочлен с коэффициентами из K. Для любого положим

, (7)

где выражение в правой части понимается как результат операций в кольце K. Получаемый при этом элемент называется значением многочлена f(x) в точке x₀. (Слово "точка" употребляется по аналогии со случаем x₀ можно представлять как точку действительной оси.) Таким образом, каждому элементу x₀ кольца K сопоставляется элемент f(x₀) того же кольца и тем самым определяется функция на K со значениями в K.

Покажем, что сложение и умножение многочленов согласуются с обычными операциями, производимыми над функциями, когда складываются или, соответственно, перемножаются значения функций в каждой точке.

Рассмотрим два многочлена: h(x) = f(x) + g(x) - их сумма. Докажем, что h(x₀)==f(x₀) + g(x₀) для любого =

Пусть теперь - произведение многочленов f(x) и g(x). Докажем, что для любого K (в частности, коммутативностью и ассоциативностью умножения), получим:

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

Вообще говоря, соответствие между многочленами и определяемыми ими функциями не является взаимно однозначным. Однако, если кольцо K бесконечно, то различным многочленам из кольца K[x] всегда соответствуют различные функции.

4. Схема Горнера и теорема Безу.

В кольце многочленов деление в обычном смысле слова, как правило, невозможно. Например, в кольце многочлен x² нельзя разделить на x + 1, т.е. не существует такого многочлена g(x), что x² = g(x)(x+ 1) (если бы такой многочлен существовал, то при x = -1 мы получили бы невозможное равенство

Если для полиномов 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. Этот способ носит название схемы Горнера. Вычисления удобно располагать в виде таблицы:

	a₀	a₁	a₂	...	a_n-1	a_n
c	b₀	b₁	b₂	...	b_n_-1	c

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

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

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

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

Пусть будет

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

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

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

Иначе говоря, существует не более одного многочлена степени не выше n, принимающего в данных (различных) точках данные значения y₁, y₂, ..., y_n₊₁.

Доказательство. Предположим, что 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 неверно. Однако при некоторых дополнительных предположениях и в этом случае оказывается возможным из равенства функций, определяемых двумя многочленами, сделать вывод о равенстве самих многочленов.

5. Делимость многочленов.

Теорема 5 (алгоритм Евклида). Пусть K - коммутативное кольцо, - многочлены степени Предположим, что старший коэффициент многочлена gявляется обратимым элементом вK. Тогда существуют однозначно определенные многочлены такие, что и

Доказательство. Пусть и - единица в K. Применим индукцию по n.

Если и и

Предположим, что теорема доказана для многочленов степени (где (иначе возьмем и имеет степень q₁, r, такие, что и q, r и закончено.

Что касается единственности, то предположим, что и g есть единица, то и, следовательно,

В условии теоремы требуется обратимость элемента b_m. Это можно заменить более слабым условием: необходимо, чтобы элемент a_n делился на в кольце K, так как необходимо произвести, как следует из доказательства теоремы, деление с остатком f(x) на g(x) (имеет степень раз, чтобы получить искомые q и r. Если же умножить f(x) на раз на b_m. Поэтому справедливо следующее следствие.

Следствие. Пусть K - коммутативное кольцо, - многочлены степени где так что Тогда существуют однозначно определенные многочлены такие, что и

Пример . Многочлен нельзя разделить на многочлен Z. Однако, многочлен уже можно разделить на g(x) с остатком. Произведем деление "уголком".

24x³ + 16x - 8 2x+3

24x³ +36x² 12x² -18x -35

-36x² + 16x -8

-36x² -54x

-70x - 8

-70x - 105

Итак, соответствует многочлену f₁(x) из этой теоремы.

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

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

(9)

причем f и gпринадлежат одному и тому же главному идеалу и т.д. Таким образом, последний ненулевой остаток (т.е. r_k) и есть наибольший общий делитель многочленов f иg.

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

Для удобства умножим полученный остаток на

Полученный остаток разделим на 9 и выполним третье деление:

Поскольку остаток равен нулю, то

Наибольший общий делитель нескольких многочленов f₁, f₂, ..., f_m может быть найден индуктивным способом на основании следующей формулы:

(10)

Для того чтобы найти наибольший общий делитель многочленов и т.д.; и будет искомым наибольшим делителем.

Докажем формулу (10). Согласно определению наибольшего общего делителя, делители многочлена - это в точности общие делители многочленов и f_m совпадает с совокупностью всех общих делителей многочленов и f_m; отсюда и следует формула (10).

Наибольший общий делитель d двух многочленов над полем R, а также всякий многочлен, кратный d, может быть представлен в виде линейным выражением данного многочлена через многочлены f и g.

Для нахождения линейного выражения наибольшего общего делителя d можно воспользоваться алгоритмом Евклида. В самом деле, первое из равенств (9) дает следующее линейное выражение многочлена r₁ через f и g: r₂:

Пример. Найдем линейное выражение наибольшего общего делителя d многочленов f и g из примера 14.

Результаты делений с остатком, выполненных при решении предыдущего примера, показывают, что

Линейное выражение любого многочлена h, кратного d, может быть найдено, исходя из линейного выражения d. А именно: пусть и

На практике линейное выражение многочлена h удобнее искать не с помощью алгоритма Евклида, а методом неопределенных коэффициентов. Запишем искомые многочлены u и v в общем виде с неопределенными (неизвестными) коэффициентами. Приравнивая коэффициенты при одинаковых степенях x в равенстве u и v. Легко видеть, что эти уравнения будут линейными.

7. Наименьшее общее кратное.

Наименьшим общим кратным многочленов над полем R называется многочлен h, обладающий следующими свойствами: 1) h делится на каждый из многочленов h делит любое общее кратное многочленов

Теорема Для двух многочленов fиgнаименьшее общее кратное [f, g] связано с наибольшим общим делителем (f, g) соотношением

(11)

Доказательство. Для доказательства формулы (23) положим и рассмотрим многочлен

(12)

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

Из формулы (12) вытекает

Следствие. Наименьшее общее кратное двух взаимно простых многочленов равно их произведению.

8. Сравнения многочленов по многочлену.

Пусть, например, - кольцо вычетов по простому модулю p. Два многочлена будем называть эквивалентными, если они определяют одну и ту же функцию на имеется p элементов, то из следствия теоремы 3 непосредственно вытекает следующее утверждение:

Теорема 6. Если многочлены имеющие степень не выше чем эквивалентны, то они равны.

Определение. Два многочлена и называются сравнимыми по многочлену дают одинаковые остатки

Пример. Многочлены и сравнимы по многочлену

Теорема 7. Для любых многочленов и

Доказательство. Разделим многочлены и с остатком на

Если и разность делится на

следует, что

Теорема 8. Для многочленов

Где - любая из операций (т.е. сравнения можно почленно складывать, вычитать и перемножать).

Доказательство. Из условия, согласно теореме 7, имеем

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

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

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

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

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

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

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

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

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

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

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

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

Действительно, пусть, и по теореме 8 имеем:

т. е.

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