У. Питерсон - Коды, исправляющие ошибки (1267328), страница 36
Текст из файла (страница 36)
Если з(Х) делится на «(Х) и «(Х) делится на з(Х), то они отличаются самое большее множителем, который является элементом поля. Это утверждение можно проверить следующим образом. Пусть для некоторых многочленов а(Х) и Ь(Х) справедливы равенства «(Х) = е(Х)а(Х) и з(Х) = г(Х)Ь(Х). Тогда, так как степень г(Х) равна сумме степеней з(Х) и а(Х), степень г(Х) больше или равна степени з(Х). Аналогично степень з(Х) равна или больше степени г(Х), и, таким образом, степени з(Х) и г(Х) должны быть равны.
Следовательно, многочлены а(Х) и Ь(Х) имеют степень О и должны быть элементами поля. Для любой пары многочленов з(Х) и й(Х) существует единственная пара многочленов д(Х) — частное и г(Х) — остаток, таких, что (6.4) з (Х) = й (Х) а (Х) + г (Х) и степень г(Х) меньше степени й(Х). Этот факт известен как алгоритм деления Евклида, и многочлены а(Х) и «(Х) могут быть найдены путем обычного деления многочленов «столбикомь.
В предположении, что делитель в алгоритме деления имеет первую степень, т. е. й(Х) = Х вЂ” а, можно получить несколько важных результатов. Пусть г(Х) =(Х вЂ” а) а(Х) + г. (6.5) Поскольку многочлен «должен иметь степень, меньшую чем степень делителя, он должен иметь степень, равную О, т. е. должен быть элементом поля. Подставляя в это равенство а вместо Х, найдем, что « = ((а), Это теорема об остатке, Далее, если 1(а) = О, т. е. если а — корень многочлена ДХ), то г = О и много- член Х вЂ” а является множителем г(Х).
Этот результат известен как теорема Безу. Таким образом, каждому корню' многочлена 1(Х) однозначно соответствует множитель первой степени, Поскольку степень произведения многочленов равна сумме степеней множителей, степень ((Х) по крайней мере не меньше числа корней много члена ~ (Х) ° Сходство в строении и свойствах кольца целых чисел и кольца многочленов над некоторым полем очевидно. Оба они являются частными случаями алгебраического образования, называемого евклидовым кольцом. Далее в этом, а также в двух следующих разделах приводятся в основном результаты, аналогичные теоремам равд.
6,2. Доказательства не даются, но читатель сможет сам получить их на основе доказательств равд. 6.2, заменяя «целое число» на «многочлен», выражение «а меньше, чем Ь» на «степень а(Х) меньше степени Ь(Х)» н введя несколько очень незначительных дополнительных изменений. Наибольший общий делитель й(Х) двух многочлепов г(Х) и з(Х) всегда может быть представлен в виде й(Х)=а (Х)г(Х)+ Ь(Х)е(Х), (6.6) где а(Х) и Ь(Х) — многочлены. Этот результат может быть получен путем использования алгоритма деления таким же образом, как это делалось для целых чисел. Теорема. 6.5. Совокупность многочленов образует идеал тогда и только тогда, когда она содержит все м огочлены, кратные некоторому многочлену.
Это значит, что кольцо многочленов есть кольцо главных идеалов. Идеал, состоящий из всех многочленов, кратных )(Х), обозначается через (((Х)). Кольцо классов вычетов, образованных по этому идеалу, называется кольцом многочлепов по модулю ) (Х). Теорема 6.6. Каждый класс вычетов по модулю многочлена Г(Х) степени и содержит либо О, либо многочлен степени, меньшей чем и. Нуль является элементом идеала, а многочлены степеней, меньших чем и, принадлежат различным классам вычетов. 6.4. Алгебра классов вычетов многочленов Теорема 6.7. Классы вычетов многочленов по модулю много- члена г(Х) степени и образуют коммутативную линейнуго алгебру размерности и над полем коэффициентов.
Доказательство. Умножение на скаляр определяется равенством а(г(Х)) = (аг(Х)); легко проверить, что прн этом выполняются все аксиомы векторного пространства и алгебры. Например, справедливость дистрибутивного закона проверяется следующим образом: (г (ХЦ ((г (Х)) + ~Е (ХЦ) = (г (Х) (з (Х) + ~ (Х))) = = (г (Х) з (Х) + г (Х) ~ (Х)) = = (г(Х)) (з(ХЦ+ (г(Х)) (1 (ХЦ. То, что векторное пространство имеет размерность и, можно увидеть из того, что п классов вычетов (1), (Х), (Х'), ..., (Х"-') порождают все пространство, поскольку каждый класс вычетов содержит многочлен степени, меньшей чем и, и (а +а,ХФ ., +а„,Х" ~)=а,(Ц+а,(Х)+ .. +а,(Х" '). (6.7) Кроме того, зти и классов вычетов линейно независимы, потому что в правой части соотношения (6.7) стоит произвольная линейная комбинация классов вычетов (1), (Х), ..., (Х" — 9, а левая часть равна нулю, только если многочлен аз+ а,Х+ ...
+ а„,Х -' делится на 1(Х), что невозможно, или если все коэффициенты а; равны О. Ч, т. д. Обычно принято брать многочлеп минимальной степени в классе вычетов в качестве представителя этого класса вычетов, однако в этой книг использование одних и тех же обозначений для класса вычетов и многочлена минимальной степени в классе вычетов может привести к некоторой путанице. Поэтому там, где классы вычетов не обозначаются при помощи фигурных скобок, будет применяться следующая система обозначений.
Для обозначения класса вычетов, содержащего Х, будет использоваться некоторый символ, обычно 5 или а. Класс вычетов, содержащий элемент поля, будет обозначаться таким же символом, как этот элемент поля; это не должно стать причиной путаницы. Тогда смежный класс, который содержит многочлен аь+ а~Х+ ... ... + а„~Х" ', имеет вид (аз+ а,Х + ... + а„,Х" ) = (оь) + +(а )(Х)+ ... +(а„,)(Х" ')= — а,+а,5+ ... + а„,5" '. Таким образом, каждый класс вычетов равен многочлену от 5 степени, меньшей чем п.
Теорема 6.8. В алгебре многочленов ио модулю многочлена 1(Х) степени и многочлен 1(5) =- О, но не существует равного нулю многочлена от 5 степени, меньшей чем п. Локазател ьство. 1(5) = 10+ 115 + . " + 1 5" = 10+ 11 (Х) + ... + 1. (Х") = =(1 +1,Х+ ... +1,Х")=(1(Х))=О. Аналогично, если д(Х) — любой многочлен степени, меньшей чем и то в(5) = (в(Х)), и по теореме 6.6 этот класс вычетов не есть идеал.
Ч. т. д. Из этой теоремы следует, что различные многочлены от Я, имеющие степени, меньшие чем и, являются различными классами вычетов, так как в противном случае их разность была бы много- членом от 5 степени, меньшей чем п, который был бы равен О. Теорема 6.9. Пусть»' — идеал в алгебре многочленов по модулю ((Х), а к(Х) — отличный от нуля многочлен наименьшей степени, такой, что класс вычетов (д(Х)) принадлежит Х.
При этом класс вычетов (з(Х)) принадлежит Х тогда и только тогда, когда много- член э(Х) делится на й(Х). Более того, многочлен д(Х) является делителем ((Х). Доказательство. В соответствии с алгоритмом деления Евклида з (Х) = д'(Х) д (Х) + «(Х), где степень «(Х) меньше степени д(Х). Следовательно, ( (Х)) =(й(ХН(ИХ))+( (Х)).
и если классы вычетов (з(Х)) и (д(Х)) принадлежат Х, то класс вычетов (з(Х)) — (д(Х))(д(Х)) = («(Х)) также принадлежит Х. Так как степень»(Х) меньше степени д(Х) и по предположению д(Х) — ненулевой многочлен наименьшей степени, такой, что класс вычетов (й(Х)) принадлежит Х, то многочлен»(Х) должен быть равен О.
Следовательно, многочлен з(Х) кратен многочлену д(Х). Обратно, если многочлен з(Х) кратен многочлену у(Х), то з(Х)=д(Х)д(Х) и (з(Х)) =(д(Х))(д(Х)), так что если класс вычетов (д(Х)) принадлежит У, то класс вычетов (з(Х)) также должен принадлежать В соответствии с алгоритмом деления Евклида 1 (Х) = К (Х) ч (Х) +» (Х), где степень многочлена»(Х) меньше степени й(Х).
Поэтому (О) =() (Х)) =(д(ХЦ(д(Х))+ (»(Х)), и, значит, класс вычетов (»(Х)) принадлежит Х, Поскольку степень»(Х) меньше степени д(Х), то многочлен «(Х) должен быть нулевым, и, следовательно, многочлен )(Х) кратен д(Л). Ч. т. д. Теорема 6.10. Для любого идеала У в алгебре л~нюгочленов по модулю ) (Х) существует единственный нормированный много- член д(Х) минимальной степени, такой, что класс вьшетов (д(Х)) принадлежит идеалу 1.
И наоборот, каждый нормированный многочлен д(Х), являющийся делителем ((Х), порождает некоторый идеал Х, в котором д(Х) является нормированным многочленом наименьшей степени. Доказательство. Должен существовать многочлен наименьшей степени й(Х) = йь+й,Х+ „, + йкХ", такой, что класс вычетов (й(Х)) принадлежит У. Тогда многочлен Ь~, ~й (Х) оказывается нормированным многочленом наименьшей степени, класс вычетов которого также принадлежит У, и, следовательно, в У существует по крайней мере один нормированный многочлен минимальной степени. Предположим, что существуют два таких многочлена д(Х) и д'(Х). Тогда по теореме 6.9 многочлен д'(Х) делится на у(Х) и многочлен у(Х) делится на д'(Х), и, таким образом, они отличаются самое большее на множитель, являющийся элементом поля.
Поскольку по предположению оба многочлена являются нормированными, этим элементом поля должна быть 1 и д(Х) = = в (Х). Следовательно, существует единственный нормированный многочлен минимальной степени д'(Х), класс вычетов которого (у(Х)) принадлежит У. Предположим теперь, что д(Х) — нормированный многочлен, являющийся делителем У(Х), и рассмотрим идеал У, порожденный классом вычетов (у(Х)), т. е. идеал, содержащий все классы вычетов, кратные (д(Х)).
Пусть класс вычетов («(Х)) принадлежит У. Тогда («(Х)) = (д (Х)) (а (Х)) = (у (Х) и (Х)) для некоторого многочлена а(Х) „и поэтому «(Х) =д(Х)а(Х)+ 1(Х) Ь(Х) для некоторого многочлена Ь(Х). Так как многочлен У(Х) кратен д(Х), то «(Х) также кратен д(Х), и поэтому, если многочлен «(Х) отличен от нуля, он имеет степень, по крайней мере не меньшую чем степень д(Х). Таким образом, д(Х) — нормированный многочлен минимальной степени, класс вычетов которого принадлежит У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
