Циклотомический многочлен

редактировать

Неприводимый многочлен, корни которого являются корнями n-й степени из единицы

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

Φ n (x) = ∏ gcd (k, n) = 1 1 ≤ k ≤ n (x - e 2 i π k n). {\ displaystyle \ Phi _ {n} (x) = \ prod _ {\ stackrel {1 \ leq k \ leq n} {\ gcd (k, n) = 1}} \ left (xe ^ {2i \ pi { \ frac {k} {n}}} \ right).}

\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 2 i π / n {\ displaystyle e ^ {2i \ pi / n}}$ $e^{2i\pi /n}$ - пример такого корня).

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

∏ d ∣ n Φ d (x) = xn - 1, {\ displaystyle \ prod _ {d \ mid n} \ Phi _ {d} (x) = x ^ {n} -1,}

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

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

Содержание

1 Примеры
2 Свойства
- 2.1 Основные инструменты
- 2.2 Простые варианты вычислений
- 2.3 Целые числа в виде коэффициентов
- 2.4 Формула Гаусса
- 2.5 Формула Люка
3 Циклотомические полиномы над конечным полем и целыми p-адическими числами
4 Полиномиальные значения
5 Приложения
6 См. Также
7 Примечания
8 Ссылки
9 Внешние ссылки

Примеры

Если n является простым числом, то

Φ n (x) = 1 + x + x 2 + ⋯ + xn - 1 = ∑ k = 0 n - 1 хк. {\ displaystyle \ Phi _ {n} (x) = 1 + x + x ^ {2} + \ cdots + x ^ {n-1} = \ sum _ {k = 0} ^ {n-1} x ^ {k}.}

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

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

Φ 2 p (x) = 1 - x + x 2 - ⋯ + xp - 1 = ∑ К знак равно 0 п - 1 (- х) к. {\ displaystyle \ Phi _ {2p} (x) = 1-x + x ^ {2} - \ cdots + x ^ {p-1} = \ sum _ {k = 0} ^ {p-1} (- x) ^ {k}.}

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

Для n до 30 круговые многочлены:

Φ 1 (x) = x - 1 Φ 2 (x) = x + 1 Φ 3 (x) = x 2 + x + 1 Φ 4 (x) = x 2 + 1 Φ 5 (x) = x 4 + x 3 + x 2 + x + 1 Φ 6 (x) = x 2 - x + 1 Φ 7 (x) = x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 Φ 8 (x) = x 4 + 1 Φ 9 (x) = x 6 + x 3 + 1 Φ 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 Φ 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 Φ 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 Φ 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 Φ 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 Φ 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 Φ 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 Φ 24 (x) = x 8 - x 4 + 1 Φ 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 Φ 27 (x) = x 18 + x 9 + 1 Φ 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 + Икс + 1 Φ 30 (Икс) = Икс 8 + Икс 7 - Икс 5 - Икс 4 - Икс 3 + Икс + 1. {\ Displaystyle {\ begin {Выровненный} \ 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 {align}}}

{\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:

Φ 105 ( х) = х 48 + х 47 + х 46 - х 43 - х 42-2 х 41 - х 40 - х 39 + х 36 + х 35 + х 34 + х 33 + х 32 + х 31 - х 28 - х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 {\ begin {align} \ 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} \\ \ qquad \ quad -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 {align}}}

{\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}\\\qquad \quad -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, они являются палиндромами четной степени.

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

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

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

xn - 1 = ∏ 1 ⩽ k ⩽ n (x - e 2 i π kn) = ∏ d ∣ n ∏ 1 ⩽ k ⩽ n НОД (k, n) = d (x - e 2 i π kn) = ∏ d ∣ n Φ nd (x) = ∏ d ∣ n Φ d (x). {\ displaystyle {\ begin {align} x ^ {n} -1 = \ prod _ {1 \ leqslant k \ leqslant n} \ left (xe ^ {2i \ pi {\ frac {k} {n}}} \ справа) \\ = \ prod _ {d \ mid n} \ prod _ {1 \ leqslant k \ leqslant n \ atop \ gcd (k, n) = d} \ left (xe ^ {2i \ pi {\ frac {k} {n}}} \ right) \\ = \ prod _ {d \ mid n} \ Phi _ {\ frac {n} {d}} (x) = \ prod _ {d \ mid n} \ Phi _ {d} (x). \ End {align}}}

{\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-й степени из единицы для уникального деления n.

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

Φ N (x) знак равно ∏ d ∣ n (xd - 1) μ (nd), {\ displaystyle \ Phi _ {n} (x) = \ prod _ {d \ mid n} (x ^ {d} -1) ^ {\ mu \ left ({\ frac {n} {d}} \ right)},}

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

где $μ {\ displaystyle \ mu}$ $\mu$ является функцией Мёбиуса.

Преобразование Фурье функций от наибольшего общего делителя вместе с формулой обращения Мёбиуса дает:

Φ n (x) = ∏ k = 1 n (x gcd (k, n) - 1) cos ⁡ (2 π kn). {\ Displaystyle \ Phi _ {n} (x) = \ prod _ {k = 1} ^ {n} \ left (x ^ {\ gcd (k, n)} - 1 \ right) ^ {\ cos \ left ({\ гидроразрыва {2 \ pi k} {n}} \ right)}.}

\Phi _{n}(x)=\prod _{k=1}^{n}\left(x^{\gcd(k,n)}-1\right)^{\cos \left({\frac {2\pi k}{n}}\right)}.

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

Φ n (x) = xn - 1 ∏ d < n d | n Φ d ( x) {\displaystyle \Phi _{n}(x)={\frac {x^{n}-1}{\prod _{\stackrel {d|n}{{}_{d

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

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

Эта формула позволяет вычислить $Φ n (x) {\ displaystyle \ Phi _ {n} (x)}$ $\Phi _{n}(x)$ на компьютере для любого n, как только доступны целочисленная факторизация и деление многочленов. Многие системы компьютерной алгебры имеют встроенную функцию для вычисления циклотомических полиномов. Например, эта функция вызывается путем ввода cyclotomic_polynomial (n, x)в SageMath, numtheory [cyclotomic] (n, x);в Maple, Cyclotomic [n, x]в Mathematica и polcyclo (n, x)в PARI / GP.

Easy случаи для вычисления

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

Φ n (x) = 1 + x + x 2 + ⋯ + xn - 1 = ∑ i = 0 n - 1 xi. {\ displaystyle \ Phi _ {n} (x) = 1 + x + x ^ {2} + \ cdots + x ^ {n-1} = \ sum _ {i = 0} ^ {n-1} x ^ {i}.}

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

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

Φ 2 n (x) = Φ n (- x). {\ displaystyle \ Phi _ {2n} (x) = \ Phi _ {n} (- x).}

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

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

Ф п (х) знак равно 1 - х + х 2 - ⋯ + хр - 1 знак равно ∑ я = 0 р - 1 (- х) я. {\ displaystyle \ Phi _ {n} (x) = 1-x + x ^ {2} - \ cdots + x ^ {p-1} = \ sum _ {i = 0} ^ {p-1} (- x) ^ {i}.}

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

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

Φ n (x) = Φ p (xpm - 1) = ∑ я знак равно 0 п - 1 xipm - 1. {\ Displaystyle \ Phi _ {n} (x) = \ Phi _ {p} (x ^ {p ^ {m-1}}) = \ sum _ {i = 0} ^ {p-1} x ^ { ip ^ {m-1}}.}

\Phi _{n}(x)=\Phi _{p}(x^{p^{m-1}})=\sum _{i=0}^{p-1}x^{ip^{m-1}}.

В более общем случае, если n = pr с r, взаимно простым с p, то

Φ n (x) = Φ pr (xpm - 1). {\ displaystyle \ Phi _ {n} (x) = \ Phi _ {pr} (x ^ {p ^ {m-1}}).}

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

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

Φ n (x) = Φ q (xn / q). {\ displaystyle \ Phi _ {n} (x) = \ Phi _ {q} (x ^ {n / q}).}

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

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

Φ 2 h (x) = x 2 h - 1 + 1 {\ displaystyle \ Phi _ {2 ^ {h} } (х) = х ^ {2 ^ {ч-1}} + 1}

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

Φ pk (x) = ∑ i = 0 p - 1 xipk - 1 {\ displaystyle \ Phi _ {p ^ {k} } (x) = \ sum _ {i = 0} ^ {p-1} x ^ {ip ^ {k-1}}}

\Phi _{p^{k}}(x)=\sum _{i=0}^{p-1}x^{ip^{k-1}}

Φ 2 hpk (x) = ∑ i = 0 p - 1 (- 1) ixi 2 час - 1 pk - 1 {\ displaystyle \ Phi _ {2 ^ {h} p ^ {k}} (x) = \ sum _ {i = 0} ^ {p-1} (- 1) ^ {i} x ^ {i2 ^ {h-1} p ^ {k-1}}}

\Phi _{2^{h}p^{k}}(x)=\sum _{i=0}^{p-1}(-1)^{i}x^{i2^{h-1}p^{k-1}}

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

Φ n p (x) = Φ n (x p) / Φ n (x). {\ displaystyle \ Phi _ {np} (x) = \ Phi _ {n} (x ^ {p}) / \ Phi _ {n} (x).}

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

Целые числа в виде коэффициентов

Проблема ограничения величины коэффициентов круговых многочленов была объектом ряда исследовательских работ.

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

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

Если n является произведением нескольких различных нечетных простых множителей, коэффициенты могут увеличиваться до очень высоких значений. Например, $Φ 15015 (x) = Φ 3 × 5 × 7 × 11 × 13 (x) {\ displaystyle \ Phi _ {15015} (x) = \ Phi _ {3 \ times 5 \ times 7 \ times 11 \ times 13} (x)}$ $\Phi _{15015}(x)=\Phi _{3\times 5\times 7\times 11\times 13}(x)$ имеет коэффициенты от −22 до 23, $Φ 255255 (x) = Φ 3 × 5 × 7 × 11 × 13 × 17 (x) {\ displaystyle \ Phi _ {255255} (x) = \ Phi _ {3 \ times 5 \ times 7 \ times 11 \ times 13 \ times 17} (x)}$ $\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.

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

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

4 Φ n (z) = A n 2 (z) - (- 1) n - 1 2 nz 2 B n 2 (z) {\ displaystyle 4 \ Phi _ {n} (z) = A_ {n} ^ {2} (z) - (- 1) ^ {\ frac {n-1} {2}} nz ^ {2} B_ {n} ^ {2} (z)}

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), и в этом случае он антипалиндромный.

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

4 Φ 5 (z) = 4 (z 4 + z 3 + z 2 + z + 1) = (2 z 2 + z + 2) 2 - 5 z 2 4 Φ 7 (z) = 4 (z 6 + z 5 + z 4 + z 3 + z 2 + z + 1) = (2 z 3 + z 2 - z - 2) 2 + 7 z 2 (z + 1) 2 4 Φ 11 (z) = 4 (z 10 + z 9 + z 8 + z 7 + z 6 + z 5 + z 4 + z 3 + z 2 + z + 1) = (2 z 5 + z 4 - 2 z 3 + 2 z 2 - z - 2) 2 + 11 z 2 (z 3 + 1) 2 {\ displaystyle {\ begin {align} 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 {align}}}

{\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. Тогда

Φ n (z) = U n 2 (z) - (- 1) n - 1 2 nz V n 2 (z) {\ displaystyle \ Phi _ {n} ( z) = U_ {n} ^ {2} (z) - (- 1) ^ {\ frac {n-1} {2}} nzV_ {n} ^ {2} (z)}

\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. Это также можно записать

Φ n ((- 1) n - 1 2 z) = C n 2 (z) - nz D n 2 (z). {\ displaystyle \ Phi _ {n} \ left ((- 1) ^ {\ frac {n-1} {2}} z \ right) = C_ {n} ^ {2} (z) -nzD_ {n} ^ {2} (z).}

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

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

Φ n 2 (- z 2) = Φ 2 n (Z) знак равно С N 2 (Z) - nz D N 2 (z) {\ Displaystyle \ Phi _ {\ frac {n} {2}} \ left (-z ^ {2} \ right) = \ Phi _ {2n} (z) = C_ {n} ^ {2} (z) -nzD_ {n} ^ {2} (z)}

\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) являются палиндромными.

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

Φ 3 (- z) = Φ 6 (z) = z 2 - z + 1 = (z + 1) 2 - 3 z Φ 5 (z) = z 4 + z 3 + z 2 + z + 1 = (z 2 + 3 z + 1) 2-5 z (z + 1) 2 Φ 6/2 (- z 2) = Φ 12 (z) = z 4 - z 2 + 1 знак равно (z 2 + 3 z + 1) 2-6 z (z + 1) 2 {\ displaystyle {\ begin {align} \ 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 {align}}}

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

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

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

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

Значения полиномов

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

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

Для n ≥ 2 имеем

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

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

Φ n (1) = 1 { \ displaystyle \ Phi _ {n} (1) = 1}

\Phi _{n}(1)=1

, если n не является степенью простого числа,

Φ n (1) = p {\ displaystyle \ Phi _ {n} ( 1) = p}

\Phi _{n}(1)=p

, если

n = pk {\ displaystyle n = p ^ { k}}

n=p^{k}

- степень простого числа с k ≥ 1.

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

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

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

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

Φ n (b) = 2 кгч, {\ displaystyle \ Phi _ {n } (b) = 2 ^ {k} gh,}

\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 является мультипликативным порядком of b по модулю p.

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

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

Φ 1 (2) = 1 Φ 2 (2 к - 1) = 2 кк>0 Φ 6 (2) = 3 {\ displaystyle {\ begin {align} \ Phi _ {1} (2) = 1 \\\ Phi _ {2} \ left (2 ^ {k} -1 \ right) = 2 ^ {k} k>0 \\\ Phi _ {6} (2) = 3 \ end {align}}}

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

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

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

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

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

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

Доказательства
Значения $Φ n (1). {\ displaystyle \ Phi _ {n} (1).}$ $\Phi _{n}(1).$ Если $n = pk + 1 {\ displaystyle n = p ^ {k + 1}}$ $n=p^{k+1}$ - это степень простого числа, тогда $Φ n (x) = 1 + xpk + x 2 pk + ⋯ + x (p - 1) pk и Φ n (1) = p. {\ displaystyle \ Phi _ {n} (x) = 1 + x ^ {p ^ {k}} + x ^ {2p ^ {k}} + \ cdots + x ^ {(p-1) p ^ {k }} \ qquad {\ text {and}} \ qquad \ Phi _ {n} (1) = p.}$ $\Phi _{n}(x)=1+x^{p^{k}}+x^{2p^{k}}+\cdots +x^{(p-1)p^{k}}\qquad {\text{and}}\qquad \Phi _{n}(1)=p.$ Если n не является степенью простого числа, пусть $P (x) = 1 + x + ⋯ + xn - 1, {\ displaystyle P (x) = 1 + x + \ cdots + x ^ {n-1},}$ $P(x)=1+x+\cdots +x^{n-1},$ мы имеем $P (1) = n, {\ displaystyle P (1) = n,}$ $P(1)=n,$ и P является произведением $Φ k (x) {\ displaystyle \ Phi _ {k} (x)}$ $\Phi _{k}(x)$ для k делит n и отличается от 1. Если p является простым делителем, кратным m от n, то $Φ p (x), Φ p 2 (x), ⋯, Φ pm (x) {\ displaystyle \ Phi _ { p} (x), \ Phi _ {p ^ {2}} (x), \ cdots, \ Phi _ {p ^ {m}} (x)}$ $\Phi _{p}(x),\Phi _{p^{2}}(x),\cdots,\Phi _{p^{m}}(x)$ делят P (x), и их значения при 1 - это m факторов, равных p из $n = P (1). {\ displaystyle n = P (1).}$ $n=P(1).$ Поскольку m - это кратность p в n, p не может делить значение на 1 из других факторов $P (x). {\ displaystyle P (x).}$ $P(x).$ Таким образом, нет простого числа, делящего $Φ n (1). {\ displaystyle \ Phi _ {n} (1).}$ $\Phi _{n}(1).$ Если n - порядок умножения b по модулю p, то $p ∣ Φ n (b). {\ displaystyle p \ mid \ Phi _ {n} (b).}$ $p\mid \Phi _{n}(b).$ По определению, $p ∣ bn - 1. {\ displaystyle p \ mid b ^ {n} -1.}$ $p\mid b^{n}-1.$ Если $p ∤ Φ n (b), {\ displaystyle p \ nmid \ Phi _ {n} (b),}$ $p\nmid \Phi _{n}(b),$ , то p разделит другой множитель $Φ к (b) {\ displaystyle \ Phi _ {k} (b)}$ $\Phi _{k}(b)$ из $bn - 1, {\ displaystyle b ^ {n} -1,}$ $b^{n}-1,$ и, таким образом, разделит $bk - 1, {\ displaystyle b ^ {k} -1,}$ $b^{k}-1,$ показывая, что, если бы это было так, n не было бы порядком умножения b по модулю p. Другие простые делители числа $Φ n (b) {\ displaystyle \ Phi _ {n} (b)}$ $\Phi _{n}(b)$ являются делителями n. Пусть p - простой делитель числа $Φ n (b) {\ displaystyle \ Phi _ {n} (b)}$ $\Phi _{n}(b)$ такой, что n не является порядком умножения b по модулю p. Если k - порядок умножения b по модулю p, то p делит как $Φ n (b) {\ displaystyle \ Phi _ {n} (b)}$ $\Phi _{n}(b)$ , так и $Φ k (b). {\ displaystyle \ Phi _ {k} (b).}$ $\Phi _{k}(b).$ , результат из $Φ n (x) {\ displaystyle \ Phi _ {n} (x)}$ $\Phi _{n}(x)$ и $Φ k (x) {\ displaystyle \ Phi _ {k} (x)}$ $\Phi _{k}(x)$ можно записать как $P Φ k + Q Φ n, {\ displaystyle P \ Phi _ {k} + Q \ Phi _ {n},}$ $P\Phi _{k}+Q\Phi _{n},$ где P и Q - многочлены. Таким образом, p делит результат. Поскольку k делит n, а результат двух многочленов делит дискриминант любого общего кратного этих многочленов, p делит также дискриминант $nn {\ displaystyle n ^ {n}}$ $n^n$ из $xn - 1. {\ displaystyle x ^ {n} -1.}$ $x^{n}-1.$ Таким образом, p делит n. g и h взаимно просты. Другими словами, если p является простым общим делителем n и $Φ n (b), {\ displaystyle \ Phi _ {n} (b),}$ $\Phi _{n}(b),$ , то n не является мультипликативным порядком из b по модулю p. Согласно маленькой теореме Ферма, мультипликативный порядок числа b является делителем p - 1 и, следовательно, меньше n. g не содержит квадратов. Другими словами, если p является простым общим делителем n и $Φ n (b), {\ displaystyle \ Phi _ {n} (b),}$ $\Phi _{n}(b),$ , то $p 2 { \ displaystyle p ^ {2}}$ $p^{2}$ не делит $Φ n (b). {\ displaystyle \ Phi _ {n} (b).}$ $\Phi _{n}(b).$ Пусть n = pm. Достаточно доказать, что $p 2 {\ displaystyle p ^ {2}}$ $p^{2}$ не делит S (b) для некоторого многочлена S (x), который кратен $Φ n ( Икс). {\ displaystyle \ Phi _ {n} (x).}$ $\Phi _{n}(x).$ Возьмем $S (x) = xn - 1 xm - 1 = 1 + xm + x 2 m + ⋯ + x (p - 1) м. {\ Displaystyle S (x) = {\ frac {x ^ {n} -1} {x ^ {m} -1}} = 1 + x ^ {m} + x ^ {2m} + \ cdots + x ^ {(p-1) m}.}$ $S(x)={\frac {x^{n}-1}{x^{m}-1}}=1+x^{m}+x^{2m}+\cdots +x^{(p-1)m}.$ Мультипликативный порядок b по модулю p делит gcd (n, p - 1), который является делителем m = n / p. Таким образом, c = b - 1 делится на p. Теперь $S (b) = (1 + c) p - 1 c = p + (p 2) c + ⋯ + (p p) c p - 1. {\ displaystyle S (b) = {\ frac {(1 + c) ^ {p} -1} {c}} = p + {\ binom {p} {2}} c + \ cdots + {\ binom {p} {p}} c ^ {p-1}.}$ $S(b)={\frac {(1+c)^{p}-1}{c}}=p+{\binom {p}{2}}c+\cdots +{\binom {p}{p}}c^{p-1}.$ Поскольку p простое число и больше 2, все члены, кроме первого, кратны $p 2. {\ displaystyle p ^ {2}.}$ $p^{2}.$ Это доказывает, что $p 2 ∤ Φ n (b). {\ displaystyle p ^ {2} \ nmid \ Phi _ {n} (b).}$ $p^{2}\nmid \Phi _{n}(b).$

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

Значения $Φ n (1). {\ displaystyle \ Phi _ {n} (1).}$ $\Phi _{n}(1).$ Если $n = pk + 1 {\ displaystyle n = p ^ {k + 1}}$ $n=p^{k+1}$ - это степень простого числа, тогда

Φ n (x) = 1 + xpk + x 2 pk + ⋯ + x (p - 1) pk и Φ n (1) = p. {\ displaystyle \ Phi _ {n} (x) = 1 + x ^ {p ^ {k}} + x ^ {2p ^ {k}} + \ cdots + x ^ {(p-1) p ^ {k }} \ qquad {\ text {and}} \ qquad \ Phi _ {n} (1) = p.}

\Phi _{n}(x)=1+x^{p^{k}}+x^{2p^{k}}+\cdots +x^{(p-1)p^{k}}\qquad {\text{and}}\qquad \Phi _{n}(1)=p.

Если n не является степенью простого числа, пусть

P (x) = 1 + x + ⋯ + xn - 1, {\ displaystyle P (x) = 1 + x + \ cdots + x ^ {n-1},}

P(x)=1+x+\cdots +x^{n-1},

мы имеем

P (1) = n, {\ displaystyle P (1) = n,}

P(1)=n,

и P является произведением

Φ k (x) {\ displaystyle \ Phi _ {k} (x)}

\Phi _{k}(x)

для k делит n и отличается от 1. Если p является простым делителем, кратным m от n, то

Φ p (x), Φ p 2 (x), ⋯, Φ pm (x) {\ displaystyle \ Phi _ { p} (x), \ Phi _ {p ^ {2}} (x), \ cdots, \ Phi _ {p ^ {m}} (x)}

\Phi _{p}(x),\Phi _{p^{2}}(x),\cdots,\Phi _{p^{m}}(x)

делят P (x), и их значения при 1 - это m факторов, равных p из

n = P (1). {\ displaystyle n = P (1).}

n=P(1).

Поскольку m - это кратность p в n, p не может делить значение на 1 из других факторов

P (x). {\ displaystyle P (x).}

P(x).

Таким образом, нет простого числа, делящего

Φ n (1). {\ displaystyle \ Phi _ {n} (1).}

\Phi _{n}(1).

Если n - порядок умножения b по модулю p, то $p ∣ Φ n (b). {\ displaystyle p \ mid \ Phi _ {n} (b).}$ $p\mid \Phi _{n}(b).$ По определению, $p ∣ bn - 1. {\ displaystyle p \ mid b ^ {n} -1.}$ $p\mid b^{n}-1.$ Если $p ∤ Φ n (b), {\ displaystyle p \ nmid \ Phi _ {n} (b),}$ $p\nmid \Phi _{n}(b),$ , то p разделит другой множитель $Φ к (b) {\ displaystyle \ Phi _ {k} (b)}$ $\Phi _{k}(b)$ из $bn - 1, {\ displaystyle b ^ {n} -1,}$ $b^{n}-1,$ и, таким образом, разделит $bk - 1, {\ displaystyle b ^ {k} -1,}$ $b^{k}-1,$ показывая, что, если бы это было так, n не было бы порядком умножения b по модулю p.

Другие простые делители числа $Φ n (b) {\ displaystyle \ Phi _ {n} (b)}$ $\Phi _{n}(b)$ являются делителями n. Пусть p - простой делитель числа $Φ n (b) {\ displaystyle \ Phi _ {n} (b)}$ $\Phi _{n}(b)$ такой, что n не является порядком умножения b по модулю p. Если k - порядок умножения b по модулю p, то p делит как $Φ n (b) {\ displaystyle \ Phi _ {n} (b)}$ $\Phi _{n}(b)$ , так и $Φ k (b). {\ displaystyle \ Phi _ {k} (b).}$ $\Phi _{k}(b).$ , результат из $Φ n (x) {\ displaystyle \ Phi _ {n} (x)}$ $\Phi _{n}(x)$ и $Φ k (x) {\ displaystyle \ Phi _ {k} (x)}$ $\Phi _{k}(x)$ можно записать как $P Φ k + Q Φ n, {\ displaystyle P \ Phi _ {k} + Q \ Phi _ {n},}$ $P\Phi _{k}+Q\Phi _{n},$ где P и Q - многочлены. Таким образом, p делит результат. Поскольку k делит n, а результат двух многочленов делит дискриминант любого общего кратного этих многочленов, p делит также дискриминант $nn {\ displaystyle n ^ {n}}$ $n^n$ из $xn - 1. {\ displaystyle x ^ {n} -1.}$ $x^{n}-1.$ Таким образом, p делит n.

g и h взаимно просты. Другими словами, если p является простым общим делителем n и $Φ n (b), {\ displaystyle \ Phi _ {n} (b),}$ $\Phi _{n}(b),$ , то n не является мультипликативным порядком из b по модулю p. Согласно маленькой теореме Ферма, мультипликативный порядок числа b является делителем p - 1 и, следовательно, меньше n.

g не содержит квадратов. Другими словами, если p является простым общим делителем n и $Φ n (b), {\ displaystyle \ Phi _ {n} (b),}$ $\Phi _{n}(b),$ , то $p 2 { \ displaystyle p ^ {2}}$ $p^{2}$ не делит $Φ n (b). {\ displaystyle \ Phi _ {n} (b).}$ $\Phi _{n}(b).$ Пусть n = pm. Достаточно доказать, что $p 2 {\ displaystyle p ^ {2}}$ $p^{2}$ не делит S (b) для некоторого многочлена S (x), который кратен $Φ n ( Икс). {\ displaystyle \ Phi _ {n} (x).}$ $\Phi _{n}(x).$ Возьмем

S (x) = xn - 1 xm - 1 = 1 + xm + x 2 m + ⋯ + x (p - 1) м. {\ Displaystyle S (x) = {\ frac {x ^ {n} -1} {x ^ {m} -1}} = 1 + x ^ {m} + x ^ {2m} + \ cdots + x ^ {(p-1) m}.}

S(x)={\frac {x^{n}-1}{x^{m}-1}}=1+x^{m}+x^{2m}+\cdots +x^{(p-1)m}.

Мультипликативный порядок b по модулю p делит gcd (n, p - 1), который является делителем m = n / p. Таким образом, c = b - 1 делится на p. Теперь

S (b) = (1 + c) p - 1 c = p + (p 2) c + ⋯ + (p p) c p - 1. {\ displaystyle S (b) = {\ frac {(1 + c) ^ {p} -1} {c}} = p + {\ binom {p} {2}} c + \ cdots + {\ binom {p} {p}} c ^ {p-1}.}

S(b)={\frac {(1+c)^{p}-1}{c}}=p+{\binom {p}{2}}c+\cdots +{\binom {p}{p}}c^{p-1}.

Поскольку p простое число и больше 2, все члены, кроме первого, кратны

p 2. {\ displaystyle p ^ {2}.}

p^{2}.

Это доказывает, что

p 2 ∤ Φ n (b). {\ displaystyle p ^ {2} \ nmid \ Phi _ {n} (b).}

p^{2}\nmid \Phi _{n}(b).

Приложения

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

Доказательство
Предположим, что $p 1, p 2,…, pk {\ displaystyle p_ {1}, p_ {2}, \ ldots, p_ {k}}$ $p_{1},p_{2},\ldots,p_{k}$ - конечный список простых чисел конгруэнтно $1 {\ displaystyle 1}$ $1$ по модулю $n. {\ displaystyle n.}$ $n.$ Пусть $N = np 1 p 2 ⋯ pk {\ displaystyle N = np_ {1} p_ {2} \ cdots p_ {k}}$ $N=np_{1}p_{2}\cdots p_{k}$ и рассмотрим $Φ n (N) {\ displaystyle \ Phi _ {n} (N)}$ $\Phi _{n}(N)$ . Пусть $q {\ displaystyle q}$ $q$ будет простым множителем $Φ n (N) {\ displaystyle \ Phi _ {n} (N)}$ $\Phi _{n}(N)$ (to посмотрите, что $Φ n (N) ≠ ± 1 {\ displaystyle \ Phi _ {n} (N) \ neq \ pm 1}$ $\Phi _{n}(N)\neq \pm 1$ разложите его на линейные множители и обратите внимание, что 1 - ближайший корень единицы до $N {\ displaystyle N}$ $N$ ). Поскольку $Φ n (x) ≡ ± 1 (mod x), {\ displaystyle \ Phi _ {n} (x) \ Equiv \ pm 1 {\ pmod {x}},}$ $\Phi _{n}(x)\equiv \pm 1{\pmod {x}},$ мы знайте, что $q {\ displaystyle q}$ $q$ - это новое простое число, которого нет в списке. Покажем, что $q ≡ 1 (mod n). {\ displaystyle q \ Equiv 1 {\ pmod {n}}.}$ $q\equiv 1{\pmod {n}}.$ Пусть $m {\ displaystyle m}$ $m$ будет порядком $N {\ displaystyle N}$ $N$ по модулю $q. {\ displaystyle q.}$ $q.$ Так как $Φ n (N) ∣ N n - 1 {\ displaystyle \ Phi _ {n} (N) \ mid N ^ {n} -1}$ $\Phi _{n}(N)\mid N^{n}-1$ у нас есть $N n - 1 ≡ 0 (mod q) {\ displaystyle N ^ {n} -1 \ Equiv 0 {\ pmod {q}}}$ $N^{n}-1\equiv 0{\pmod {q}}$ . Таким образом, $m ∣ n {\ displaystyle m \ mid n}$ $m\mid n$ . Мы покажем, что $m = n {\ displaystyle m = n}$ $m=n$ . Предположим для противоречия, что $m < n {\displaystyle m$ $m<n$ . Поскольку $∏ d ∣ м Φ d (N) = N m - 1 ≡ 0 (mod q) {\ displaystyle \ prod _ {d \ mid m} \ Phi _ {d} (N) = N ^ {m } -1 \ Equiv 0 {\ pmod {q}}}$ $\prod _{d\mid m}\Phi _{d}(N)=N^{m}-1\equiv 0{\pmod {q}}$ мы имеем $Φ d (N) ≡ 0 (mod q), {\ displaystyle \ Phi _ {d} (N) \ Equiv 0 { \ pmod {q}},}$ $\Phi _{d}(N)\equiv 0{\pmod {q}},$ для некоторых $d < n {\displaystyle d$ $d<n$ . Тогда $N {\ displaystyle N}$ $N$ является двойным корнем из $∏ d ∣ n Φ d (x) ≡ x n - 1 (mod q). {\ displaystyle \ prod _ {d \ mid n} \ Phi _ {d} (x) \ Equiv x ^ {n} -1 {\ pmod {q}}.}$ $\prod _{d\mid n}\Phi _{d}(x)\equiv x^{n}-1{\pmod {q}}.$ Таким образом, $N {\ displaystyle N}$ $N$ должен быть корнем производной, поэтому $d (xn - 1) dx \| N ≡ n N n - 1 ≡ 0 (mod q). {\ displaystyle \ left. {\ frac {d (x ^ {n} -1)} {dx}} \ right \| _ {N} \ Equiv nN ^ {n-1} \ Equiv 0 {\ pmod {q} }.}$ $\left.{\frac {d(x^{n}-1)}{dx}}\right\|_{N}\equiv nN^{n-1}\equiv 0{\pmod {q}}.$ Но $q ∤ N {\ displaystyle q \ nmid N}$ $q\nmid N$ и, следовательно, $q ∤ n. {\ displaystyle q \ nmid n.}$ $q\nmid n.$ Это противоречие, поэтому $m = n {\ displaystyle m = n}$ $m=n$ . Порядок $N (mod q), {\ displaystyle N {\ pmod {q}},}$ $N{\pmod {q}},$ , который равен $n {\ displaystyle n}$ $n$ , должен разделить $q - 1 {\ displaystyle q-1}$ $q-1$ . Таким образом, $q ≡ 1 (mod n). {\ displaystyle q \ Equiv 1 {\ pmod {n}}.}$ $q\equiv 1{\pmod {n}}.$

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

Предположим, что $p 1, p 2,…, pk {\ displaystyle p_ {1}, p_ {2}, \ ldots, p_ {k}}$ $p_{1},p_{2},\ldots,p_{k}$ - конечный список простых чисел конгруэнтно $1 {\ displaystyle 1}$ $1$ по модулю $n. {\ displaystyle n.}$ $n.$ Пусть $N = np 1 p 2 ⋯ pk {\ displaystyle N = np_ {1} p_ {2} \ cdots p_ {k}}$ $N=np_{1}p_{2}\cdots p_{k}$ и рассмотрим $Φ n (N) {\ displaystyle \ Phi _ {n} (N)}$ $\Phi _{n}(N)$ . Пусть $q {\ displaystyle q}$ $q$ будет простым множителем $Φ n (N) {\ displaystyle \ Phi _ {n} (N)}$ $\Phi _{n}(N)$ (to посмотрите, что $Φ n (N) ≠ ± 1 {\ displaystyle \ Phi _ {n} (N) \ neq \ pm 1}$ $\Phi _{n}(N)\neq \pm 1$ разложите его на линейные множители и обратите внимание, что 1 - ближайший корень единицы до $N {\ displaystyle N}$ $N$ ). Поскольку $Φ n (x) ≡ ± 1 (mod x), {\ displaystyle \ Phi _ {n} (x) \ Equiv \ pm 1 {\ pmod {x}},}$ $\Phi _{n}(x)\equiv \pm 1{\pmod {x}},$ мы знайте, что $q {\ displaystyle q}$ $q$ - это новое простое число, которого нет в списке. Покажем, что $q ≡ 1 (mod n). {\ displaystyle q \ Equiv 1 {\ pmod {n}}.}$ $q\equiv 1{\pmod {n}}.$

Пусть $m {\ displaystyle m}$ $m$ будет порядком $N {\ displaystyle N}$ $N$ по модулю $q. {\ displaystyle q.}$ $q.$ Так как $Φ n (N) ∣ N n - 1 {\ displaystyle \ Phi _ {n} (N) \ mid N ^ {n} -1}$ $\Phi _{n}(N)\mid N^{n}-1$ у нас есть $N n - 1 ≡ 0 (mod q) {\ displaystyle N ^ {n} -1 \ Equiv 0 {\ pmod {q}}}$ $N^{n}-1\equiv 0{\pmod {q}}$ . Таким образом, $m ∣ n {\ displaystyle m \ mid n}$ $m\mid n$ . Мы покажем, что $m = n {\ displaystyle m = n}$ $m=n$ .

Предположим для противоречия, что $m < n {\displaystyle m$ $m<n$ . Поскольку

∏ d ∣ м Φ d (N) = N m - 1 ≡ 0 (mod q) {\ displaystyle \ prod _ {d \ mid m} \ Phi _ {d} (N) = N ^ {m } -1 \ Equiv 0 {\ pmod {q}}}

\prod _{d\mid m}\Phi _{d}(N)=N^{m}-1\equiv 0{\pmod {q}}

мы имеем

Φ d (N) ≡ 0 (mod q), {\ displaystyle \ Phi _ {d} (N) \ Equiv 0 { \ pmod {q}},}

\Phi _{d}(N)\equiv 0{\pmod {q}},

для некоторых $d < n {\displaystyle d$ $d<n$ . Тогда $N {\ displaystyle N}$ $N$ является двойным корнем из

∏ d ∣ n Φ d (x) ≡ x n - 1 (mod q). {\ displaystyle \ prod _ {d \ mid n} \ Phi _ {d} (x) \ Equiv x ^ {n} -1 {\ pmod {q}}.}

\prod _{d\mid n}\Phi _{d}(x)\equiv x^{n}-1{\pmod {q}}.

Таким образом, $N {\ displaystyle N}$ $N$ должен быть корнем производной, поэтому

d (xn - 1) dx | N ≡ n N n - 1 ≡ 0 (mod q). {\ displaystyle \ left. {\ frac {d (x ^ {n} -1)} {dx}} \ right | _ {N} \ Equiv nN ^ {n-1} \ Equiv 0 {\ pmod {q} }.}

\left.{\frac {d(x^{n}-1)}{dx}}\right|_{N}\equiv nN^{n-1}\equiv 0{\pmod {q}}.

Но $q ∤ N {\ displaystyle q \ nmid N}$ $q\nmid N$ и, следовательно, $q ∤ n. {\ displaystyle q \ nmid n.}$ $q\nmid n.$ Это противоречие, поэтому $m = n {\ displaystyle m = n}$ $m=n$ . Порядок $N (mod q), {\ displaystyle N {\ pmod {q}},}$ $N{\pmod {q}},$ , который равен $n {\ displaystyle n}$ $n$ , должен разделить $q - 1 {\ displaystyle q-1}$ $q-1$ . Таким образом, $q ≡ 1 (mod n). {\ displaystyle q \ Equiv 1 {\ pmod {n}}.}$ $q\equiv 1{\pmod {n}}.$

См. также

Примечания

Ссылки

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

Гаусс, Карл Фридрих (1986) [1801]. Disquisitiones Arithmeticae. Переведено на английский Кларком, Артуром А. (2-е изд. Корр.). Нью-Йорк: Спрингер. ISBN 0387962549.
Gauss, Carl Friedrich (1965) [1801]. Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae other papers on number theory). Translated into German by Maser, H. (2nd ed.). New York: Chelsea. ISBN 0-8284-0191-8.
Lemmermeyer, Franz (2000). Reciprocity Laws: from Euler to Eisenstein. Berlin: Springer. doi :10.1007/978-3-662-12893-0. ISBN 978-3-642-08628-1.
Maier, Helmut (2008), "Anatomy of integers and cyclotomic polynomials", in De Koninck, Jean-Marie; Granville, Andrew ; Luca, Florian (eds.), Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13-17, 2006, CRM Proceedings and Lecture Notes, 46, Providence, RI: American Mathematical Society, pp. 89–95, ISBN 978-0-8218-4406-9, Zbl 1186.11010
Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization (2nd ed.). Boston: Birkhäuser. ISBN 0-8176-3743-5.

External links