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

редактировать
Неприводимый многочлен, корни которого являются корнями 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).} {\displaystyle \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}.}{\displaystyle \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}.}{\displaystyle \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}}}{\displaystyle {\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}}}{\displaystyle {\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]}{\displaystyle \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}}}{\displaystyle {\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)},}{\displaystyle \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)}.}{\displaystyle \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).}{\displaystyle \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)}{\displaystyle \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)}{\displaystyle \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)}{\displaystyle \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)}{\displaystyle 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}}}{\displaystyle {\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)}{\displaystyle \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).}{\displaystyle \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)}{\displaystyle \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}}}{\displaystyle {\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}}}{\displaystyle {\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}{\displaystyle \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}{\displaystyle \Phi _{1}(x)=x-1}и Φ 2 (x) = x + 1 {\ displaystyle \ Phi _ {2} (x) = x + 1}{\displaystyle \Phi _{2}(x)=x+1}).

Для n ≥ 2 имеем

Φ n (0) = 1, {\ displaystyle \ Phi _ {n} (0) = 1,}{\displaystyle \Phi _{n}(0)=1,}
Φ n (1) = 1 { \ displaystyle \ Phi _ {n} (1) = 1}{\displaystyle \Phi _{n}(1)=1}, если n не является степенью простого числа,
Φ n (1) = p {\ displaystyle \ Phi _ {n} ( 1) = p}{\displaystyle \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).}{\displaystyle \Phi _{n}(b).}Обратное неверно, но имеет место следующее.

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

Φ n (b) = 2 кгч, {\ displaystyle \ Phi _ {n } (b) = 2 ^ {k} gh,}{\displaystyle \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),}{\displaystyle \Phi _{n}(b),}, то либо n делитель p - 1, либо p делитель n. В последнем случае p 2 {\ displaystyle p ^ {2}}p^{2}не делит Φ n (b). {\ displaystyle \ Phi _ {n} (b).}{\displaystyle \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}}}{\displaystyle {\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))}}}{\displaystyle {\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)}{\displaystyle \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).}{\displaystyle \Phi _{n}(1).}Если n = pk + 1 {\ displaystyle n = p ^ {k + 1}}{\displaystyle 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.}{\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.}
Если n не является степенью простого числа, пусть P (x) = 1 + x + ⋯ + xn - 1, {\ displaystyle P (x) = 1 + x + \ cdots + x ^ {n-1},}{\displaystyle P(x)=1+x+\cdots +x^{n-1},}мы имеем P (1) = n, {\ displaystyle P (1) = n,}{\displaystyle P(1)=n,}и P является произведением Φ k (x) {\ displaystyle \ Phi _ {k} (x)}{\displaystyle \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)}{\displaystyle \Phi _{p}(x),\Phi _{p^{2}}(x),\cdots,\Phi _{p^{m}}(x)}делят P (x), и их значения при 1 - это m факторов, равных p из n = P (1). {\ displaystyle n = P (1).}{\displaystyle n=P(1).}Поскольку m - это кратность p в n, p не может делить значение на 1 из других факторов P (x). {\ displaystyle P (x).}{\displaystyle P(x).}Таким образом, нет простого числа, делящего Φ n (1). {\ displaystyle \ Phi _ {n} (1).}{\displaystyle \Phi _{n}(1).}
  • Если n - порядок умножения b по модулю p, то p ∣ Φ n (b). {\ displaystyle p \ mid \ Phi _ {n} (b).}{\displaystyle p\mid \Phi _{n}(b).}По определению, p ∣ bn - 1. {\ displaystyle p \ mid b ^ {n} -1.}{\displaystyle p\mid b^{n}-1.}Если p ∤ Φ n (b), {\ displaystyle p \ nmid \ Phi _ {n} (b),}{\displaystyle p\nmid \Phi _{n}(b),}, то p разделит другой множитель Φ к (b) {\ displaystyle \ Phi _ {k} (b)}{\displaystyle \Phi _{k}(b)}из bn - 1, {\ displaystyle b ^ {n} -1,}{\displaystyle b^{n}-1,}и, таким образом, разделит bk - 1, {\ displaystyle b ^ {k} -1,}{\displaystyle 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).}{\displaystyle \Phi _{k}(b).}, результат из Φ n (x) {\ displaystyle \ Phi _ {n} (x)}\Phi _{n}(x)и Φ k (x) {\ displaystyle \ Phi _ {k} (x)}{\displaystyle \Phi _{k}(x)}можно записать как P Φ k + Q Φ n, {\ displaystyle P \ Phi _ {k} + Q \ Phi _ {n},}{\displaystyle 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),}{\displaystyle \Phi _{n}(b),}, то n не является мультипликативным порядком из b по модулю p. Согласно маленькой теореме Ферма, мультипликативный порядок числа b является делителем p - 1 и, следовательно, меньше n.
  • g не содержит квадратов. Другими словами, если p является простым общим делителем n и Φ n (b), {\ displaystyle \ Phi _ {n} (b),}{\displaystyle \Phi _{n}(b),}, то p 2 { \ displaystyle p ^ {2}}p^{2}не делит Φ n (b). {\ displaystyle \ Phi _ {n} (b).}{\displaystyle \Phi _{n}(b).}Пусть n = pm. Достаточно доказать, что p 2 {\ displaystyle p ^ {2}}p^{2}не делит S (b) для некоторого многочлена S (x), который кратен Φ n ( Икс). {\ displaystyle \ Phi _ {n} (x).}{\displaystyle \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}.}{\displaystyle 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}.}{\displaystyle 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}.}{\displaystyle p^{2}.}Это доказывает, что p 2 ∤ Φ n (b). {\ displaystyle p ^ {2} \ nmid \ Phi _ {n} (b).}{\displaystyle 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}}{\displaystyle 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}}{\displaystyle N=np_{1}p_{2}\cdots p_{k}}и рассмотрим Φ n (N) {\ displaystyle \ Phi _ {n} (N)}{\displaystyle \Phi _{n}(N)}. Пусть q {\ displaystyle q}qбудет простым множителем Φ n (N) {\ displaystyle \ Phi _ {n} (N)}{\displaystyle \Phi _{n}(N)}(to посмотрите, что Φ n (N) ≠ ± 1 {\ displaystyle \ Phi _ {n} (N) \ neq \ pm 1}{\displaystyle \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}},}{\displaystyle \Phi _{n}(x)\equiv \pm 1{\pmod {x}},}мы знайте, что q {\ displaystyle q}q- это новое простое число, которого нет в списке. Покажем, что q ≡ 1 (mod n). {\ displaystyle q \ Equiv 1 {\ pmod {n}}.}{\displaystyle 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}{\displaystyle \Phi _{n}(N)\mid N^{n}-1}у нас есть N n - 1 ≡ 0 (mod q) {\ displaystyle N ^ {n} -1 \ Equiv 0 {\ pmod {q}}}{\displaystyle N^{n}-1\equiv 0{\pmod {q}}}. Таким образом, m ∣ n {\ displaystyle m \ mid n}{\displaystyle m\mid n}. Мы покажем, что m = n {\ displaystyle m = n}m=n.

Предположим для противоречия, что m < n {\displaystyle mm<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}}}{\displaystyle \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}},}{\displaystyle \Phi _{d}(N)\equiv 0{\pmod {q}},}

для некоторых d < n {\displaystyle d{\displaystyle 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}}.}{\displaystyle \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} }.}{\displaystyle \left.{\frac {d(x^{n}-1)}{dx}}\right|_{N}\equiv nN^{n-1}\equiv 0{\pmod {q}}.}

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

Последняя правка сделана 2021-05-16 12:49:02
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте