Круговой многочлен

Круговой многочлен, или многочлен деления круга, — многочлен вида

Φ n ( x ) = ∏ k ( x − ξ n k ) {displaystyle Phi _{n}(x)=prod _{k}(x-xi _{n}^{k})}

где

ξ n k = cos ⁡ 2 π k n + i sin ⁡ 2 π k n {displaystyle xi _{n}^{k}=cos {frac {2pi k}{n}}+isin {frac {2pi k}{n}}}

представляет собой корень степени n {displaystyle n} из единицы, а произведение берётся по всем натуральным числам k {displaystyle k} , меньшим n {displaystyle n} и взаимно простым с n {displaystyle n} .

Свойства

Коэффициенты кругового многочлена являются целыми числами.
Степень кругового многочлена d e g Φ n = φ ( n ) {displaystyle mathop {mathrm {deg} } ,Phi _{n}=varphi (n)} , где φ {displaystyle varphi } — функция Эйлера.
Круговой многочлен удовлетворяет соотношению

∏ d | n Φ d ( x ) = x n − 1 {displaystyle prod _{d|n}Phi _{d}(x)=x^{n}-1} где произведение берется по всем положительным делителям d {displaystyle d} числа n {displaystyle n} , включая единицу и само n {displaystyle n} . Это равенство можно переписать в следующем виде: Φ n ( x ) = x n − 1 ∏ d | n , d < n Φ d ( x ) . {displaystyle Phi _{n}(x)={frac {x^{n}-1}{prod _{d|n,,d<n}Phi _{d}(x)}}.}

Для многочлена Φ n ( x ) {displaystyle Phi _{n}(x)} можно указать явное выражение через функцию Мёбиуса:

Φ n ( x ) = ∏ d | n ( x d − 1 ) μ ( n / d ) {displaystyle Phi _{n}(x)=prod _{d|n}(x^{d}-1)^{mu (n/d)}}

Частный случай предыдущей формулы: если n = p {displaystyle n=p} — простое число, то

Φ n ( x ) = x p − 1 x − 1 = x p − 1 + x p − 2 + ⋯ + 1 {displaystyle Phi _{n}(x)={frac {x^{p}-1}{x-1}}=x^{p-1}+x^{p-2}+cdots +1}

Если n = 2 m {displaystyle n=2m} , где m {displaystyle m} — нечётное число, то:

Φ 2 m ( x ) = Φ m ( − x ) {displaystyle Phi _{2m}(x)=Phi _{m}(-x)}

Если m {displaystyle m} - максимальное натуральное число, делящее n {displaystyle n} , и свободное от квадратов, и d = n / m {displaystyle d=n/m} , то

Φ n ( x ) = Φ m ( x d ) {displaystyle Phi _{n}(x)=Phi _{m}(x^{d})}

Над полем рациональных чисел все многочлены Φ n ( x ) {displaystyle Phi _{n}(x)} неприводимы, но над конечными простыми полями эти многочлены могут быть приводимы.Так, если p {displaystyle p} - простое число, то по модулю p {displaystyle p} многочлен Φ p − 1 ( x ) {displaystyle Phi _{p-1}(x)} разлагается на линейные множители, а многочлен Φ p + 1 ( x ) {displaystyle Phi _{p+1}(x)} раскладывается в произведение (различных) многочленов степени 2 (неприводимых над кольцом Z p {displaystyle mathbb {Z} _{p}} ), со свободными членами, равными 1.
- Например:

Φ 8 ( x ) = x 4 + 1 = ( x 2 + 4 x + 1 ) ( x 2 − 4 x + 1 ) ( mod 7 ) {displaystyle Phi _{8}(x)=x^{4}+1=(x^{2}+4x+1)(x^{2}-4x+1){pmod {7}}} Φ 12 ( x ) = x 4 − x 2 + 1 = ( x 2 + 5 x + 1 ) ( x 2 − 5 x + 1 ) ( mod 11 ) {displaystyle Phi _{12}(x)=x^{4}-x^{2}+1=(x^{2}+5x+1)(x^{2}-5x+1){pmod {11}}} Φ 14 ( x ) = ( x 2 − 6 x + 1 ) ( x 2 − 5 x + 1 ) ( x 2 − 3 x + 1 ) ( mod 13 ) {displaystyle Phi _{14}(x)=(x^{2}-6x+1)(x^{2}-5x+1)(x^{2}-3x+1){pmod {13}}}

Более общим является следующий факт: Если p — простое число, n — натуральное, то многочлен Φ Φ n ( p ) ( x ) {displaystyle Phi _{Phi _{n}(p)}(x)} по модулю p раскладывается в произведение многочленов степени n. Если n ещё и простое, то многочлены степени n, участвующие в разложении, неприводимы над кольцом Z p {displaystyle mathbb {Z} _{p}} .

Примеры

Приведём сводку первых 30 круговых многочленов.

Φ 1 ( x ) = x − 1 {displaystyle Phi _{1}(x)=x-1} Φ 2 ( x ) = x + 1 {displaystyle Phi _{2}(x)=x+1} Φ 3 ( x ) = x 2 + x + 1 {displaystyle Phi _{3}(x)=x^{2}+x+1} Φ 4 ( x ) = x 2 + 1 {displaystyle Phi _{4}(x)=x^{2}+1} Φ 5 ( x ) = x 4 + x 3 + x 2 + x + 1 {displaystyle Phi _{5}(x)=x^{4}+x^{3}+x^{2}+x+1} Φ 6 ( x ) = x 2 − x + 1 {displaystyle Phi _{6}(x)=x^{2}-x+1} Φ 7 ( x ) = x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 {displaystyle Phi _{7}(x)=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1} Φ 8 ( x ) = x 4 + 1 {displaystyle Phi _{8}(x)=x^{4}+1} Φ 9 ( x ) = x 6 + x 3 + 1 {displaystyle Phi _{9}(x)=x^{6}+x^{3}+1} Φ 10 ( x ) = x 4 − x 3 + x 2 − x + 1 {displaystyle Phi _{10}(x)=x^{4}-x^{3}+x^{2}-x+1} Φ 11 ( x ) = x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 {displaystyle Phi _{11}(x)=x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1} Φ 12 ( x ) = x 4 − x 2 + 1 {displaystyle Phi _{12}(x)=x^{4}-x^{2}+1} Φ 13 ( x ) = x 12 + x 11 + x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 {displaystyle Phi _{13}(x)=x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1} Φ 14 ( x ) = x 6 − x 5 + x 4 − x 3 + x 2 − x + 1 {displaystyle Phi _{14}(x)=x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1} Φ 15 ( x ) = x 8 − x 7 + x 5 − x 4 + x 3 − x + 1 {displaystyle Phi _{15}(x)=x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1} Φ 16 ( x ) = x 8 + 1 {displaystyle Phi _{16}(x)=x^{8}+1} Φ 17 ( x ) = x 16 + x 15 + x 14 + x 13 + x 12 + x 11 + x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 {displaystyle Phi _{17}(x)=x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1} Φ 18 ( x ) = x 6 − x 3 + 1 {displaystyle Phi _{18}(x)=x^{6}-x^{3}+1} Φ 19 ( x ) = x 18 + x 17 + x 16 + x 15 + x 14 + x 13 + x 12 + x 11 + x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 {displaystyle Phi _{19}(x)=x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1} Φ 20 ( x ) = x 8 − x 6 + x 4 − x 2 + 1 {displaystyle Phi _{20}(x)=x^{8}-x^{6}+x^{4}-x^{2}+1} Φ 21 ( x ) = x 12 − x 11 + x 9 − x 8 + x 6 − x 4 + x 3 − x + 1 {displaystyle Phi _{21}(x)=x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{4}+x^{3}-x+1} Φ 22 ( x ) = x 10 − x 9 + x 8 − x 7 + x 6 − x 5 + x 4 − x 3 + x 2 − x + 1 {displaystyle Phi _{22}(x)=x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1} Φ 23 ( x ) = x 22 + x 21 + x 20 + x 19 + x 18 + x 17 + x 16 + x 15 + x 14 + x 13 + x 12 + x 11 + x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 {displaystyle Phi _{23}(x)=x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1} Φ 24 ( x ) = x 8 − x 4 + 1 {displaystyle Phi _{24}(x)=x^{8}-x^{4}+1} Φ 25 ( x ) = x 20 + x 15 + x 10 + x 5 + 1 {displaystyle Phi _{25}(x)=x^{20}+x^{15}+x^{10}+x^{5}+1} Φ 26 ( x ) = x 12 − x 11 + x 10 − x 9 + x 8 − x 7 + x 6 − x 5 + x 4 − x 3 + x 2 − x + 1 {displaystyle Phi _{26}(x)=x^{12}-x^{11}+x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1} Φ 27 ( x ) = x 18 + x 9 + 1 {displaystyle Phi _{27}(x)=x^{18}+x^{9}+1} Φ 28 ( x ) = x 12 − x 10 + x 8 − x 6 + x 4 − x 2 + 1 {displaystyle Phi _{28}(x)=x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+1} Φ 29 ( x ) = x 28 + x 27 + x 26 + x 25 + x 24 + x 23 + x 22 + x 21 + x 20 + x 19 + x 18 + x 17 + x 16 + x 15 + x 14 + x 13 + x 12 + x 11 + x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 {displaystyle Phi _{29}(x)=x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1} Φ 30 ( x ) = x 8 + x 7 − x 5 − x 4 − x 3 + x + 1 {displaystyle Phi _{30}(x)=x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1}

Из этой сводки можно сделать вывод, что ненулевые коэффициенты кругового многочлена всегда равны ± 1 , {displaystyle pm 1,} но это предположение неверно. Первый контрпример даёт 105-й многочлен:

Φ 105 ( x ) = x 48 + x 47 + x 46 − x 43 − x 42 − 2 x 41 − x 40 − x 39 + x 36 + x 35 + x 34 + x 33 + x 32 + x 31 − x 28 − x 26 − x 24 − x 22 − x 20 + x 17 + x 16 + x 15 + x 14 + x 13 + x 12 − x 9 − x 8 − 2 x 7 − x 6 − x 5 + x 2 + x + 1 {displaystyle {egin{aligned}Phi _{105}(x)=&;x^{48}+x^{47}+x^{46}-x^{43}-x^{42}-2x^{41}-x^{40}-x^{39}+x^{36}+x^{35}+x^{34}&{}+x^{33}+x^{32}+x^{31}-x^{28}-x^{26}-x^{24}-x^{22}-x^{20}+x^{17}+x^{16}+x^{15}&{}+x^{14}+x^{13}+x^{12}-x^{9}-x^{8}-2x^{7}-x^{6}-x^{5}+x^{2}+x+1end{aligned}}}

Приложения

Одним из важнейших приложений круговых многочленов является теорема о мультипликативной группе конечного поля:

Теорема. Мультипликативная группа K ∗ {displaystyle K^{*}} конечного поля K {displaystyle K} является циклической группой.

Доказательство. Пусть поле K {displaystyle K} состоит из n + 1 {displaystyle n+1} элемента, тогда его мультипликативная группа (группа обратимых элементов) K ∗ {displaystyle K^{*}} содержит все элементы поля, кроме нуля, то есть состоит из n {displaystyle n} элементов. По теореме Лагранжа порядок элемента группы делит порядок этой группы, следовательно, для любого элемента a ∈ K ∗ {displaystyle ain K^{*}} выполнено a n = 1 {displaystyle a^{n}=1} , то есть все элементы из K ∗ {displaystyle K^{*}} являются корнями уравнения x n − 1 = 0 {displaystyle x^{n}-1=0} . Тогда

∏ a ∈ K ∗ ( x − a ) = x n − 1 {displaystyle prod limits _{ain K^{*}}(x-a)=x^{n}-1} ,

так как все корни левой части являются корнями правой части и степени и старшие члены обоих многочленов равны.

Так как

x n − 1 = ∏ d | n Φ d ( x ) {displaystyle x^{n}-1=prod limits _{d|n}Phi _{d}(x)} и deg ⁡ Φ d ( x ) = φ ( d ) ⩾ 1 {displaystyle deg Phi _{d}(x)=varphi (d)geqslant 1} ,

то многочлен Φ n ( x ) {displaystyle Phi _{n}(x)} имеет ровно φ ( n ) {displaystyle varphi (n)} корней в K {displaystyle K} (и, значит, хотя бы один). Его корни являются элементами группы K ∗ {displaystyle K^{*}} порядка n {displaystyle n} , то есть циклическая группа, образованная любым из них, содержит n {displaystyle n} различных элементов и должна совпадать со всей группой K ∗ {displaystyle K^{*}} , откуда следует цикличность этой группы.