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

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

${\mathrm{\Phi }}_n(x)=\prod _k(x-{\xi }_n^k)$

где

${\xi }_n^k=\cos \frac{2\pi k}{n}+i\sin \frac{2\pi k}{n}$

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

Свойства

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

$\prod _{d|n}{\mathrm{\Phi }}_d(x)=x^n-1$

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

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

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

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

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

${\mathrm{\Phi }}_n(x)=\frac{x^p-1}{x-1}=x^{p-1}+x^{p-2}+\cdots +1$

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

${\mathrm{\Phi }}_{2m}(x)={\mathrm{\Phi }}_m(-x)$

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

${\mathrm{\Phi }}_n(x)={\mathrm{\Phi }}_m(x^d)$

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

${\mathrm{\Phi }}_{pn}(x)=\frac{{\mathrm{\Phi }}_n(x^p)}{{\mathrm{\Phi }}_n(x)}$

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

${\mathrm{\Phi }}_8(x)=x^4+1=(x^2+4x+1)(x^2-4x+1)(\mathrm{mod}7)$

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

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

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

$|x-1{|}^{\phi (n)}⩽{\mathrm{\Phi }}_n(x)⩽|x+1{|}^{\phi (n)}$

Примеры

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

${\mathrm{\Phi }}_1(x)=x-1$

${\mathrm{\Phi }}_2(x)=x+1$

${\mathrm{\Phi }}_3(x)=x^2+x+1$

${\mathrm{\Phi }}_4(x)=x^2+1$

${\mathrm{\Phi }}_5(x)=x^4+x^3+x^2+x+1$

${\mathrm{\Phi }}_6(x)=x^2-x+1$

${\mathrm{\Phi }}_7(x)=x^6+x^5+x^4+x^3+x^2+x+1$

${\mathrm{\Phi }}_8(x)=x^4+1$

${\mathrm{\Phi }}_9(x)=x^6+x^3+1$

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

${\mathrm{\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 }}_{12}(x)=x^4-x^2+1$

${\mathrm{\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 }}_{14}(x)=x^6-x^5+x^4-x^3+x^2-x+1$

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

${\mathrm{\Phi }}_{16}(x)=x^8+1$

${\mathrm{\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 }}_{18}(x)=x^6-x^3+1$

${\mathrm{\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 }}_{20}(x)=x^8-x^6+x^4-x^2+1$

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

${\mathrm{\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 }}_{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 }}_{24}(x)=x^8-x^4+1$

${\mathrm{\Phi }}_{25}(x)=x^{20}+x^{15}+x^{10}+x^5+1$

${\mathrm{\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 }}_{27}(x)=x^{18}+x^9+1$

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

${\mathrm{\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 }}_{30}(x)=x^8+x^7-x^5-x^4-x^3+x+1$

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

$\begin{array}{cc}{\mathrm{\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{array}$

Приложения

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

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

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

$\prod _{a\in K^{*}}(x-a)=x^n-1$,

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

Так как

$x^n-1=\prod _{d|n}{\mathrm{\Phi }}_d(x)$ и $\mathrm{deg}{\mathrm{\Phi }}_d(x)=\phi (d)⩾1$,

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

См. также

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

Литература

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