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

Курсовая работа по математике

Ставропольский государственный институт

Ставрополь, 2004 г.

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, в которых всеэлементы, начиная с некоторого, равны нулю. Вводим теперь определения равенстваи основных действий.

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

/>. Ясно, что требование об обращениив нуль всех членов, начиная с некоторого, сохраняется при сложении.

/>. Здесь тоже сохраняется требованиеоб обращении в нуль всех членов, начиная с некоторого места.

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

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

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

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

/>                                  (3)

существенны лишь коэффициенты />, и поэтому можно было бы писатьвместо (1) последовательность />. Однако, в конечном счете, записьмногочлена в виде выражения (3) оказывается более удобной.

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

При сложении многочленов /> и /> по формуле (1) мы видим, чтоформула для суммы не содержит членов, степень которых выше, чем />, а формула (2) дляпроизведения — членов, степень которых выше, чем 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)в точке x0. (Слово «точка» употребляется по аналогии со случаем />, когда x0 можнопредставлять как точку действительной оси.) Таким образом, каждому элементу x0кольца K сопоставляется элемент f(x0) того же кольца и тем самым определяетсяфункция на K со значениями в K.

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

Рассмотрим два многочлена: />, />. Пусть h(x) = f(x) + g(x) — ихсумма. Докажем, что h(x0)=  =f(x0) + g(x0) для любого />. В соответствии с формулой (1) />  /> = /> />, где />, что итребовалось доказать.

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

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

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

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

В кольце многочленов деление в обычном смысле слова,как правило, невозможно. Например, в кольце /> многочлен x2 нельзя разделить на x+ 1, т.е. не существует такого многочлена g(x), что x2 = 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. Этот способ носит названиесхемы Горнера. Вычисления удобно располагать в виде таблицы:

a0 a1 a2 ... an-1 an c b0 b1 b2 ... bn-1 c

Элементы нижней строки вычисляются последовательно поформулам (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 имеем:

/>, />,

т. е. />/>/>/>.

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

еще рефераты
Еще работы по математике