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

--PAGE_BREAK--с коэффициентами многочлена, полученного после раскрытия скобок и приведения подобных, в правой части этого равенства приводит к цепочке равенств

<img width=«123» height=«143» src=«ref-1_593367910-1657.coolpic» v:shapes="_x0000_i1160">

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

<img width=«123» height=«143» src=«ref-1_593369567-1648.coolpic» v:shapes="_x0000_i1161">                                                (8)

Равенство <img width=«60» height=«21» src=«ref-1_593364840-494.coolpic» v:shapes="_x0000_i1162"> непосредственно следует из равенства <img width=«148» height=«21» src=«ref-1_593360131-823.coolpic» v:shapes="_x0000_i1163"> после подстановки в последнее вместо 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), если <img width=«60» height=«21» src=«ref-1_593372532-481.coolpic» v:shapes="_x0000_i1164">.

Следствие (теорема Безу). Многочлен f(x) делится на <img width=«36» height=«13» src=«ref-1_593373013-331.coolpic» v:shapes="_x0000_i1165"> в кольце K[x]  тогда и только тогда, когда c — его корень.

Доказательство. Пусть f(x) делится на <img width=«36» height=«13» src=«ref-1_593373013-331.coolpic» v:shapes="_x0000_i1166">, т.е. <img width=«125» height=«21» src=«ref-1_593373675-714.coolpic» v:shapes="_x0000_i1167">. Тогда <img width=«60» height=«21» src=«ref-1_593372532-481.coolpic» v:shapes="_x0000_i1168">.

Пусть <img width=«60» height=«21» src=«ref-1_593372532-481.coolpic» v:shapes="_x0000_i1169">. Тогда в равенстве <img width=«148» height=«21» src=«ref-1_593360131-823.coolpic» v:shapes="_x0000_i1170"> будет <img width=«84» height=«21» src=«ref-1_593376174-556.coolpic» v:shapes="_x0000_i1171">, т.е. <img width=«125» height=«21» src=«ref-1_593373675-714.coolpic» v:shapes="_x0000_i1172">. Следствие полностью доказано.

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

Доказательство. Докажем это утверждение с помощью индукции по степени многочлена. Многочлен нулевой степени вообще не имеет корней, так что для него утверждение теоремы справедливо. Предположим теперь, что утверждение теоремы справедливо для всех многочленов степени <img width=«33» height=«16» src=«ref-1_593377444-352.coolpic» v:shapes="_x0000_i1173">, и докажем его для любого многочлена f(x) степени n. Предположим, рассуждая от противного, что x1, x2, ..., xm — корни многочлена f(x), причем <img width=«41» height=«15» src=«ref-1_593377796-452.coolpic» v:shapes="_x0000_i1174">. По теореме Безу, f(x) делится на <img width=«41» height=«21» src=«ref-1_593378248-346.coolpic» v:shapes="_x0000_i1175">, т.е. <img width=«133» height=«21» src=«ref-1_593378594-721.coolpic» v:shapes="_x0000_i1176">, где g(x) — некоторый многочлен степени <img width=«33» height=«16» src=«ref-1_593377444-352.coolpic» v:shapes="_x0000_i1177">. Элементы x2, ..., xm кольца K являются корнями многочлена g(x). В самом деле, при <img width=«71» height=«19» src=«ref-1_593379667-516.coolpic» v:shapes="_x0000_i1178"> имеем: <img width=«149» height=«21» src=«ref-1_593380183-777.coolpic» v:shapes="_x0000_i1179">. Так как <img width=«73» height=«21» src=«ref-1_593380960-509.coolpic» v:shapes="_x0000_i1180">, а кольцо K не имеет делителей нуля, то <img width=«65» height=«21» src=«ref-1_593381469-546.coolpic» v:shapes="_x0000_i1181">. Таким образом, многочлен g(x) имеет не менее чем <img width=«37» height=«16» src=«ref-1_593382015-376.coolpic» v:shapes="_x0000_i1182"> корней, что противоречит предположению индукции, поскольку <img width=«156» height=«21» src=«ref-1_593382391-833.coolpic» v:shapes="_x0000_i1183">. Теорема доказана.

Следствие. Многочлен степени не выше n однозначно определяется своими значениями в <img width=«33» height=«16» src=«ref-1_593383224-361.coolpic» v:shapes="_x0000_i1184"> точках.

Иначе говоря, существует не более одного многочлена степени не выше n, принимающего в данных (различных) точках <img width=«100» height=«21» src=«ref-1_593383585-543.coolpic» v:shapes="_x0000_i1185"> данные значения y1, y2, ..., yn+1.

Доказательство. Предположим, что f(x), g(x) — два многочлена степени не выше n, принимающие одинаковые значения в точках <img width=«100» height=«21» src=«ref-1_593383585-543.coolpic» v:shapes="_x0000_i1186">. Рассмотрим многочлен <img width=«128» height=«21» src=«ref-1_593384671-728.coolpic» v:shapes="_x0000_i1187">. Степень этого многочлена также не выше, чем n. Так как <img width=«93» height=«21» src=«ref-1_593385399-595.coolpic» v:shapes="_x0000_i1188">, то <img width=«63» height=«21» src=«ref-1_593385994-588.coolpic» v:shapes="_x0000_i1189"> при <img width=«115» height=«19» src=«ref-1_593386582-577.coolpic» v:shapes="_x0000_i1190">, т.е. <img width=«100» height=«21» src=«ref-1_593383585-543.coolpic» v:shapes="_x0000_i1191">  — корни многочлена h(x). Согласно теореме 3 h(x) = 0, т.е. f(x) = g(x).

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

Доказательство. Пусть многочлены <img width=«121» height=«21» src=«ref-1_593387702-830.coolpic» v:shapes="_x0000_i1192"> определяют одинаковые функции. Это означает, что <img width=«97» height=«21» src=«ref-1_593388532-638.coolpic» v:shapes="_x0000_i1193"> для любого <img width=«49» height=«21» src=«ref-1_593340754-497.coolpic» v:shapes="_x0000_i1194">. Обозначим через n наивысшую из степеней многочленов f(x), g(x). Так как кольцо K бесконечно, то в нем найдутся <img width=«33» height=«16» src=«ref-1_593383224-361.coolpic» v:shapes="_x0000_i1195"> различных элементов <img width=«100» height=«21» src=«ref-1_593383585-543.coolpic» v:shapes="_x0000_i1196">. Согласно нашему предположению, многочлены f(x) и g(x) принимают одинаковые значения в каждой из точек <img width=«100» height=«21» src=«ref-1_593383585-543.coolpic» v:shapes="_x0000_i1197"> (как и вообще в любой точке). Следствие теоремы 3 позволяет сделать отсюда вывод, что <img width=«84» height=«21» src=«ref-1_593391114-585.coolpic» v:shapes="_x0000_i1198">.

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

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

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

<img width=«115» height=«143» src=«ref-1_593391699-1769.coolpic» v:shapes="_x0000_i1199">                                                     (9)

причем <img width=«253» height=«21» src=«ref-1_593393468-993.coolpic» v:shapes="_x0000_i1200">, поэтому процесс деления конечен. Пусть <img width=«71» height=«21» src=«ref-1_593394461-584.coolpic» v:shapes="_x0000_i1201">, т.е. f и g принадлежат одному и тому же главному идеалу <img width=«25» height=«21» src=«ref-1_593395045-431.coolpic» v:shapes="_x0000_i1202">. Поэтому их разность <img width=«120» height=«21» src=«ref-1_593395476-767.coolpic» v:shapes="_x0000_i1203">, т.е. <img width=«69» height=«21» src=«ref-1_593396243-596.coolpic» v:shapes="_x0000_i1204">. Аналогично можно доказать, что <img width=«72» height=«21» src=«ref-1_593396839-603.coolpic» v:shapes="_x0000_i1205">, <img width=«73» height=«21» src=«ref-1_593397442-614.coolpic» v:shapes="_x0000_i1206"> и т.д. Таким образом, <img width=«84» height=«21» src=«ref-1_593398056-637.coolpic» v:shapes="_x0000_i1207">. Из последнего равенства (21) следует, что <img width=«43» height=«23» src=«ref-1_593398693-444.coolpic» v:shapes="_x0000_i1208">, тогда <img width=«83» height=«21» src=«ref-1_593399137-599.coolpic» v:shapes="_x0000_i1209">. Поэтому <img width=«123» height=«21» src=«ref-1_593399736-662.coolpic» v:shapes="_x0000_i1210">. Следовательно, по теореме 14 <img width=«99» height=«21» src=«ref-1_593400398-623.coolpic» v:shapes="_x0000_i1211">, т.е. <img width=«68» height=«21» src=«ref-1_593401021-610.coolpic» v:shapes="_x0000_i1212">. Таким образом, последний ненулевой остаток (т.е. rk) и есть наибольший общий делитель многочленов f и g.

Пример. В кольце <img width=«35» height=«20» src=«ref-1_593357414-421.coolpic» v:shapes="_x0000_i1213"> многочленов с действительными коэффициентами найдем наибольший общий делитель многочленов <img width=«176» height=«24» src=«ref-1_593402052-772.coolpic» v:shapes="_x0000_i1214">, <img width=«115» height=«24» src=«ref-1_593402824-675.coolpic» v:shapes="_x0000_i1215"> <img width=«56» height=«16» src=«ref-1_593403499-455.coolpic» v:shapes="_x0000_i1216">. Делим f на g:

<img width=«147» height=«3» src=«ref-1_593403954-167.coolpic» v:shapes="_x0000_s1026"><img width=«3» height=«70» src=«ref-1_593404121-162.coolpic» v:shapes="_x0000_s1027">                               <img width=«147» height=«20» src=«ref-1_593404283-698.coolpic» v:shapes="_x0000_i1217">      <img width=«129» height=«20» src=«ref-1_593404981-717.coolpic» v:shapes="_x0000_i1218">

<img width=«146» height=«2» src=«ref-1_593405698-157.coolpic» v:shapes="_x0000_s1028"><img width=«12» height=«2» src=«ref-1_593405855-159.coolpic» v:shapes="_x0000_s1029">                               <img width=«141» height=«41» src=«ref-1_593406014-854.coolpic» v:shapes="_x0000_i1219">        <img width=«51» height=«41» src=«ref-1_593406868-524.coolpic» v:shapes="_x0000_i1220">

<img width=«12» height=«2» src=«ref-1_593407392-156.coolpic» v:shapes="_x0000_s1030">                                    <img width=«143» height=«41» src=«ref-1_593407548-766.coolpic» v:shapes="_x0000_i1221">

<img width=«175» height=«2» src=«ref-1_593408314-165.coolpic» v:shapes="_x0000_s1031">                                    <img width=«157» height=«41» src=«ref-1_593408479-899.coolpic» v:shapes="_x0000_i1222">

                                                <img width=«123» height=«41» src=«ref-1_593409378-868.coolpic» v:shapes="_x0000_i1223">

Для удобства умножим полученный остаток на <img width=«28» height=«41» src=«ref-1_593410246-401.coolpic» v:shapes="_x0000_i1224">. При этом последующие остатки также умножатся на некоторые числа, отличные от нуля, что несущественно при нахождении наибольшего общего делителя, так как он находится с точностью до константы. Выполним второе деление:

<img width=«3» height=«50» src=«ref-1_593410647-165.coolpic» v:shapes="_x0000_s1032">                                   <img width=«129» height=«20» src=«ref-1_593404981-717.coolpic» v:shapes="_x0000_i1225">     <img width=«75» height=«20» src=«ref-1_593411529-546.coolpic» v:shapes="_x0000_i1226">

<img width=«127» height=«2» src=«ref-1_593412075-157.coolpic» v:shapes="_x0000_s1033"><img width=«12» height=«2» src=«ref-1_593412232-161.coolpic» v:shapes="_x0000_s1034"><img width=«89» height=«2» src=«ref-1_593412393-162.coolpic» v:shapes="_x0000_s1035">                                   <img width=«113» height=«20» src=«ref-1_593412555-672.coolpic» v:shapes="_x0000_i1227">          <img width=«43» height=«16» src=«ref-1_593413227-421.coolpic» v:shapes="_x0000_i1228">

<img width=«12» height=«3» src=«ref-1_593413648-161.coolpic» v:shapes="_x0000_s1036">                                             <img width=«101» height=«20» src=«ref-1_593413809-619.coolpic» v:shapes="_x0000_i1229">

<img width=«108» height=«2» src=«ref-1_593414428-162.coolpic» v:shapes="_x0000_s1037">                                             <img width=«111» height=«20» src=«ref-1_593414590-650.coolpic» v:shapes="_x0000_i1230">

                                                            <img width=«53» height=«16» src=«ref-1_593415240-499.coolpic» v:shapes="_x0000_i1231">

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

<img width=«12» height=«2» src=«ref-1_593415739-160.coolpic» v:shapes="_x0000_s1038"><img width=«41» height=«2» src=«ref-1_593415899-161.coolpic» v:shapes="_x0000_s1039"><img width=«2» height=«50» src=«ref-1_593416060-157.coolpic» v:shapes="_x0000_s1040">                                               <img width=«75» height=«20» src=«ref-1_593411529-546.coolpic» v:shapes="_x0000_i1232">   <img width=«36» height=«16» src=«ref-1_593416763-390.coolpic» v:shapes="_x0000_i1233">

<img width=«80» height=«2» src=«ref-1_593417153-165.coolpic» v:shapes="_x0000_s1041">                                               <img width=«53» height=«20» src=«ref-1_593417318-464.coolpic» v:shapes="_x0000_i1234">         <img width=«37» height=«16» src=«ref-1_593417782-381.coolpic» v:shapes="_x0000_i1235">

<img width=«12» height=«2» src=«ref-1_593418163-160.coolpic» v:shapes="_x0000_s1042">                                                      <img width=«45» height=«16» src=«ref-1_593418323-462.coolpic» v:shapes="_x0000_i1236">

<img width=«51» height=«2» src=«ref-1_593418785-157.coolpic» v:shapes="_x0000_s1043">                                                      <img width=«45» height=«16» src=«ref-1_593418323-462.coolpic» v:shapes="_x0000_i1237">

                                                           0

Поскольку остаток равен нулю, то <img width=«92» height=«21» src=«ref-1_593419404-620.coolpic» v:shapes="_x0000_i1238">.

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

<img width=«293» height=«21» src=«ref-1_593420024-965.coolpic» v:shapes="_x0000_i1239">.                           (10)

Для того чтобы найти наибольший общий делитель многочленов <img width=«123» height=«21» src=«ref-1_593420989-678.coolpic» v:shapes="_x0000_i1240">, следует, согласно этой формуле, найти сначала <img width=«87» height=«21» src=«ref-1_593421667-647.coolpic» v:shapes="_x0000_i1241">, затем <img width=«87» height=«21» src=«ref-1_593422314-649.coolpic» v:shapes="_x0000_i1242"> и т.д.; <img width=«103» height=«21» src=«ref-1_593422963-688.coolpic» v:shapes="_x0000_i1243"> и будет искомым наибольшим делителем.

Докажем формулу (10). Согласно определению наибольшего общего делителя, делители многочлена <img width=«111» height=«21» src=«ref-1_593423651-700.coolpic» v:shapes="_x0000_i1244">  — это в точности общие делители многочленов <img width=«97» height=«21» src=«ref-1_593424351-632.coolpic» v:shapes="_x0000_i1245">. Поэтому совокупность всех общих делителей многочленов <img width=«111» height=«21» src=«ref-1_593423651-700.coolpic» v:shapes="_x0000_i1246"> и fm совпадает с совокупностью всех общих делителей многочленов <img width=«97» height=«21» src=«ref-1_593424351-632.coolpic» v:shapes="_x0000_i1247"> и fm; отсюда и следует формула (10).

Наибольший общий делитель d двух многочленов <img width=«77» height=«21» src=«ref-1_593426315-608.coolpic» v:shapes="_x0000_i1248"> над полем R, а также всякий многочлен, кратный d, может быть представлен в виде <img width=«52» height=«21» src=«ref-1_593426923-524.coolpic» v:shapes="_x0000_i1249">, где <img width=«72» height=«20» src=«ref-1_593427447-619.coolpic» v:shapes="_x0000_i1250">. Такое представление мы называем линейным выражением данного многочлена через многочлены f и g.

Для нахождения линейного выражения наибольшего общего делителя d можно воспользоваться алгоритмом Евклида. В самом деле, первое из равенств (9) дает следующее линейное выражение многочлена r1 через f и g: <img width=«83» height=«21» src=«ref-1_593428066-577.coolpic» v:shapes="_x0000_i1251">. Подставляя его во второе равенство, получаем линейное выражение многочлена r2: <img width=«151» height=«21» src=«ref-1_593428643-722.coolpic» v:shapes="_x0000_i1252"> <img width=«88» height=«21» src=«ref-1_593429365-628.coolpic» v:shapes="_x0000_i1253">. Продолжая так дальше, получаем, в конце концов, линейное выражение наибольшего общего делителя <img width=«43» height=«21» src=«ref-1_593429993-470.coolpic» v:shapes="_x0000_i1254">.

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

Результаты делений с остатком, выполненных при решении предыдущего примера, показывают, что <img width=«215» height=«45» src=«ref-1_593430463-1414.coolpic» v:shapes="_x0000_i1255">, <img width=«229» height=«24» src=«ref-1_593431877-1083.coolpic» v:shapes="_x0000_i1256">. Отсюда находим: <img width=«213» height=«41» src=«ref-1_593432960-1174.coolpic» v:shapes="_x0000_i1257">,  <img width=«248» height=«41» src=«ref-1_593434134-1201.coolpic» v:shapes="_x0000_i1258"> <img width=«456» height=«41» src=«ref-1_593435335-227.coolpic» v:shapes="_x0000_i1259">. Таким образом, <img width=«91» height=«41» src=«ref-1_593435562-725.coolpic» v:shapes="_x0000_i1260">, <img width=«112» height=«41» src=«ref-1_593436287-751.coolpic» v:shapes="_x0000_i1261">.

Линейное выражение любого многочлена h, кратного d, может быть найдено, исходя из линейного выражения d. А именно: пусть <img width=«52» height=«21» src=«ref-1_593437038-504.coolpic» v:shapes="_x0000_i1262"> и <img width=«80» height=«21» src=«ref-1_593437542-626.coolpic» v:shapes="_x0000_i1263">. Тогда <img width=«220» height=«21» src=«ref-1_593438168-1045.coolpic» v:shapes="_x0000_i1264">.

На практике линейное выражение многочлена h удобнее искать не с помощью алгоритма Евклида, а методом неопределенных коэффициентов. Запишем искомые многочлены u и v в общем виде с неопределенными (неизвестными) коэффициентами. Приравнивая коэффициенты при одинаковых степенях x в равенстве <img width=«77» height=«21» src=«ref-1_593439213-617.coolpic» v:shapes="_x0000_i1265">, получим систему уравнений для коэффициентов многочленов u и v. Легко видеть, что эти уравнения будут линейными.

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

Наименьшим общим кратным многочленов <img width=«129» height=«21» src=«ref-1_593439830-826.coolpic» v:shapes="_x0000_i1266"> над полем R называется многочлен h, обладающий следующими свойствами: 1) h делится на каждый из многочленов <img width=«81» height=«21» src=«ref-1_593440656-602.coolpic» v:shapes="_x0000_i1267">, т.е. является их общим кратным; 2) h делит любое общее кратное многочленов <img width=«81» height=«21» src=«ref-1_593440656-602.coolpic» v:shapes="_x0000_i1268">.

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

<img width=«224» height=«21» src=«ref-1_593441860-1010.coolpic» v:shapes="_x0000_i1269">                                  (11)

Доказательство. Для доказательства формулы (23) положим <img width=«71» height=«21» src=«ref-1_593442870-591.coolpic» v:shapes="_x0000_i1270">, <img width=«67» height=«21» src=«ref-1_593443461-557.coolpic» v:shapes="_x0000_i1271">, <img width=«57» height=«21» src=«ref-1_593444018-500.coolpic» v:shapes="_x0000_i1272">, <img width=«56» height=«21» src=«ref-1_593444518-487.coolpic» v:shapes="_x0000_i1273"> и рассмотрим многочлен

<img width=«136» height=«41» src=«ref-1_593445005-860.coolpic» v:shapes="_x0000_i1274">                                                (12)

Многочлен <img width=«19» height=«17» src=«ref-1_593445865-349.coolpic» v:shapes="_x0000_i1275"> является общим кратным многочленов f, g и, следовательно, делится на h. Теперь рассмотрим многочлен <img width=«56» height=«41» src=«ref-1_593446214-659.coolpic» v:shapes="_x0000_i1276">. Равенства <img width=«63» height=«44» src=«ref-1_593446873-653.coolpic» v:shapes="_x0000_i1277">, <img width=«63» height=«44» src=«ref-1_593447526-658.coolpic» v:shapes="_x0000_i1278"> показывают, что <img width=«20» height=«17» src=«ref-1_593448184-345.coolpic» v:shapes="_x0000_i1279">  — общий делитель многочленов f, g; следовательно, <img width=«20» height=«17» src=«ref-1_593448184-345.coolpic» v:shapes="_x0000_i1280"> делит d, т.е. <img width=«55» height=«21» src=«ref-1_593448874-484.coolpic» v:shapes="_x0000_i1281">, где q — некоторый многочлен. Отсюда получаем: <img width=«125» height=«44» src=«ref-1_593449358-938.coolpic» v:shapes="_x0000_i1282">, т.е. <img width=«52» height=«21» src=«ref-1_593450296-478.coolpic» v:shapes="_x0000_i1283">. Стало быть, h делится на <img width=«19» height=«17» src=«ref-1_593445865-349.coolpic» v:shapes="_x0000_i1284">. Таким образом, h и <img width=«19» height=«17» src=«ref-1_593445865-349.coolpic» v:shapes="_x0000_i1285"> ассоциированы, т.е. <img width=«51» height=«17» src=«ref-1_593451472-439.coolpic» v:shapes="_x0000_i1286">, где <img width=«39» height=«16» src=«ref-1_593451911-395.coolpic» v:shapes="_x0000_i1287">, <img width=«37» height=«17» src=«ref-1_593452306-367.coolpic» v:shapes="_x0000_i1288">. Из (24) получаем тогда, что <img width=«60» height=«21» src=«ref-1_593452673-595.coolpic» v:shapes="_x0000_i1289">, что и требовалось доказать.

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

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

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

Пусть, например, <img width=«53» height=«24» src=«ref-1_593453268-501.coolpic» v:shapes="_x0000_i1290">  — кольцо вычетов по простому модулю p. Два многочлена <img width=«131» height=«24» src=«ref-1_593453769-842.coolpic» v:shapes="_x0000_i1291">    продолжение
--PAGE_BREAK--