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

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

Подобные одночлены складываются по правилу Буква 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 , ... 2. 3. Легко проверяется коммутативность и ассоциативность сложения и умножения и дистрибутивность умножения со сложением. Далее ясно, что и 4. отождествляется с последовательностью Рассмотрим теперь последовательность (0, 1, 0, ..., 0, ...), обозначив ее буквой x . Тогда x 2 = (0, 0, 1, 0, ..., 0, ...) и т.д.

Поэтому K [ x ] полиномов. Итак, при определении многочлена (3) существенны лишь коэффициенты Пусть называется высшим (старшим) членом полинома f ( x ) и показатель n называется степенью f ( x ) и обозначается deg f . Нулевой полином не имеет высшего члена в смысле данного определения и считается, что он равен нулю.

Коэффициент называется свободным членом.

Многочлен, старший коэффициент которого равен единице, называется нормированным. При сложении многочленов и по формуле (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 0 . (Слово 'точка' употребляется по аналогии со случаем x 0 можно представлять как точку действительной оси.) Таким образом, каждому элементу x 0 кольца K сопоставляется элемент f ( x 0 ) того же кольца и тем самым определяется функция на K со значениями в K . Покажем, что сложение и умножение многочленов согласуются с обычными операциями, производимыми над функциями, когда складываются или, соответственно, перемножаются значения функций в каждой точке.

Рассмотрим два многочлена: h ( x ) = f ( x ) + g ( x ) - их сумма.

Докажем, что h ( x 0 )= = f ( x 0 ) + g ( x 0 ) для любого = Пусть теперь - произведение многочленов f ( x ) и g ( x ). Докажем, что для любого K (в частности, коммутативностью и ассоциативностью умножения), получим: Таким образом, функция, определяемая суммой (соответственно произведением) двух многочленов, есть сумма (соответственно произведение) функций, определяемых этими многочленами.

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

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

Например, в кольце многочлен x 2 нельзя разделить на x + 1, т.е. не существует такого многочлена g ( x ), что x 2 = 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 0	a 1	a 2	...	a n-1	a n
c	b 0	b 1	b 2	...	b n -1	c

Элементы нижней строки вычисляются последовательно по формулам (8): b 0 = a 0 , a каждый последующий элемент равен сумме элемента, находящегося над ним, и предыдущего элемента нижней строки, умноженного на x 0 . Элемент c кольца K называется корнем полинома f ( x ), если Следствие (теорема Безу). Многочлен f ( x ) делится на в кольце K [ x ] тогда и только тогда, когда c - его корень.

Доказательство . Пусть f ( x ) делится на Пусть будет Теорема 3 . Число корней ненулевого многочлена не превосходит его степени.

Доказательство . Докажем это утверждение с помощью индукции по степени многочлена.

Многочлен нулевой степени вообще не имеет корней, так что для него утверждение теоремы справедливо.

Предположим теперь, что утверждение теоремы справедливо для всех многочленов степени f ( x ) степени n . Предположим, рассуждая от противного, что x 1 , x 2 , ..., x m - корни многочлена f ( x ), причем f ( x ) делится на g ( x ) - некоторый многочлен степени x 2 , ..., x m кольца K являются корнями многочлена g ( x ). В самом деле, при имеем: K не имеет делителей нуля, то g ( x ) имеет не менее чем корней, что противоречит предположению индукции, поскольку Следствие . Многочлен степени не выше n однозначно определяется своими значениями в точках. Иначе говоря, существует не более одного многочлена степени не выше n , принимающего в данных (различных) точках данные значения y 1 , y 2 , ..., y n +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 неверно.

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

Теорема 5 (алгоритм Евклида). Пусть K - коммутативное кольцо, - многочлены степени Предположим, что старший коэффициент многочлена g является обратимым элементом в K . Тогда существуют однозначно определенные многочлены такие, что и Доказательство . Пусть и - единица в K . Применим индукцию по n . Если и и Предположим, что теорема доказана для многочленов степени (где (иначе возьмем и имеет степень q 1 , r , такие, что и q , r и закончено. Что касается единственности, то предположим, что и g есть единица, то и, следовательно, В условии теоремы требуется обратимость элемента b m . Это можно заменить более слабым условием: необходимо, чтобы элемент a n делился на в кольце K , так как необходимо произвести, как следует из доказательства теоремы, деление с остатком f ( x ) на g ( x ) ( имеет степень раз, чтобы получить искомые q и r . Если же умножить f ( x ) на раз на b m . Поэтому справедливо следующее следствие.

Следствие . Пусть K - коммутативное кольцо, - многочлены степени где так что Тогда существуют однозначно определенные многочлены такие, что и Пример . Многочлен нельзя разделить на многочлен Z . Однако, многочлен уже можно разделить на g ( x ) с остатком.

Произведем деление 'уголком'.

24 x 3 + 16 x - 8 2 x +3 24 x 3 +36 x 2 12 x 2 -18 x -35 -36 x 2 + 16 x -8 -36 x 2 - 54 x -70 x - 8 -70 x - 105 97 Итак, соответствует многочлену f 1 ( x ) из этой теоремы. 6. Вычисление наибольшего общего делителя.

Наибольший общий делитель двух многочленов f и g из кольца R [ x ] многочленов над полем R может быть найден при помощи алгоритма Евклида.

Алгоритм Евклида нахождения наибольшего общего делителя состоит в следующем.

Сначала делят с остатком многочлен f на многочлен g , затем многочлен g - на остаток от первого деления, затем остаток от первого деления - на остаток от второго деления и т.д., пока не получится нулевой остаток. Это дает следующую цепочку равенств: (9) причем f и g принадлежат одному и тому же главному идеалу и т.д. Таким образом, последний ненулевой остаток (т.е. r k ) и есть наибольший общий делитель многочленов f и g . Пример . В кольце многочленов с действительными коэффициентами найдем наибольший общий делитель многочленов f на g : Для удобства умножим полученный остаток на Полученный остаток разделим на 9 и выполним третье деление: 0 Поскольку остаток равен нулю, то Наибольший общий делитель нескольких многочленов f 1 , f 2 , ..., f m может быть найден индуктивным способом на основании следующей формулы: (10) Для того чтобы найти наибольший общий делитель многочленов и т.д.; и будет искомым наибольшим делителем.

Докажем формулу (10). Согласно определению наибольшего общего делителя, делители многочлена - это в точности общие делители многочленов и f m совпадает с совокупностью всех общих делителей многочленов и f m ; отсюда и следует формула (10). Наибольший общий делитель d двух многочленов над полем R , а также всякий многочлен, кратный d , может быть представлен в виде линейным выражением данного многочлена через многочлены f и g . Для нахождения линейного выражения наибольшего общего делителя d можно воспользоваться алгоритмом Евклида. В самом деле, первое из равенств (9) дает следующее линейное выражение многочлена r 1 через f и g : r 2 : Пример . Найдем линейное выражение наибольшего общего делителя 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. Классы вычетов.

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

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

оценка жилой недвижимости в Смоленске
оценка стоимости дачи в Курске
оценка стоимости зданий в Твери