Циклотомный полином

В математике n - й круговой полином для любого положительного целого числа n — это уникальный неприводимый многочлен с целыми коэффициентами является делителем , который $x^{n}-1$ и не является делителем $x^{k}-1$ для любого k < n . его корни Все — это n-ные примитивные корни из единицы. $e^{2i\pi {\frac {k}{n}}}$, где k пробегает положительные целые числа, не большие n и взаимно простые с n (а i — мнимая единица ). Другими словами, n- й круговой полином равен

$\Phi _{n}(x)=\prod _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\left(x-e^{2i\pi {\frac {k}{n}}}\right).$

Его также можно определить как унитарный многочлен с целыми коэффициентами, который является минимальным многочленом над полем рациональных чисел любого примитивного корня n -й степени из единицы ( $e^{2i\pi /n}$ является примером такого корня).

Важным соотношением, связывающим круговые многочлены и примитивные корни из единицы, является

$\prod _{d\mid n}\Phi _{d}(x)=x^{n}-1,$

показывая, что х является корнем $x^{n}-1$ тогда и только тогда, когда это d-   й примитивный корень из единицы для некоторого d, который делит n .

Примеры

Если n — простое число , то

$\Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}.$

Если n = 2 p, где p — простое число, отличное от 2, то

$\Phi _{2p}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}.$

Для n до 30 круговыми полиномами являются:

${\begin{aligned}\Phi _{1}(x)&=x-1\\\Phi _{2}(x)&=x+1\\\Phi _{3}(x)&=x^{2}+x+1\\\Phi _{4}(x)&=x^{2}+1\\\Phi _{5}(x)&=x^{4}+x^{3}+x^{2}+x+1\\\Phi _{6}(x)&=x^{2}-x+1\\\Phi _{7}(x)&=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Phi _{8}(x)&=x^{4}+1\\\Phi _{9}(x)&=x^{6}+x^{3}+1\\\Phi _{10}(x)&=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\\\Phi _{12}(x)&=x^{4}-x^{2}+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\\\Phi _{14}(x)&=x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1\\\Phi _{15}(x)&=x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1\\\Phi _{16}(x)&=x^{8}+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\\\Phi _{18}(x)&=x^{6}-x^{3}+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\\\Phi _{20}(x)&=x^{8}-x^{6}+x^{4}-x^{2}+1\\\Phi _{21}(x)&=x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{4}+x^{3}-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\\\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}\\&\qquad \quad +x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Phi _{24}(x)&=x^{8}-x^{4}+1\\\Phi _{25}(x)&=x^{20}+x^{15}+x^{10}+x^{5}+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\\\Phi _{27}(x)&=x^{18}+x^{9}+1\\\Phi _{28}(x)&=x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+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}\\&\qquad \quad +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 _{30}(x)&=x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1.\end{aligned}}$

Случай 105-го кругового многочлена интересен тем, что 105 — это наименьшее положительное целое число, которое является произведением трех различных нечетных простых чисел (3*5*7), и этот многочлен является первым многочленом, имеющим коэффициент, отличный от 1, 0, или -1:

${\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}}$

Характеристики

Основные инструменты

Круговые многочлены представляют собой монические многочлены с целыми коэффициентами, которые неприводимы в поле рациональных чисел. За исключением n, равного 1 или 2, они являются палиндромами четной степени.

Степень $\Phi _{n}$, или, другими словами, число примитивных корней n-й степени из единицы равно $\varphi (n)$, где $\varphi$ — это полная функция Эйлера .

Тот факт, что $\Phi _{n}$ является неприводимым многочленом степени $\varphi (n)$ ринге на $\mathbb {Z} [x]$ является нетривиальным результатом Гаусса . В зависимости от выбранного определения нетривиальным результатом является либо значение степени, либо неприводимость. Случай простого числа n доказать легче, чем общий случай, благодаря критерию Эйзенштейна .

Фундаментальное соотношение, включающее круговые полиномы, следующее:

${\begin{aligned}x^{n}-1&=\prod _{1\leqslant k\leqslant n}\left(x-e^{2i\pi {\frac {k}{n}}}\right)\\&=\prod _{d\mid n}\prod _{1\leqslant k\leqslant n \atop \gcd(k,n)=d}\left(x-e^{2i\pi {\frac {k}{n}}}\right)\\&=\prod _{d\mid n}\Phi _{\frac {n}{d}}(x)=\prod _{d\mid n}\Phi _{d}(x).\end{aligned}}$

это означает, что каждый корень n-й степени из единицы является примитивным корнем d- й степени из единицы для уникального d, делящего n .

Формула обращения Мёбиуса позволяет $\Phi _{n}(x)$ быть выражено в виде явной рациональной дроби:

$\Phi _{n}(x)=\prod _{d\mid n}(x^{d}-1)^{\mu \left({\frac {n}{d}}\right)},$

где $\mu$ — функция Мёбиуса .

Круговой полином $\Phi _{n}(x)$ может быть вычислено путем (точного) деления $x^{n}-1$ круговыми полиномами собственных делителей n, ранее вычисленных рекурсивно тем же методом:

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

(Напомним, что $\Phi _{1}(x)=x-1$.)

Эта формула определяет алгоритм вычисления $\Phi _{n}(x)$ для любого n при условии, что целочисленная факторизация и деление полиномов доступны . Многие системы компьютерной алгебры , такие как SageMath , Maple , Mathematica и PARI/GP , имеют встроенную функцию для вычисления круговых полиномов.

Простые случаи для вычислений

Как отмечалось выше, если n — простое число, то

$\Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}\;.$

Если n — нечетное целое число, большее единицы, то

$\Phi _{2n}(x)=\Phi _{n}(-x)\;.$

В частности, если n = 2 p — дважды нечетное простое число, то (как отмечалось выше)

$\Phi _{n}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}\;.$

Если п = р ^м — степень простого числа (где p — простое число), то

$\Phi _{n}(x)=\Phi _{p}(x^{p^{m-1}})=\sum _{k=0}^{p-1}x^{kp^{m-1}}\;.$

В более общем смысле, если n = p ^м r , где r относительно простое с p , тогда

$\Phi _{n}(x)=\Phi _{pr}(x^{p^{m-1}})\;.$

Эти формулы можно применять неоднократно, чтобы получить простое выражение для любого кругового полинома. $\Phi _{n}(x)$ в терминах кругового многочлена свободного от квадратов индекса: Если q является произведением простых делителей числа n (его радикала ), то

$\Phi _{n}(x)=\Phi _{q}(x^{n/q})\;.$

Это позволяет задавать формулы для n -го кругового многочлена, когда n имеет не более одного нечетного простого множителя: Если p — нечетное простое число, а h и k — положительные целые числа, то

$\Phi _{2^{h}}(x)=x^{2^{h-1}}+1\;,$

$\Phi _{p^{k}}(x)=\sum _{j=0}^{p-1}x^{jp^{k-1}}\;,$

$\Phi _{2^{h}p^{k}}(x)=\sum _{j=0}^{p-1}(-1)^{j}x^{j2^{h-1}p^{k-1}}\;.$

Для других значений n вычисление n -го кругового полинома аналогично сводится к вычислению $\Phi _{q}(x),$ где q — произведение различных нечетных простых делителей числа n . Чтобы разобраться с этим случаем, нужно иметь в виду, что для p простого числа и не делящего n ,

$\Phi _{np}(x)=\Phi _{n}(x^{p})/\Phi _{n}(x)\;.$

Целые числа, выступающие в качестве коэффициентов

Проблема ограничения величин коэффициентов круговых многочленов была предметом ряда научных работ. Несколько обзорных статей дают общий обзор.

Если n имеет не более двух различных нечетных простых делителей, то Миготти показал, что коэффициенты $\Phi _{n}$ все находятся в наборе {1, −1, 0}.

Первый круговой полином для произведения трех разных нечетных простых множителей: $\Phi _{105}(x);$ он имеет коэффициент −2 (см. его выражение выше ). Обратное неверно: $\Phi _{231}(x)=\Phi _{3\times 7\times 11}(x)$ имеет коэффициенты только из {1, −1, 0}.

Если n является произведением большего количества различных нечетных простых множителей, коэффициенты могут увеличиться до очень высоких значений. Например, $\Phi _{15015}(x)=\Phi _{3\times 5\times 7\times 11\times 13}(x)$ имеет коэффициенты от -22 до 23, $\Phi _{255255}(x)=\Phi _{3\times 5\times 7\times 11\times 13\times 17}(x)$, наименьшее n с 6 различными нечетными простыми числами, имеет коэффициенты до 532.

Пусть A ( n ) обозначает максимальное абсолютное значение коэффициентов Φ _n . Известно, что для любого положительного k количество n до x с A ( n ) > n ^к не меньше c ( k )⋅ x для положительного c ( k ), зависящего от k и достаточно большого x . В противоположном направлении, для любой функции ψ( n ), стремящейся к бесконечности с n, мы имеем A ( n ), ограниченную сверху величиной n ^{ψ( п )} почти для всех n .

Комбинация теорем Бейтмана соотв. Воан заявляет что, с одной стороны, для каждого $\varepsilon >0$, у нас есть

$A(n)<e^{\left(n^{(\log 2+\varepsilon )/(\log \log n)}\right)}$

для всех достаточно больших натуральных чисел $n$, а с другой стороны, мы имеем

$A(n)>e^{\left(n^{(\log 2)/(\log \log n)}\right)}$

для бесконечного числа положительных целых чисел $n$. Это означает, в частности, что одномерные полиномы (конкретно $x^{n}-1$ для бесконечного числа положительных целых чисел $n$) может иметь факторы (например, $\Phi _{n}$), коэффициенты которого суперполиномиально больше исходных коэффициентов. Это недалеко от общей границы Ландау-Миньотта .

Формула Гаусса

Пусть n нечетно, не содержит квадратов и больше 3. Тогда:

$4\Phi _{n}(z)=A_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nz^{2}B_{n}^{2}(z)$

где и A _n ( z ), и B _n ( z ) имеют целые коэффициенты, A _n ( z ) имеет степень φ ( n )/2, а B _n ( z ) имеет степень φ ( n )/2 − 2. Кроме того, A _n ( z ) является палиндромом, если его степень четна; если его степень нечетна, то он антипалиндромный. Точно так же B _n ( z ) является палиндромным, если только n не является составным и ≡ 3 (mod 4), и в этом случае он антипалиндромный.

Первые несколько случаев

${\begin{aligned}4\Phi _{5}(z)&=4(z^{4}+z^{3}+z^{2}+z+1)\\&=(2z^{2}+z+2)^{2}-5z^{2}\\[6pt]4\Phi _{7}(z)&=4(z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1)\\&=(2z^{3}+z^{2}-z-2)^{2}+7z^{2}(z+1)^{2}\\[6pt]4\Phi _{11}(z)&=4(z^{10}+z^{9}+z^{8}+z^{7}+z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1)\\&=(2z^{5}+z^{4}-2z^{3}+2z^{2}-z-2)^{2}+11z^{2}(z^{3}+1)^{2}\end{aligned}}$

Формула Лукаса

Пусть n нечетное, свободное от квадратов и больше 3. Тогда

$\Phi _{n}(z)=U_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nzV_{n}^{2}(z)$

где и U _n ( z ), и V _n ( z ) имеют целые коэффициенты, U _n ( z ) имеет степень φ ( n )/2, а V _n ( z ) имеет степень φ ( n )/2 − 1. Это может также быть написанным

$\Phi _{n}\left((-1)^{\frac {n-1}{2}}z\right)=C_{n}^{2}(z)-nzD_{n}^{2}(z).$

Если n четное, не содержит квадратов и больше 2 (это заставляет n /2 быть нечетным),

$\Phi _{\frac {n}{2}}\left(-z^{2}\right)=\Phi _{2n}(z)=C_{n}^{2}(z)-nzD_{n}^{2}(z)$

где C _n ( z ) и D _n ( z ) имеют целые коэффициенты, C _n ( z ) имеет степень φ ( n ), а D _n ( z ) имеет степень φ ( n ) − 1. C _n ( z ) и D _n ( z ) являются палиндромами.

Первые несколько случаев:

${\begin{aligned}\Phi _{3}(-z)&=\Phi _{6}(z)=z^{2}-z+1\\&=(z+1)^{2}-3z\\[6pt]\Phi _{5}(z)&=z^{4}+z^{3}+z^{2}+z+1\\&=(z^{2}+3z+1)^{2}-5z(z+1)^{2}\\[6pt]\Phi _{6/2}(-z^{2})&=\Phi _{12}(z)=z^{4}-z^{2}+1\\&=(z^{2}+3z+1)^{2}-6z(z+1)^{2}\end{aligned}}$

Гипотеза сестры Бейтер

Гипотеза сестры Бейтер касается максимального размера (по абсолютному значению). $A(pqr)$ коэффициентов троичных круговых многочленов $\Phi _{pqr}(x)$ где $3\leq p\leq q\leq r$ это три простых числа.

Циклотомические полиномы над конечным полем и над целыми p -адическими числами

Смотрите также: Конечное поле § Корни из единицы

В конечном поле с простым числом p элементов для любого целого числа n , не кратного p , круговой полином $\Phi _{n}$ разлагается на ${\frac {\varphi (n)}{d}}$ неприводимые многочлены степени d , где $\varphi (n)$ — это функция Эйлера , а d — мультипликативный порядок по p модулю n . В частности, $\Phi _{n}$ является неприводимым тогда и только тогда, когда p является примитивным корнем по модулю n , то есть p не делит n , а его мультипликативный порядок по модулю n равен $\varphi (n)$, степень $\Phi _{n}$.

Эти результаты справедливы и для целых p -адических чисел , поскольку лемма Гензеля позволяет поднять факторизацию по полю с p элементами до факторизации по p -адическим целым числам.

Полиномиальные значения

Если x принимает какое-либо действительное значение, то $\Phi _{n}(x)>0$ для каждого n ≥ 3 (это следует из того факта, что все корни кругового многочлена невещественны при n ≥ 3 ).

Для изучения значений, которые может принимать круговой многочлен, когда x задано целое значение, достаточно рассмотреть только случай n ≥ 3 , поскольку случаи n = 1 и n = 2 тривиальны (имеется $\Phi _{1}(x)=x-1$ и $\Phi _{2}(x)=x+1$).

Для n ≥ 2 имеем

$\Phi _{n}(0)=1,$

$\Phi _{n}(1)=1$ если n не является простой степенью ,

$\Phi _{n}(1)=p$ если $n=p^{k}$ — степень простого числа с k ≥ 1 .

Значения, которые круговой полином $\Phi _{n}(x)$ может принимать другие целые значения x, тесно связано с мультипликативным порядком по модулю простого числа.

Точнее, для простого числа p и целого числа b , взаимно простого с p , мультипликативный порядок b по модулю p является наименьшим положительным целым числом n таким, что p является делителем числа. $b^{n}-1.$ Для b > 1 мультипликативный порядок b по модулю p также является кратчайшим периодом представления 1/ p в системе счисления b (см. Уникальное простое число ; это объясняет выбор обозначений).

Определение мультипликативного порядка подразумевает, что если n — мультипликативный порядок b по модулю p , то p — делитель $\Phi _{n}(b).$ Обратное неверно, но имеет место следующее.

Если n > 0 — целое положительное число, а b > 1 — целое число, то (доказательство см. ниже)

$\Phi _{n}(b)=2^{k}gh,$

где

• k — неотрицательное целое число, всегда равное 0, если b четное. (На самом деле, если n не равно ни 1, ни 2, то k равно либо 0, либо 1. Кроме того, если n не является степенью 2 , то k всегда равно 0)
• g равен 1 или наибольшему нечетному простому множителю числа n .
• h нечетно, взаимно просто с n , и его простые делители — это в точности нечетные простые числа p, такие что n — мультипликативный порядок b по модулю p .

Это означает, что если p — нечетный простой делитель числа $\Phi _{n}(b),$ тогда либо n является делителем p − 1 , либо p является делителем n . В последнем случае $p^{2}$ не делит $\Phi _{n}(b).$

Из теоремы Жигмонди следует, что единственные случаи, когда b > 1 и h = 1, являются

${\begin{aligned}\Phi _{1}(2)&=1\\\Phi _{2}\left(2^{k}-1\right)&=2^{k}&&k>0\\\Phi _{6}(2)&=3\end{aligned}}$

Из приведенной выше факторизации следует, что нечетные простые множители

${\frac {\Phi _{n}(b)}{\gcd(n,\Phi _{n}(b))}}$

— это в точности нечетные простые числа p такие, что n — мультипликативный порядок b по модулю p . Эта дробь может быть четной только тогда, когда b нечетно. В этом случае мультипликативный порядок b по модулю 2 всегда равен 1 .

Существует много пар ( n , b ) с b > 1 таких, что $\Phi _{n}(b)$ является простым. Фактически, гипотеза Буняковского подразумевает, что для каждого n существует бесконечно много b > 1 таких, что $\Phi _{n}(b)$ является простым. См. OEIS : A085398 , где приведен список наименьших b > 1 таких, что $\Phi _{n}(b)$ является простым (наименьшее b > 1 такое, что $\Phi _{n}(b)$ это просто о $\lambda \cdot \varphi (n)$, где $\lambda$ – постоянная Эйлера–Машерони , $\varphi$ — полная функция Эйлера ). См. также OEIS : A206864 для получения списка наименьших простых чисел формы. $\Phi _{n}(b)$ с n > 2 и b > 1 и, в более общем плане, OEIS : A206942 для наименьших положительных целых чисел этой формы.

show Доказательства

Values of $\Phi _{n}(1).$ If $n=p^{k+1}$ is a prime power, then $\Phi _{n}(x)=1+x^{p^{k}}+x^{2p^{k}}+\cdots +x^{(p-1)p^{k}}\qquad {\text{and}}\qquad \Phi _{n}(1)=p.$ If n is not a prime power, let $P(x)=1+x+\cdots +x^{n-1},$ we have $P(1)=n,$ and P is the product of the $\Phi _{k}(x)$ for k dividing n and different of 1. If p is a prime divisor of multiplicity m in n, then $\Phi _{p}(x),\Phi _{p^{2}}(x),\cdots ,\Phi _{p^{m}}(x)$ divide P(x), and their values at 1 are m factors equal to p of $n=P(1).$ As m is the multiplicity of p in n, p cannot divide the value at 1 of the other factors of $P(x).$ Thus there is no prime that divides $\Phi _{n}(1).$ If n is the multiplicative order of b modulo p, then $p\mid \Phi _{n}(b).$ By definition, $p\mid b^{n}-1.$ If $p\nmid \Phi _{n}(b),$ then p would divide another factor $\Phi _{k}(b)$ of $b^{n}-1,$ and would thus divide $b^{k}-1,$ showing that, if there would be the case, n would not be the multiplicative order of b modulo p. The other prime divisors of $\Phi _{n}(b)$ are divisors of n. Let p be a prime divisor of $\Phi _{n}(b)$ such that n is not be the multiplicative order of b modulo p. If k is the multiplicative order of b modulo p, then p divides both $\Phi _{n}(b)$ and $\Phi _{k}(b).$ The resultant of $\Phi _{n}(x)$ and $\Phi _{k}(x)$ may be written $P\Phi _{k}+Q\Phi _{n},$ where P and Q are polynomials. Thus p divides this resultant. As k divides n, and the resultant of two polynomials divides the discriminant of any common multiple of these polynomials, p divides also the discriminant $n^{n}$ of $x^{n}-1.$ Thus p divides n. g and h are coprime. In other words, if p is a prime common divisor of n and $\Phi _{n}(b),$ then n is not the multiplicative order of b modulo p. By Fermat's little theorem, the multiplicative order of b is a divisor of p − 1, and thus smaller than n. g is square-free. In other words, if p is a prime common divisor of n and $\Phi _{n}(b),$ then $p^{2}$ does not divide $\Phi _{n}(b).$ Let n = pm. It suffices to prove that $p^{2}$ does not divide S(b) for some polynomial S(x), which is a multiple of $\Phi _{n}(x).$ We take $S(x)={\frac {x^{n}-1}{x^{m}-1}}=1+x^{m}+x^{2m}+\cdots +x^{(p-1)m}.$ The multiplicative order of b modulo p divides gcd(n, p − 1), which is a divisor of m = n/p. Thus c = bm − 1 is a multiple of p. Now, $S(b)={\frac {(1+c)^{p}-1}{c}}=p+{\binom {p}{2}}c+\cdots +{\binom {p}{p}}c^{p-1}.$ As p is prime and greater than 2, all the terms but the first one are multiples of $p^{2}.$ This proves that $p^{2}\nmid \Phi _{n}(b).$

Приложения

С использованием $\Phi _{n}$, можно дать элементарное доказательство бесконечности простых чисел, конгруэнтных 1 по модулю n , что является частным случаем теоремы Дирихле об арифметических прогрессиях .

show Доказательство

Suppose $p_{1},p_{2},\ldots ,p_{k}$ is a finite list of primes congruent to $1$ modulo $n.$ Let $N=np_{1}p_{2}\cdots p_{k}$ and consider $\Phi _{n}(N)$. Let $q$ be a prime factor of $\Phi _{n}(N)$ (to see that $\Phi _{n}(N)\neq \pm 1$ decompose it into linear factors and note that 1 is the closest root of unity to $N$). Since $\Phi _{n}(x)\equiv \pm 1{\pmod {x}},$ we know that $q$ is a new prime not in the list. We will show that $q\equiv 1{\pmod {n}}.$ Let $m$ be the order of $N$ modulo $q.$ Since $\Phi _{n}(N)\mid N^{n}-1$ we have $N^{n}-1\equiv 0{\pmod {q}}$. Thus $m\mid n$. We will show that $m=n$. Assume for contradiction that $m<n$. Since $\prod _{d\mid m}\Phi _{d}(N)=N^{m}-1\equiv 0{\pmod {q}}$ we have $\Phi _{d}(N)\equiv 0{\pmod {q}},$ for some $d<n$. Then $N$ is a double root of $\prod _{d\mid n}\Phi _{d}(x)\equiv x^{n}-1{\pmod {q}}.$ Thus $N$ must be a root of the derivative so $\left.{\frac {d(x^{n}-1)}{dx}}\right|_{N}\equiv nN^{n-1}\equiv 0{\pmod {q}}.$ But $q\nmid N$ and therefore $q\nmid n.$ This is a contradiction so $m=n$. The order of $N{\pmod {q}},$ which is $n$, must divide $q-1$. Thus $q\equiv 1{\pmod {n}}.$

См. также

• Циклотомное поле
• Факторизация Орифейля
• Корень единства

Дальнейшее чтение

Книга Гаусса Disquisitiones Arithmeticae переведена с латыни на английский и немецкий языки. Немецкое издание включает все его статьи по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.

• Гаусс, Карл Фридрих (1986) [1801], Арифметические исследования , Нью-Йорк: Springer , ISBN  0387962549
• Гаусс, Карл Фридрих (1965) [1801], Исследования по высшей арифметике (Disquisitiones Arithmeticae & Other Papers on Number Theory) , переведенные на немецкий язык Мазером Х. (2-е изд.), Нью-Йорк: Челси, ISBN  0-8284-0191-8
• Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Монографии Спрингера по математике, Берлин: Springer , doi : 10.1007/978-3-662-12893-0 , ISBN  978-3-642-08628-1

Внешние ссылки

• Вайсштейн, Эрик В. , «Циклотомический полином» , MathWorld
• «Циклотомические полиномы» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Последовательность OEIS A013595 (Треугольник коэффициентов кругового полинома Phi_n(x) (показатели степени в порядке возрастания))
• Последовательность OEIS A013594 (наименьший порядок кругового многочлена, содержащий n или -n в качестве коэффициента)