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

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

[math]\displaystyle{ \Phi_n(x)=\prod_k(x-\xi^k_n) }[/math]

где

[math]\displaystyle{ \xi^k_n=\cos\frac{2\pi k}n+i\sin\frac{2\pi k}n }[/math]

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

Свойства

• Коэффициенты кругового многочлена являются целыми числами.
• Степень кругового многочлена [math]\displaystyle{ \mathop{\mathrm{deg}}\, \Phi_n=\varphi(n) }[/math], где [math]\displaystyle{ \varphi }[/math] — функция Эйлера.
• Круговой многочлен удовлетворяет соотношению

[math]\displaystyle{ \prod_{d|n} \Phi_{d}(x)=x^n - 1 }[/math]

где произведение берется по всем положительным делителям [math]\displaystyle{ d }[/math] числа [math]\displaystyle{ n }[/math], включая единицу и само [math]\displaystyle{ n }[/math]. Это равенство можно переписать в следующем виде:

[math]\displaystyle{ \Phi_n(x)=\frac{x^n - 1}{\prod_{d|n, \, d\lt n} \Phi_d(x)}. }[/math]

• Для многочлена [math]\displaystyle{ \Phi_n(x) }[/math] можно указать явное выражение через функцию Мёбиуса:

[math]\displaystyle{ \Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)} }[/math]

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

[math]\displaystyle{ \Phi_n(x)=\frac{x^p-1}{x-1}=x^{p-1}+x^{p-2}+\cdots+1 }[/math]

• Если [math]\displaystyle{ n=2m }[/math], где [math]\displaystyle{ m }[/math] — нечётное число, большее одного то:

[math]\displaystyle{ \Phi_{2m}(x) = \Phi_{m}(-x) }[/math]

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

[math]\displaystyle{ \Phi_n(x) = \Phi_m(x^d) }[/math]

• Если [math]\displaystyle{ p }[/math] - простое число, не делящее [math]\displaystyle{ n }[/math], то

[math]\displaystyle{ \Phi_{pn}(x) = \frac{\Phi_n(x^p)}{\Phi_n(x)} }[/math]

• Над полем рациональных чисел все многочлены [math]\displaystyle{ \Phi_n(x) }[/math] неприводимы, но над конечными простыми полями эти многочлены могут быть приводимы.Так, если [math]\displaystyle{ p }[/math] - простое число, то по модулю [math]\displaystyle{ p }[/math] многочлен [math]\displaystyle{ \Phi_{p-1}(x) }[/math] разлагается на линейные множители, а многочлен [math]\displaystyle{ \Phi_{p+1}(x) }[/math] раскладывается в произведение (различных) многочленов степени 2 (неприводимых над кольцом [math]\displaystyle{ \mathbb{Z}_p }[/math]), со свободными членами, равными 1.
  • Например:

[math]\displaystyle{ \Phi_{8}(x)=x^4+1=(x^2+4x+1)(x^2-4x+1)\pmod{7} }[/math]

[math]\displaystyle{ \Phi_{12}(x)=x^4-x^2+1=(x^2+5x+1)(x^2-5x+1)\pmod{11} }[/math]

[math]\displaystyle{ \Phi_{14}(x)=(x^2-6x+1)(x^2-5x+1)(x^2-3x+1)\pmod{13} }[/math]

• Более общим является следующий факт: Если p — простое число, n — натуральное, то многочлен [math]\displaystyle{ \Phi_{\Phi_n(p)}(x) }[/math] по модулю p раскладывается в произведение многочленов степени n. Если n ещё и простое, то многочлены степени n, участвующие в разложении, неприводимы над кольцом [math]\displaystyle{ \mathbb{Z}_p }[/math].

Примеры

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

[math]\displaystyle{ \Phi_1(x) = x - 1 }[/math]

[math]\displaystyle{ \Phi_2(x) = x + 1 }[/math]

[math]\displaystyle{ \Phi_3(x) = x^2 + x + 1 }[/math]

[math]\displaystyle{ \Phi_4(x) = x^2 + 1 }[/math]

[math]\displaystyle{ \Phi_5(x) = x^4 + x^3 + x^2 + x +1 }[/math]

[math]\displaystyle{ \Phi_6(x) = x^2 - x + 1 }[/math]

[math]\displaystyle{ \Phi_7(x) = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 }[/math]

[math]\displaystyle{ \Phi_8(x) = x^4 + 1 }[/math]

[math]\displaystyle{ \Phi_9(x) = x^6 + x^3 + 1 }[/math]

[math]\displaystyle{ \Phi_{10}(x) = x^4 - x^3 + x^2 - x + 1 }[/math]

[math]\displaystyle{ \Phi_{11}(x) = x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 }[/math]

[math]\displaystyle{ \Phi_{12}(x) = x^4 - x^2 + 1 }[/math]

[math]\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 }[/math]

[math]\displaystyle{ \Phi_{14}(x) = x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 }[/math]

[math]\displaystyle{ \Phi_{15}(x) = x^8 - x^7 + x^5 - x^4 + x^3 - x + 1 }[/math]

[math]\displaystyle{ \Phi_{16}(x) = x^8 + 1 }[/math]

[math]\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 }[/math]

[math]\displaystyle{ \Phi_{18}(x) = x^6 - x^3 + 1 }[/math]

[math]\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 }[/math]

[math]\displaystyle{ \Phi_{20}(x) = x^8 - x^6 + x^4 - x^2 + 1 }[/math]

[math]\displaystyle{ \Phi_{21}(x) = x^{12} - x^{11} + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1 }[/math]

[math]\displaystyle{ \Phi_{22}(x) = x^{10} - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 }[/math]

[math]\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 }[/math]

[math]\displaystyle{ \Phi_{24}(x) = x^8 - x^4 + 1 }[/math]

[math]\displaystyle{ \Phi_{25}(x) = x^{20} + x^{15} + x^{10} + x^5 + 1 }[/math]

[math]\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 }[/math]

[math]\displaystyle{ \Phi_{27}(x) = x^{18} + x^9 + 1 }[/math]

[math]\displaystyle{ \Phi_{28}(x) = x^{12} - x^{10} + x^8 - x^6 + x^4 - x^2 + 1 }[/math]

[math]\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 }[/math]

[math]\displaystyle{ \Phi_{30}(x) = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1 }[/math]

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

[math]\displaystyle{ \begin{align}\Phi_{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\end{align} }[/math]

Приложения

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

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

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

[math]\displaystyle{ \prod\limits_{a\in K^*}(x-a) = x^n-1 }[/math],

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

Так как

[math]\displaystyle{ x^n - 1 = \prod\limits_{d|n}\Phi_d(x) }[/math] и [math]\displaystyle{ \deg \Phi_d(x) =\varphi(d)\geqslant 1 }[/math],

то многочлен [math]\displaystyle{ \Phi_n(x) }[/math] имеет ровно [math]\displaystyle{ \varphi(n) }[/math] корней в [math]\displaystyle{ K }[/math] (и, значит, хотя бы один). Его корни являются элементами группы [math]\displaystyle{ K^* }[/math] порядка [math]\displaystyle{ n }[/math], то есть циклическая группа, образованная любым из них, содержит [math]\displaystyle{ n }[/math] различных элементов и должна совпадать со всей группой [math]\displaystyle{ K^* }[/math], откуда следует цикличность этой группы.

См. также

• Круговое поле

Литература

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987.
• Ван дер Варден Б. Л. Алгебра. М.: Мир, 1975.