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

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

${\mathrm{\Phi <!--\; \Phi \; -->}}_n(x)=\underset{k}{\prod <!--\; \prod \; -->}(x-<!--\; -\; -->{\mathrm{\xi <!--\; \xi \; -->}}_n^k)$$\Phi _{n}(x)=\prod _{k}(x-\xi _{n}^{k})$

где

${\mathrm{\xi <!--\; \xi \; -->}}_n^k=\cos <!--\; \; -->\frac{2\mathrm{\pi <!--\; \pi \; -->}k}{n}+i\sin <!--\; \; -->\frac{2\mathrm{\pi <!--\; \pi \; -->}k}{n}$$\xi _{n}^{k}=\cos {\frac {2\pi k}n}+i\sin {\frac {2\pi k}n}$

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

СвойстваПравить

• Коэффициенты кругового многочлена являются целыми числами.
• Степень кругового многочлена $\mathrm{d}\mathrm{e}\mathrm{g}{\mathrm{\Phi <!--\; \Phi \; -->}}_n=\mathrm{\phi <!--\; \phi \; -->}(n)$${\mathop {{\mathrm {deg}}}}\,\Phi _{n}=\varphi (n)$ , где $\mathrm{\phi <!--\; \phi \; -->}$$\varphi$  — функция Эйлера.
• Круговой многочлен удовлетворяет соотношению

$\underset{d|n}{\prod <!--\; \prod \; -->}{\mathrm{\Phi <!--\; \Phi \; -->}}_d(x)=x^n-<!--\; -\; -->1$$\prod _{{d|n}}\Phi _{{d}}(x)=x^{n}-1$ 

где произведение берется по всем положительным делителям $d$$d$  числа $n$$n$ , включая единицу и само $n$$n$ . Это равенство можно переписать в следующем виде:

$\Phi _{n}(x)={\frac {x^{n}-1}{\prod _{{d|n,\,d<n}}\Phi _{d}(x)}}.$ 

• Для многочлена ${\mathrm{\Phi <!--\; \Phi \; -->}}_n(x)$$\Phi _{n}(x)$  можно указать явное выражение через функцию Мёбиуса:

${\mathrm{\Phi <!--\; \Phi \; -->}}_n(x)=\underset{d|n}{\prod <!--\; \prod \; -->}(x^d-<!--\; -\; -->1{)}^{\mathrm{\mu <!--\; \mu \; -->}(n/d)}$$\Phi _{n}(x)=\prod _{{d|n}}(x^{d}-1)^{{\mu (n/d)}}$ 

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

${\mathrm{\Phi <!--\; \Phi \; -->}}_n(x)=\frac{x^p-<!--\; -\; -->1}{x-<!--\; -\; -->1}=x^{p-<!--\; -\; -->1}+x^{p-<!--\; -\; -->2}+\cdots <!--\; \cdots \; -->+1$$\Phi _{n}(x)={\frac {x^{p}-1}{x-1}}=x^{p-1}+x^{p-2}+\cdots +1$ 

• Если $n=2m$$n=2m$ , где $m$$m$  — нечётное число, большее одного то:

${\mathrm{\Phi <!--\; \Phi \; -->}}_{2m}(x)={\mathrm{\Phi <!--\; \Phi \; -->}}_m(-<!--\; -\; -->x)$$\Phi _{2m}(x)=\Phi _{m}(-x)$ 

• Если $m$$m$  - максимальное натуральное число, делящее $n$$n$ , и свободное от квадратов (радикал $n$$n$ ), и $d=n/m$$d=n/m$ , то

${\mathrm{\Phi <!--\; \Phi \; -->}}_n(x)={\mathrm{\Phi <!--\; \Phi \; -->}}_m(x^d)$$\Phi _{n}(x)=\Phi _{m}(x^{d})$ 

• Если $p$$p$  - простое число, не делящее $n$$n$ , то

${\mathrm{\Phi <!--\; \Phi \; -->}}_{pn}(x)=\frac{{\mathrm{\Phi <!--\; \Phi \; -->}}_n(x^p)}{{\mathrm{\Phi <!--\; \Phi \; -->}}_n(x)}$$\Phi _{pn}(x)={\frac {\Phi _{n}(x^{p})}{\Phi _{n}(x)}}$ 

• Над полем рациональных чисел все многочлены ${\mathrm{\Phi <!--\; \Phi \; -->}}_n(x)$$\Phi _{n}(x)$  неприводимы, но над конечными простыми полями эти многочлены могут быть приводимы.Так, если $p$$p$  - простое число, то по модулю $p$$p$  многочлен ${\mathrm{\Phi <!--\; \Phi \; -->}}_{p-<!--\; -\; -->1}(x)$$\Phi _{p-1}(x)$  разлагается на линейные множители, а многочлен ${\mathrm{\Phi <!--\; \Phi \; -->}}_{p+1}(x)$$\Phi _{p+1}(x)$  раскладывается в произведение (различных) многочленов степени 2 (неприводимых над кольцом ${\mathbb{Z}}_p$$\mathbb {Z} _{p}$ ), со свободными членами, равными 1.
  • Например:

${\mathrm{\Phi <!--\; \Phi \; -->}}_8(x)=x^4+1=(x^2+4x+1)(x^2-<!--\; -\; -->4x+1)(\mathrm{mod}7)$$\Phi _{8}(x)=x^{4}+1=(x^{2}+4x+1)(x^{2}-4x+1){\pmod {7}}$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{12}(x)=x^4-<!--\; -\; -->x^2+1=(x^2+5x+1)(x^2-<!--\; -\; -->5x+1)(\mathrm{mod}11)$$\Phi _{12}(x)=x^{4}-x^{2}+1=(x^{2}+5x+1)(x^{2}-5x+1){\pmod {11}}$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{14}(x)=(x^2-<!--\; -\; -->6x+1)(x^2-<!--\; -\; -->5x+1)(x^2-<!--\; -\; -->3x+1)(\mathrm{mod}13)$$\Phi _{14}(x)=(x^{2}-6x+1)(x^{2}-5x+1)(x^{2}-3x+1){\pmod {13}}$ 

• Более общим является следующий факт: Если p — простое число, n — натуральное, то многочлен ${\mathrm{\Phi <!--\; \Phi \; -->}}_{{\mathrm{\Phi <!--\; \Phi \; -->}}_n(p)}(x)$$\Phi _{\Phi _{n}(p)}(x)$  по модулю p раскладывается в произведение многочленов степени n. Если n ещё и простое, то многочлены степени n, участвующие в разложении, неприводимы над кольцом ${\mathbb{Z}}_p$$\mathbb {Z} _{p}$ .

ПримерыПравить

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

${\mathrm{\Phi <!--\; \Phi \; -->}}_1(x)=x-<!--\; -\; -->1$$\Phi _{1}(x)=x-1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_2(x)=x+1$$\Phi _{2}(x)=x+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_3(x)=x^2+x+1$$\Phi _{3}(x)=x^{2}+x+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_4(x)=x^2+1$$\Phi _{4}(x)=x^{2}+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_5(x)=x^4+x^3+x^2+x+1$$\Phi _{5}(x)=x^{4}+x^{3}+x^{2}+x+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_6(x)=x^2-<!--\; -\; -->x+1$$\Phi _{6}(x)=x^{2}-x+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_7(x)=x^6+x^5+x^4+x^3+x^2+x+1$$\Phi _{7}(x)=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_8(x)=x^4+1$$\Phi _{8}(x)=x^{4}+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_9(x)=x^6+x^3+1$$\Phi _{9}(x)=x^{6}+x^{3}+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{10}(x)=x^4-<!--\; -\; -->x^3+x^2-<!--\; -\; -->x+1$$\Phi _{10}(x)=x^{4}-x^{3}+x^{2}-x+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{11}(x)=x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1$$\Phi _{11}(x)=x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{12}(x)=x^4-<!--\; -\; -->x^2+1$$\Phi _{12}(x)=x^{4}-x^{2}+1$ 

${\mathrm{\Phi <!--\; \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$$\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$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{14}(x)=x^6-<!--\; -\; -->x^5+x^4-<!--\; -\; -->x^3+x^2-<!--\; -\; -->x+1$$\Phi _{14}(x)=x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{15}(x)=x^8-<!--\; -\; -->x^7+x^5-<!--\; -\; -->x^4+x^3-<!--\; -\; -->x+1$$\Phi _{15}(x)=x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{16}(x)=x^8+1$$\Phi _{16}(x)=x^{8}+1$ 

${\mathrm{\Phi <!--\; \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$$\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$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{18}(x)=x^6-<!--\; -\; -->x^3+1$$\Phi _{18}(x)=x^{6}-x^{3}+1$ 

${\mathrm{\Phi <!--\; \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$$\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$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{20}(x)=x^8-<!--\; -\; -->x^6+x^4-<!--\; -\; -->x^2+1$$\Phi _{20}(x)=x^{8}-x^{6}+x^{4}-x^{2}+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{21}(x)=x^{12}-<!--\; -\; -->x^{11}+x^9-<!--\; -\; -->x^8+x^6-<!--\; -\; -->x^4+x^3-<!--\; -\; -->x+1$$\Phi _{21}(x)=x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{4}+x^{3}-x+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{22}(x)=x^{10}-<!--\; -\; -->x^9+x^8-<!--\; -\; -->x^7+x^6-<!--\; -\; -->x^5+x^4-<!--\; -\; -->x^3+x^2-<!--\; -\; -->x+1$$\Phi _{22}(x)=x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1$ 

${\mathrm{\Phi <!--\; \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$$\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$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{24}(x)=x^8-<!--\; -\; -->x^4+1$$\Phi _{24}(x)=x^{8}-x^{4}+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{25}(x)=x^{20}+x^{15}+x^{10}+x^5+1$$\Phi _{25}(x)=x^{20}+x^{15}+x^{10}+x^{5}+1$ 

${\mathrm{\Phi <!--\; \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$$\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$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{27}(x)=x^{18}+x^9+1$$\Phi _{27}(x)=x^{18}+x^{9}+1$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{28}(x)=x^{12}-<!--\; -\; -->x^{10}+x^8-<!--\; -\; -->x^6+x^4-<!--\; -\; -->x^2+1$$\Phi _{28}(x)=x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+1$ 

${\mathrm{\Phi <!--\; \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$$\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$ 

${\mathrm{\Phi <!--\; \Phi \; -->}}_{30}(x)=x^8+x^7-<!--\; -\; -->x^5-<!--\; -\; -->x^4-<!--\; -\; -->x^3+x+1$$\Phi _{30}(x)=x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1$ 

Из этой сводки можно сделать вывод, что ненулевые коэффициенты кругового многочлена всегда равны $\pm <!--\; \pm \; -->1,$$\pm 1,$  но это предположение неверно. Первый контрпример даёт 105-й многочлен:

${\begin{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+1\end{aligned}}$ 

ПриложенияПравить

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

Теорема. Мультипликативная группа $K^{\ast <!--\; \ast \; -->}$$K^{*}$  конечного поля $K$$K$  является циклической группой.

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

$\underset{a\in <!--\; \in \; -->K^{\ast <!--\; \ast \; -->}}{\prod <!--\; \prod \; -->}(x-<!--\; -\; -->a)=x^n-<!--\; -\; -->1$$\prod \limits _{a\in K^{*}}(x-a)=x^{n}-1$ ,

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

Так как

$x^n-<!--\; -\; -->1=\underset{d|n}{\prod <!--\; \prod \; -->}{\mathrm{\Phi <!--\; \Phi \; -->}}_d(x)$$x^{n}-1=\prod \limits _{d|n}\Phi _{d}(x)$  и $\mathrm{deg}<!--\; \; -->{\mathrm{\Phi <!--\; \Phi \; -->}}_d(x)=\mathrm{\phi <!--\; \phi \; -->}(d)⩾<!--\; ⩾\; -->1$$\deg \Phi _{d}(x)=\varphi (d)\geqslant 1$ ,

то многочлен ${\mathrm{\Phi <!--\; \Phi \; -->}}_n(x)$$\Phi _{n}(x)$  имеет ровно $\mathrm{\phi <!--\; \phi \; -->}(n)$$\varphi (n)$  корней в $K$$K$  (и, значит, хотя бы один). Его корни являются элементами группы $K^{\ast <!--\; \ast \; -->}$$K^{*}$  порядка $n$$n$ , то есть циклическая группа, образованная любым из них, содержит $n$$n$  различных элементов и должна совпадать со всей группой $K^{\ast <!--\; \ast \; -->}$$K^{*}$ , откуда следует цикличность этой группы.

См. такжеПравить

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

ЛитератураПравить

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