Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 26
Текст из файла (страница 26)
Требуемый резуль вытекает теперь из определений огй (~) и порядка элемента-' в группе К' . 3.4. Следствие. Если ~ Е Еч (х! — неприводимый много степени т над полем Еч, то его порядок делит число д — 1. Доказательство. Если 1(х) = сх, где с Е Ц, то огб (1) = и результат тривиален. В противном же случае результат вы ' кает из теоремы 3.3 и того факта, что Е' — группа поряд д — !.
$1. Порядки мкогочлепов я примитивные многочлепы 111 Для приводимых многочленов утверждение следствия 3.4 не обязательно выполняется (см. пример 3.10). Существует еще олна интеРпРетаЦиЯ поРЯДка многочлена 1, пРи котоРой с много- членом 7 связывается некоторая квадратная матрица и огг( (7) совпадает с порядком этой матрицы как элемента некоторой группы матриц (см. лемму 8.26). С помощью теоремы 3.3 можно получить формулу для числа нормированных многочленов данной степени и данного порядка. Снова символом гр будем обозначать функцию Зйлера, введенную в теореме 1.!5 (1ч).
Удобна следующая терминология: если и— натуральное и Ь вЂ” целое числа, причем НОД (и, Ь) — 1, то наименьшее натуральное число я, для которого Ьь =:- ! (шог( и), называется показателем, которому принадлежит число Ь по модулю п (его называют также мультипликативным порядком числа Ь по модулю и). 3.5. Теорема. Число нормированных неприводимых многочленов из Кч !х! степени т и порядка е равно ~р (е)!и, если е ~ 2, а и — показатель, которому принадлежит число д по модулю е, ровно 2, если т .=.—. е = 1, и равно 0 во всех остальных случаях.
0 частности, сгпепень неприводимого многочлена из Гч !х! порядка е должна совпадать с показателем, которому йринадлежит число д по модулю е. Доказательство. Пусть | — неприводимый многочлен из К !х), причем 7" (0) Ф О. Тогда по теореме 3.3 огд (7) = — е в том и только том случае, если все корни многочлена 7" являются первообраз- ными корнями степени е из единицы над полем Кч, т. е. если 7' делит круговой многочлен Я,. По теореме 2.47 (! 1) все нормированные неприводимые делители многочлена !',1, имеют одну и ту же шепень, и этой степенью является наименьшее натуральное число т, для которого дм: — 1 (вод е).
Число таких делителей равно гр (е)йп. Для т = е =- 1 мы должны принять в расчет также нормированный неприводимый многочлен 7 (х) — х. Значения порядков многочленов удобно представить в виде габлицы, по крайней мере для неприводимых многочленов (см. ч 2 гл. !0). Так как каждый многочлен положительной степени можно записать в виде произведения неприводимых многочленов, то вычисление порядков многочленов значительно упрощается, если знать, как находить порядок степени неприводимого много- члена и произведения попарно взаимно простых многочленов.
11оследующнй материал посвящен как раз этим вопросам. 3.6. Лемма. Пусть с — натуральное число. Многочлен Е Гя !х), удовлетворяющий условию Р (0) ~ О, делит двучлен "' — ! в том и только том случае, если огд (1) делит число с.
Гл. 3. Многочлены нлд коночными полнмн Доказательство. Если число е — огй (1) делит с, то много. член 1(х) делит х' — 1, а х' — ! делит х' — 1. Обратно, если многочлен 1(х) делит х' — 1, то по определению порядка много-,: члена с:- е, так что можно записать с = те ц. г, где т с !1) и 0 «г < е. Так как х' — 1 =. (хны 1) х' н- (х' — !), то много- член 1(х) делит х' -- 1 (поскольку делит остальные два члена, предыдущего равенства), а это возможно лшоь при г:: О. Значит, ~ число е делит с. 3.7. Следствие. Если е, и ен -- натуральньн* числа, то наи-~ болыиий обгций делигпель мноеочленов х" — ! и х'* — 1 в 'Кч 1х)) равен хл — 1, где й — НОД (е„ен1.
Докизательство. Пусть !' (х) — нормированный наибольший' общий делитель многочленов х' — 1 и х' — !. Поскольку$ лл — 1 — общий делитель юих многочлепов, чо хл — 1 делит! (х)..' С другой стороны, так как !" (л) дьмшт н х" -- 1, и х' -- 1, то по' лемме 3.6 порядок многочлена )' (х) делит как е,, так и еч Следовательно, огг! (1) делит й, а значит, согласно лемме 3.6, многочлен 1 (х) делит х" — 1.
Обьеднняя полученные результаты, заключаем,' что 1 (х)::=- хл — 1. П Так как при определении порядка многочлена не учитывается, его сомножитель, равный степени переменной х, то нет необходимости рассматривать степени таких неяриводимых многочленов д (х), для которых а (О) =- О. 3.8. Теорема. Пусаи> и Е К и а(х) — неприводимый много-; член над конечным полем харакпмристики р, такой, чгпо у (О) Ф„' -ф О, Тогда длл многочлсна вида 1:-= дн огд (1) -= огд (д") -=- р' огй (д), где 1 — наименьшее целое число, для которого р' =.= п.
Доказательство. Положим е:::-- огд (д) и с =- огй (1). Учиты-. вая, что делимость двучлена х' — 1 на многочлен 1 (х) влечет за собой делимость х' — 1 на многочлен д(х), получаем в силУ,' леммы 3.6 что число е делит с. Далее, многочлен д (х) делит х' — 11.' позтому )'(х) делит (х' — !)", а значит, делит и (х' — 1)" — х'"' — !. Таким образом, в силу леммы 3.6 число с делит ер". Учитывая доказанное ранее, получаем, что число с имеет в с .-- ер', где 0 -:, з .=, 1. Заметим, что многочлеи х" — ! им лишь простые корни„так как но следствию 3.4 число е не делите, на р. Позтому все корни многочлена х'л' — ! == (х' — 1)л' имею кратность р'. Но так как многочлен 1 (х) — — (а (х))л делит х"' — ! то, сравнивая кратности корней, получаем, что р' ..
и, так ч з =. Г. Таким образом, заключаем, что з -.--. 1 и с -= ер'. Ч 1. Порядки многочленов н примитивные многочлены 113 3.9. Теорема. Пусть у„..„уь — попарно взаимно простые ненулевые многочлены над полем К», и пусть 1' = ус ... уь. Тогда огс[ (~) = огс1 (ус ... Ь,) = НОК (огд (ус), ..., огс[ (Ф,)). Доказательство. Нетрудно видеть, что для доказательства теоремы достаточно рассмотреть лишь случай, когда ус (0) ~ О, .- 1, ..., [с, Положим е = огс[Ц) и ес = огс[(ус), 1= 1, ..., й, и пусть с = НОК (е„..., е„). Тогда каждый многочлен дс (х), 1::. с' ~~ сс, делит двучлен х'с — 1 и потому делит х' — 1. В силу попарной взаимной простоты многочленов д„..., дк получаем, что) (х) =- П дс (х) делит х' — 1.
Учитывая лемму 3,6, мы видим, с=-с что число е делит с. С другой стороны, г" (х) делит х' — 1 и, следовательно, каждый многочлен дс (х), 1 ( с < сс, делит х' — 1. Снова применяем лемму 3.6 и получаем, что каждое из чисел е;, 1 .:-', с ~ й, делит е, а потому и с делит е. Это означает, что с = е. В действительности, используя то же доказательство, можно показать, что порядок наименьшего общего кратного нескольких пенуленых многочленов равен наименьшему общему кратному порядков этих многочленов. 3.10.
Пример. Найдем порядок многочлена ~ (х) = хгв + х' + Р хк + х'+ ! ~ Ге [х!. Каноническое разложение его над полем Ге имеет вид 1(х) = (хе+ х+ 1)з(хе+ х+ 1), Так как огд (х'+ х + 1) = 3, то из теоремы 3.8 получаем, что огд ((хя + х + 1)я) = 12. Далее, огд (хе + х + 1) = 15, так что из теоремы 3.9 получаем, что огд (~) = НОК (12, 15) = 60. Заметим, что огс[ (Г) не делит число 2'е — ! = 1023; это показывает, 'сто для приводимых многочленов следствие 3.4 не обязательно выполняется.
П На основании доказанного можно дать следующую общую формулу для порядка многочлена. При этом предполагается, что все рассматриваемые многочлены имеют положительную степень н ненулевой постоянный член. 3.11. Теорема. Пусть 㻠— конечное поле характеристики р. Вели [ == а[се ... ~е" — каноническое разложение в кольце [[» [х[ многочлена ) (х) ~ Г' [х[ положительной степени, такого, что [(О) Ф 0 (т. е.
а ~ [['», и„..., пк Е [[Ч и )„..., сч — различные нормссрованньсе неприводимые многочлены из К» [х[, отличные осп х), то огс[ (Д = огс[ (а[с' ... ~е") = р'НОК (огс1 (гс), ..., огд ()е)), З зек, пм П4 Гл. 3. Многочлены над нонечнымн полнмн где 1 — наименьшее целое число, удовлетворяюи4ее неравенству р! ~ шах (и„..., па). Один нз методов определения порядка неприводимого много- члена 1 нз Кч [х), удовлетворяющего условию 1(0) ~ О, основан: на том факте, что порядок е многочлена 1 является нанмепьшнм натуральным числом, удовлетворяющим сравнению х' =-: 1 (шод )'(х)).
Кроме того, согласно следствн!о 3.4, число е делит д — 1, где! т — степень многочлена 1'. Предполагая, что д" ~ 2, будем исхо- ' днть нз разложения числа дм — 1 на простые сомножителя: ун 1 П р".) !=! Для каждого 1, 1 -~ )~~з, найдем вычеты одночленов х (ч"' — !)/а по модулю ! (х) (т. е. остатки при нх делении на ! (х)). Обычно это; делается перемножением подходящим образом выбранного набора вычетов по модулю 1 (х) степеней х, ха, х»", ..., хч" переменной х. ' Прн этом, если окажется, что х ' ' !а! чь1 (гной 1 (х))„то число е, (чл'-!),'а делится на р,', а если х ~ 'з = =1 (и!од ~ (х)), то число е не де-; Г,' лнтся на р!а.
В последнем случае мы выясняем, будет лн число е а!-! е -2 делиться на р,~, р!з, ..., р;, вычисляя соответственно вычеты, по модулю 1 (х) следующих степенея переменной х: ( "-')l'! ("-!И (ч -Мз Такой подсчет проводится для каждого простого делителя р) „: числа !)"' — 1, н в итоге находится число е =- огд (1). Ключевым моментом указанного метода является разложение на простые сомножителя натурального числа д"' — 1.
Составлены: обширные таблицы для полного разложения чнсел такого вида,, особенно для случая у = — 2. Существует связь между порядками некоторых многочленов,, которые можно получать друг нз друга простыми алгебраическими преобразованиями. Тнпнчным примером может служить следующее преобразование. 3.12. Определение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
