Найдем теперь порядок элемента а**, если а -элемент порядка п. Если {п, к) - наибольший общий делитель и и А;, то (а)"/*"-= = (а")<"= 1, так что порядок а делит число п = {п, к). С другой стороны, если а"" = 1, то km кратно п 1п/{п, к)] {п, к). Так как число п/(п, к) взаимно просто с к, то оно должно быть делителем т. Это доказывает следующую теорему:

4.23. Теорема. Если порядок элемента а равен п, то порядок элемента а равен п/{п, к).

Будем говорить, что элемент а является примитивным корнем п-й степени из единицы, если порядок а равен п. В поле порядка q элемент а называется примитивным элементом поля, если порядок а равен q - 1.

4.24. Теорема. Конечное поле порядка q содержит примитивный элемент {порядка q - i), степени которого пробегают все ненулевые элементы поля.

Доказательство. Пусть п - максимальный порядок ненулевых элементов поля, и пусть а - элемент порядка п. Так как п различных степеней а отличны от нуля, то ге g - 1. Пусть Р - некоторый другой ненулевой элемент поля, и пусть d - поря- i док-р. Если d 1 ге, то р("> имеет порядок dl{n, d), взаимно простой с п, так.что арс-) имеет порядок ?id/{n, d), превосходящий п. Так] как это противоречит выбору п, то заключаем, что d \ п. Следова-] тельно, каждый ненулевой элемент поля является корнем многочле-.] на X 1. Так как степень этого многочлена равна п, то в соответ- ствии с теоремой 2.15 он имеет в данном поле не более п корней*! Следовательно, q - i п. Так как мы уже показали, что п q - 1, то га = g - 1. щ

Эта теорема имеет следствие, обобщающее теорему Ферма:

4.25. Теорема. Каждый элемент поля порядка q удовлетво-i

- х = 0.

ряет уравнению

Доказательство. Все ненулевые элементы поля удовлет-! воряют условию а;" - 1=0; нуль поля удовлетворяет уравнении X = 0. Значит, все элементы поля удовлетворяют уравнениг X (а;«-1 - 1) = а:« - а; = 0. щ

4.3. Круговые многочлены

Каждое разложение многочлена х ~ х задает разбиение элемен- тов конечного поля порядка q. Если х - х = f {х) g {х), то каждыв элемент поля является или корнем многочлена / (х), или корпел

многочлена g {х). Мы уже рассматривали разложение а; - х - = X (а;" - 1), отделяющее нулевой элемент от ненулевых. Поставим теперь задачу разбиения множества ненулевых элементов поля на подмножества элементов одного и того же порядка с помощью разложения многочлена а;~ - 1. Если поле содержит элемент а порядка п, то элементы 1, а, а, . . ., а"" являются корнями многочлена х" - 1 степени п. Согласно теореме 2.15, ни в каком поле многочлен степени п не может иметь более, чем п корней. Следовательно, в любом поле, содержащем примитивный корень ге-й степени из единицы, справедлива следующая теорема о разложении:

4.31. Теорема.

Х"-1 = "П (а:-а)= fj (-«).

г=0 i=l

Аналогично, если п = kd, то а*

а" являются

корнями многочлена а;** - 1. Этот многочлен имеет степень d и, следовательно, не может иметь более d корней ни в одном поле. Значит, если порядок элемента а равен п и d делит п, то среди степеней а содержатся все корни степени d из единицы. Более того, каждый элемент поля, порядок которого делит п, должен быть степенью а, так как элемент порядка d является корнем d-й. степени из единицы.

Порядок каждой степени элемента а делит п, и каждый элемент поля, порядок которого делит п, является степенью а. Это доказывает следующее разбиение степеней элемента а в соответствии с их порядками:

"-1= ПП(-Р).

dn р-элемент порядка d

Многочлены, корни которых совпадают со всеми элементами поля порядка d, называются круговыми многочленами и обозначаются через Q<-) {х). Из этого определения и теоремы 4.31 как следствие сразу вытекает

4.32. Теорема.

ж"-1= П Q(<i){x).

d, d\n

Применение мультипликативной формы теоремы обращения Мёбиуса 3.42 дает

4.33. Теорема.

<?(п)(а;)= Y[(xd - i)Mn/d) [](a;»/<J-1)Д№,

d, d,

d\n dn

Используя свойства функции Мёбиуса, можно с помощью простых операций выяснить многие свойства круговых многочленов.

4.34. Свойства круговых много ч л е н о в.

4.341. Если р - простое число, не делящее т, то

4.342. Если р -простое число, не делящее т, то

4.343. Если n = Y{pl\ sde pi -простые числа, то

deg(?(")(x) = 9(re), где (р{п)-фи-функция Эйлера,

ф(„) = П/>Г(;>,-1).

4.344. Если п>2, то

(ж) = П (1 - "Т •

d, d\n

4.345. Если n>3 м п нечетно, тео

(?(2n)(x) = (?<")( -х).

4.346. Для п>2

а:Ф(п)(2(п)(х-1) = (?(") (х).

4.347.

О тогда и только тюгда, когда n = i, р тогда и только тогда, когда п - Q(n) (1) - степень простого числа,

1 тогда и только тогда, когда п имееп У не менее двух простых делителей.

4.348.

<2(")(-1) =

0 тогда и только тогда, когда п - 2, - 2 тогда и только тогда, когда n~i,

2 тогда и только тогда, когда п - степень 2, ?г>4,

р тогда и только тогда, когда п = 2р, к>0,

1 в остальных случаях.

= П [{XV~Y1-\]V-W QiPm) (х-). d, d\mp

4.342.

Q(Pm)(x) Д(Х"Р/ 1)Ц(<1) Д (a;pm/d l)n(d)

d. d,

d\m d\pm

d\tn

= [ П [{хп-"-1Г] [ П (х-/<-1)-»«)]=Щ-.

d, d\m

d, d\m

4.343. В силу свойства 4.31

ф(/7П) = /7-1ф (рт).

Согласно свойству 4.342,

Ф (рт) =р<р (т) ф (т) = -1) ф {т). Следовательно, используя индукцию, получаем, что

Ф(Др:о=л"(л-1)Ф(П:о=

г=1 1=1

=. д рГЧр.-1)ф(Др:о=ПрГ(р.-1).

4.344.

Qin) (х) = П (х"<* - = ( 1) dln П (1 - x)<У =

din djn

П (1 -x)i*W, если п = 1,

Ц (i a;n/d)ix«i) если ге>1.

Доказательства. 4.341.

= ]][(! + a;"/<i)t№ = Q"" (- x).

4.346. Если порядок a равен n, то и порядок а" равен га. Следовательно, (f") (а") =0 тогда и только тогда, когда (а) = 0. Таким образом, (х) и а;ф(")(2" (х~) имеют одинаковые корни. Степень обоих многочленов равна ф (га) и если га>2, то оба многочлена нормированы. Следовательно,

(?М(х)=хФ(")(?(")(х-1)

Ф(п) Ф(п)

<"(Х)= П <?1">Х* = ХФ(")(?<"(х-1)= 2 <?jl,) iX*.

i=0 i==0

Таким образом, Q =Qin)-i Для всех i.

4.347. Так как условия теоремы друг друга исключают, то надо проверить только достаточность утверждения.

(а) (1) = 1 -1 = 0.

(Ь) (!)=(?<»> (!»"") = (?<»>(!),

<?<>() = fEf = S

(2<Р)(1)= S Г =/7.

(с) Согласно свойству 4.342, 4.348.

(a) (?2)(а;) = а; + 1; (?<2.(-1) = 0,

(b) (?<1. (а;) = а; - 1; «?<i (-1) == - 2,

(c) «?(2 (д.) .г"-!!; (2") ( !)== 11 = 2,

(d) (?(2Р) (Х) = (?(Л (-Х); (?(2Р) (-1) = «?(Л (1)=J9,

(e) Если ге = / и га нечетно, то ( - 1) = ( - 1) = р-1

= 2 (-1)*=!.

.5. Круговые многочлены Если га = тр, р нечетно и {р, гаг) = 1,

С>™> [(-1)Р]

= 1..

(?"п)(-1)

Непосредственным следствием свойства 4.343 является

4.35. Теорема. Любое конечное поле порядка q содержит точно ц> {q - 1) примитивных элементов поля.

Используя свойство 4.343, можно сразу определить степень любого кругового многочлена. Если порядок а равен га, то порядок элемента а равен га тогда и только тогда, когда (к, га) = 1. Следовательно, если а - элемент порядка га, то

«?"()== П (-сс").

(п, ft) = l

ls;ft<n

Отсюда видно, что функция Эйлера ф (га) равна числу чисел, мень-1ПИХ га и взаимно простых с п.

Перечисленные свойства круговых многочленов оказываются очень полезными для упрощения вычислений. На основании свойства 4.341 вычисления могут быть сведены к случаю, когда га является произведением различных простых множителей. Для га > 1 имеем

(4.36) (х) = П (1 - x"*)tW mod хФ(")/2+1.

Вычисления по модулю х<р(")/+ позволяют с минимальными усилиями определить первую половину коэффициентов кругового многочлена. Вторая половина определяется затем согласно свойству 4.346 симметричным образом. Свойства 4.347 и 4.348 полезны для проверки результатов.

4.37. Пример. Определим Q() и (Х").

(х) =(?<в(х"), ф(6) = 2, (?<в = 1-х + х2.

((105, ? (р (105) = ф (3.5 • 7) = 2 • 4 • 6 = 48.

/)<105, /N (1-хЗ) (1-х6)(1-х7) (1-105)

(1 -х) (1-а;1б) (1-(1-х38) -- = (1 + X + х2) (1 - х8) (1 - х) (1 + х") (1 + х21) mod х = S (1 4- X + х2) (1 - х - х + 15 а.20 а.21 22) od xs.

то ( - 1) =

4.345. Согласно свойствам 4.342 и 4.344,

Q(n) (х2) I 1-х"**