У. Питерсон - Коды, исправляющие ошибки (1267328), страница 38
Текст из файла (страница 38)
д. Может существовать самое большее конечное число таких элементов, и поэтому где-то должно появиться повторение, т. е. д' = д! для некоторых ! и !. Умножая это равенство на (д') †', получим 1 = 6! †'. Следовательно, некоторая степень элемента я равна 1. Пусть е — наименьшее целое положительное число, такое, что у' = !. Число е называется порядком элемента д. Совокупность элементов 1, д, дг, ..., й ' образует подгруппу, поскольку произведение любых двух элементов совокупности есть снова элемент того же вида, а элемент, обратный д!, равен йч ! и, следовательно, тоже является одним из элементов этой совокупности.
Группа, которая состоит нз всех степеней одного из ее элементов„ называется циклической группой. Порядок е любого элемента д группы является делителем порядка группы, так как группа содержит циклическую подгруппу из е элементов, порожденную д, и некоторое число смежных классов по этой подгруппе, каждый из которых состоит тоже из е элементов. Теорема 6.18.
Совокупность корней многочлена Хч-' — 1 является совокупностью всех д — 1 ненулевых элементов поля Сгр(у). Доказательство. Совокупность д — 1 ненулевых элементов поля 6Р(д) образует группу. Порядок каждого элемента поля ОР(д) должен быть делителем д — 1, и, следовательно, каждый из д — 1 элементов является корнем многочлена Хч-' — 1. Но этот много- член имеет самое большее д — 1 различных корней, так как его степень равна д — 1. Ч.т. д. Теорема 6.19. Многочлен Х" — 1 делится на многочлен Хм — 1 тогда и только тогда, когда и делится на т.
Доказательство. Предположим, что и = та' Тогда Уг — 1 делится на У вЂ” 1, поскольку У = 1 — корень многочлена Уг — 1, Подставляя Х'" = У, получаем, что Х ' — 1 делится на Х'" — 1. Теперь допустим, что п = тй+ г, где г ( А Тогда Х" — 1=Х'(Х "— 1)+Х' — 1, и в соответствии с алгоритмом деления Евклида Х" — 1=6(Х)(Х" — 1)+ г(Х). Сравнивая эти равенства, находим Хг (Хагэ 1) у(Х) =, и г(Х) =Х'-1, Хл 1 так как д(Х) — многочлен, а степень т(Х) меньше с(. Таким образом, остаток равен О только тогда, когда с = О, т.
е. когда и делится на т. Ч. т. д. Теорема 6.20. В поле 6Р(д) существует примитивный элемент а, т. е, элемент порядка а — 1. Каждый ненулевой элемент поля 6Р(д) может быть представлен как некоторая степень ы, т. е. мультипликативная группа поля Галуа 6Г(ц) является циклической. Доказательство.
Пусть д — 1= р,'р" ... р,, и пусть !3,. — элемент поля порядка р,", 1=1, 2, ..., г. (Существует рч — р,'и ' ра1 таких элементов — корни многочлена Х ' — 1, которые не являются аг корнями многочлена Х ' — 1.) Поскольку р," и р" взаимно просты, то существуют такие з и г, что зр,'+1р'-'=1. Поэтому араг вра 1-1р~Ь Фр'г (М») ' =(!3») ' =(Я =(3», 'аналогично ((Зфз) ' =йь Таким образом, Р, и (3, являются степенями (3(3», откуда следует, что порядок элемента поля (3,йр являетсн делителем р',р,'ч Но если ра раг/а (!31(3») ' »г =1 при некотором а >1, то либо порядок (3, меньше чем р',, либо порядок (3» меньше чем р';-, что противоречит нашим предположениям. Следовательно, порядок !31р» равен р', р,'*.
Индукцией по 1 отсюда выводим, что порядок элемента а=Щ3»... й, равен р,"р" ... р,'а=у — !. Таким образом, элементы а, а', ... ..., а« '=1 являются различными элементами поля, и мультипликативная группа поля 6Р(д) циклическая. Ч.т.д. Пример. Поле Галуа 6г (2') из 2' элементов может быть образовано как поле многочленов над 6г(2) по модулю Х~+Х+1. Пусть а обозначает класс вычетов, который содержит Х. Тогда а является корнем многочлена Х'+ Х+ 1 и примитивным элементом поля. Для этого случая 15 ненулевых элементов поля приведены в табл.
6.!. Следующие семь теорем содержат более детальные сведения о взаимосвязи между мультипликативными свойствами элементов поля, минимальными многочленами от элементов поля и многочленом Х» — Х. После этих теорем расположен материал„иллюстриРующий методы их использовании при разложении многочленов тябяяця ел. ПрсдотзяЛЕППЕ ПОЛЯ 0Р(2з) а'+ а'+ а' аз + аг аз + аз+ а'+ а'+ аз+ аз+ аз+ аг аз вида Х" — 1 на множители. Это должно помочь читателю глубже понять структуру поля. Теорема 6.21.
Если ) (Х) — много»лен с коэффициентами из поля 6Р(у) и 6-корень )(Х) в расширении поля 6Р(г)), то 6» также является корнем !'(Х). Доказательство. Пусть 1(Х) = ао+ азХ+ ... + а„Х". Тогда 1(Х))»=(ао)» + (азХ)~+... + (а„Х")» = ао»+ аз»Х»+ ... + АХ»)" по теореме 6.14. Далее, по теореме 6.16 а»-' = 1, и поэтому а» = а для любого элемента а нз 6Р(з)). Следовательно, ()(Х)1»= ао+ + азХ»+,, + а„(Х») = )(Х»), и если Щ) = О, то У(6)3» = =1(6)=О. Ч.
и. Теорема 6.22. Рассмотрим расширение поля 6Р(д), которое содержит все корни много»лена Х» — Х. Тогда совокупность этих корней образует подполе. Доказательство. Если а и Ь вЂ” корпи многочлена, то а + Ь— также корень многочлепа Х' — Х, так как по теореме 6.14 т т зл (а+Ь)» =а» +Ь» =а+Ь. Кроме того,( — а) = — (а» /= — а, и, таким образом, — а — тоже корень этого многочлена, если а является его корнем.
(Заметим, что — а=а, если характеристика поля равна 2.) Поэтому корни многочлена образуют аддитивную группу. Если а и Ь вЂ” корни многочлена, то произведение аЬ и обратный элемент а — ' (если а ныл) также являются его корнями. Остальные аксиомы справедливы, поскольку корни принадлежат полю. Ч. т.
д. Теорема 6.23. Каэкдый лгногочлен р(Х) степени пт, непсзиводимый над полем 6Р(д), является делителелз многочлена Х» — Х. ао —- аг аг аз аз а' = ао а' а' = азо азз а'з = а" = а'з а'з 1=(0001) а =(0010) (0 100) -(1 000) а+ 1 =(00 ! 1) а = (О 1 1 0) = (1 1 0 0) а + 1 = (1 0 1 1) -1-1 =(0101) а =(1010) а + 1 = (О 1 1 1) а =(1110) а+1=(1111) + 1 = (1 1 О 1) + 1 =(! 001) 1 =а' Доказательство. Если р(Х) = Х, то теорема, очевидно, верна.
Пусть теперь р(Х)Ф Х и а (отличный от нуля) — корень много- члена р(Х) в расширении поля многочленов по модулю р(Х) над полем 6Р(у). Это поле является полем из д ' элементов, и совокупность всех его ненулевых элементов образует группу порядка — 1, Поэтому порядок с» должен быть делителем д — 1 и и »1 — ~ должен быть корнем многочлена Х» — 1. Тогда по теореме бйб Ф» — ~ многочлен р(Х) является делителем многочленаХ" — 1.
Ч. т. д. Теорема 6.24. Каждый делитель многочлена Х» — Х, неприводимый над полем 6Р(д), имеет степень, равную т или меньшую т, Доказательство, Предположим, что многочлен р(Х) степени А представляет собой неприводимый делитель многочлена Х' — Х над полем 6Р(д), и рассмотрим расширение поля многочленов над 6Р(д) по модулю р(Х). Оио состоит из дь элементов, каждый из которых может быть представлен в виде аь+ апх+ ... ... + аь га."- ' = р, где»х — корень р(Х), а а», аь ..., аь ~ — элементы поля 6Р(д). Тогда по теореме 6.14 р» = а»» + а' а' + + а$ и" <ь и ФВ РП По теореме 6.18 а' =1 и, следовательню, а» =а для любого элемента а из поля 6Р(д ), и поскольку а», аь ..., аь ~ принадлежат 6Р(д) н, следовательно, принадлежат также расширению поля 6Р(дм), то' р» = аь + а,а» + ...
+ аь ,а» УП УИ Ш Но а — корень многочлена Х» — Х, и поэтому а» =а и а'» =а~ для всех 1. Таким образом, =а»+ а,и+ ... +аь,а т. е. (1 — также корень многочлена Х» — Х. Так как число таких элементов составляет дь, тогда как Х вЂ” Х имеет не более чем » у"' корней, то д"' ) д" и, следовательно, гп ) й. Ч. т. д. Теорема 6.25. Если р — элемент расширения поля 6Р(у), то порядок е элемента р является делителем числа уь — 1, но не является делителем никакого меньшего числа вида д" — 1; здесь Я вЂ” степень минимальной функции для и.
Доказательство. Пусть т(Х) — минимальная функция для (1; предположим, что ее степень равна Й, Тогда п»(Х) является дели»»-1 гелем многочлепа Х» — 1 по теореме 6.23, а р — корнем много»е-! члена Х вЂ” 1. Поэтому порядок р является делителем д" — 1, Предположим, что д" — 1 делится на порядок р при и й. Тогда является корнем многочлена Х' — Х, а тп (Х) — делителем Х~ — Х по теореме 6.16. Таким образом, по теореме 6.24 степень многочлена т(Х) не превосходит п. Ч. т. д. Теорема 6.26. Пусть р(Х) — аногочлен степени т с коэф4иг(иентами из поля бр(у), который неприводим в этом поле, и пусть 6 корень многочлена р(Х) в расширении поля.
Тогда чш-1 11, 6ч, ..., рч образуют совокупность всех корней нногочлена р(х). Доказательство. По теореме 6.21 элементы являются корнями многочлена р(Х). Следующее рассуждение показывает, что эти и элементов поля различны. Предположим, что т зто не так н р~ =6", и пусть 1(й Тогда у=~' =Ь")' =Ь")' 61 +г-! 11 Таким образом, порядок 11 является делителем у +~-' — 1. Но многочлеп р(Х) отличается от минимального многочлена для р самое большее на постоянный множитель, и та+1 — 1( и, где и степень р(Х). Это противоречит утверждению теоремы 6.25, н„следот — 1 вательно, элементы 6, рч, ..., рч различны. Так как многочлен р(Х) может иметь самое большее пт корней, то этим исчерпываются все корни р(Х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
