Циклотомический полином - Cyclotomic polynomial

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

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

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

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

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

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

Примеры

Если п это простое число, тогда

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

Если п = 2п где п это странно простое число, тогда

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

За п до 30 круговыми многочленами являются:^[1]

{ Displaystyle { begin {align} 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 {выравнивается}}}

Случай 105-го кругового полинома интересен тем, что 105 - это наименьшее целое число, которое является произведением трех различных нечетных простых чисел (3 * 5 * 7), и этот полином является первым, имеющим коэффициент кроме 1, 0 или -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 {выравнивается}}}

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

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

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

Степень ${ displaystyle Phi _ {n}}$ , или другими словами количество ппервобытные корни единства, ${ Displaystyle varphi (п)}$ , где ${ displaystyle varphi}$ является Функция Эйлера.

Дело в том, что ${ displaystyle Phi _ {n}}$ является неприводимым многочленом степени ${ Displaystyle varphi (п)}$ в кольцо ${ Displaystyle mathbb {Z} [х]}$ является нетривиальным результатом из-за Гаусс.^[2] В зависимости от выбранного определения, нетривиальным результатом является либо значение степени, либо неприводимость. Случай простого п легче доказать, чем общий случай, благодаря Критерий Эйзенштейна.

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

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

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

В Формула обращения Мебиуса позволяет выразить ${ Displaystyle Phi _ {п} (х)}$ как явная рациональная дробь:

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

где ${ displaystyle mu}$ это Функция Мёбиуса.

В преобразование Фурье функций наибольший общий делитель вместе с Формула обращения Мебиуса дает:^[3]

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

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

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

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

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

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

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

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

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

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

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

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

Если $п = п м$ это основная сила (где п простое число), то

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

В более общем смысле, если $п = п м р$ с $р$ относительно простой $п$ , тогда

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

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

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

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

{ Displaystyle Phi _ {2 ^ {ч}} (х) = х ^ {2 ^ {ч-1}} + 1}

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

{ Displaystyle Phi _ {2 ^ {h} p ^ {k}} (x) = sum _ {i = 0} ^ {p-1} (- 1) ^ {i} x ^ {i2 ^ { ч-1} р ^ {к-1}}}

Для остальных значений $п$ , вычисление $п$ -й круговой полином аналогично сводится к полиному ${ Displaystyle Phi _ {q} (х),}$ где $q$ является произведением различных нечетных простых делителей числа $п$ . Чтобы разобраться в этом случае, нужно, чтобы $п$ простое и неделящееся $п$ ,^[5]

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

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

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

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

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

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

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

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

Позволять п быть нечетным, без квадратов и больше 3. Тогда:^[8]^[9]

{ Displaystyle 4 Phi _ {n} (z) = A_ {n} ^ {2} (z) - (- 1) ^ { frac {n-1} {2}} nz ^ {2} B_ { п} ^ {2} (г)}

где оба А_п(z) и B_п(z) имеют целые коэффициенты, А_п(z) имеет степень φ(п) / 2, и B_п(z) имеет степень φ(п) / 2 - 2. Кроме того, А_п(z) палиндромный, когда его степень четна; если его степень нечетная, это антипалиндромный эффект. Так же, B_п(z) палиндромный, если п является составным и 3 (mod 4), и в этом случае он антипалиндромный.

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

{ 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 {выровнено }}}

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

Позволять п быть нечетным, бесквадратным и больше 3. Тогда^[10]

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

где оба U_п(z) и V_п(z) имеют целые коэффициенты, U_п(z) имеет степень φ(п) / 2, и V_п(z) имеет степень φ(п) / 2 - 1. Это также можно записать

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

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

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

где оба C_п(z) и D_п(z) имеют целые коэффициенты, C_п(z) имеет степень φ(п), и D_п(z) имеет степень φ(п) − 1. C_п(z) и D_п(z) оба палиндромны.

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

{ 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 {выровнено}}}

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

Через конечное поле с простым числом $п$ элементов, для любого целого числа $п$ это не кратно $п$ , круговой полином ${ displaystyle Phi _ {n}}$ разлагается на ${ displaystyle { frac { varphi (n)} {d}}}$ неприводимые многочлены степени $d$ , где ${ Displaystyle varphi (п)}$ является Функция Эйлера и $d$ это мультипликативный порядок из $п$ по модулю $п$ . Особенно, ${ displaystyle Phi _ {n}}$ неприводимо если и только если $п$ это примитивный корень по модулю $п$ , это, $п$ не разделяет $п$ , и его мультипликативный порядок по модулю $п$ является ${ Displaystyle varphi (п)}$ , степень ${ displaystyle Phi _ {n}}$ .^{[нужна цитата ]}

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

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

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

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

За $п \geq 2$ , надо

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

{ Displaystyle Phi _ {п} (1) = 1}

если

п

это не основная сила,

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

если

{ Displaystyle п = р ^ {к}}

это основная сила с

k \geq 1

.

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

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

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

Если $п > 0$ положительное целое число и $б > 1$ является целым числом, то (см. доказательство ниже)

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

где

$k$ - неотрицательное целое число, всегда равное 0, когда $б$ даже. (Фактически, если $п$ не равно ни 1, ни 2, то $k$ либо 0, либо 1. Кроме того, если $п$ это не степень 2, тогда $k$ всегда равно 0)
$г$ 1 или наибольший нечетный простой делитель числа $п$ .
$час$ нечетное, взаимно простое с $п$ , и это главные факторы в точности нечетные простые числа $п$ такой, что $п$ это мультипликативный порядок $б$ по модулю $п$ .

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

Теорема Жигмонди означает, что единственные случаи, когда $б > 1$ и $час = 1$ находятся

{ 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 { frac { Phi _ {n} (b)} { gcd (n, Phi _ {n} (b))}}}

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

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

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

Ценности ${ displaystyle Phi _ {n} (1).}$ Если ${ Displaystyle п = р ^ {к + 1}}$ это простая степень, тогда

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

Если

п

не главная сила, пусть

{ Displaystyle Р (х) = 1 + х + cdots + х ^ {п-1},}

у нас есть

{ Displaystyle P (1) = п,}

и

п

продукт

{ Displaystyle Phi _ {к} (х)}

за

k

разделение

п

и отличается от

1

. Если

п

простой делитель кратности

м

в

п

, тогда

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

разделять

п (Икс)

, а их значения при

1

находятся

м

факторы равные

п

из

{ displaystyle n = P (1).}

Так как

м

это кратность

п

в

п

,

п

не может делить стоимость на

1

других факторов

{ Displaystyle P (x).}

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

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

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

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

$г$ и $час$ взаимно просты. Другими словами, если $п$ является простым общим делителем $п$ и ${ Displaystyle Phi _ {п} (б),}$ тогда $п$ не является мультипликативным порядком $б$ по модулю $п$ . От Маленькая теорема Ферма, мультипликативный порядок $б$ является делителем $п - 1$ , и, следовательно, меньше, чем $п$ .

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

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

Мультипликативный порядок

б

по модулю

п

разделяет

gcd (п, п - 1)

, который является делителем

м = п / п

. Таким образом

c = б м - 1

кратно

п

. Сейчас же,

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

Так как

п

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

{ displaystyle p ^ {2}.}

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

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

Приложения

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

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

Предположим ${ displaystyle p_ {1}, p_ {2}, ldots, p_ {k}}$ конечный список простых чисел, конгруэнтных ${ displaystyle 1}$ по модулю ${ displaystyle n.}$ Позволять ${ displaystyle N = np_ {1} p_ {2} cdots p_ {k}}$ и рассмотреть ${ displaystyle Phi _ {n} (N)}$ . Позволять ${ displaystyle q}$ быть основным фактором ${ Displaystyle Phi _ {п} (N)}$ (чтобы увидеть, что ${ Displaystyle Phi _ {п} (N) neq pm 1}$ разложите его на линейные множители и обратите внимание, что 1 - ближайший корень из единицы к ${ displaystyle N}$ ). поскольку ${ Displaystyle Phi _ {п} (х) эквив пм 1 { pmod {х}},}$ мы знаем это ${ displaystyle q}$ нового прайма нет в списке. Мы покажем, что ${ Displaystyle q Equiv 1 { pmod {n}}.}$

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

Предположим от противного, что ${ Displaystyle м <п}$ . поскольку

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

у нас есть

{ Displaystyle Phi _ {d} (N) Equiv 0 { pmod {q}},}

для некоторых ${ displaystyle d$ . потом ${ displaystyle N}$ двойной корень из

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

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

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

Но ${ displaystyle q nmid N}$ и поэтому ${ displaystyle q nmid n.}$ Это противоречие, поэтому ${ displaystyle m = n}$ . Получатель чего-то ${ displaystyle N { pmod {q}},}$ который ${ displaystyle n}$ , должен разделить ${ displaystyle q-1}$ . Таким образом ${ Displaystyle q Equiv 1 { pmod {n}}.}$

Смотрите также

Примечания

^ Слоан, Н. Дж. А. (ред.). «Последовательность A013595». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
^ Ланг, Серж (2002), Алгебра, Тексты для выпускников по математике, 211 (Пересмотренное третье изд.), Нью-Йорк: Springer-Verlag, ISBN 978-0-387-95385-4, Г-Н 1878556
^ Шрамм, Вольфганг (2015). "Eine Alternative Produktdarstellung für die Kreisteilungspolynome". Elemente der Mathematik. Швейцарское математическое общество. 70 (4): 137–143. Архивировано из оригинал на 2015-12-22. Получено 2015-10-10.
^ Кокс, Дэвид А. (2012), «Упражнение 12», Теория Галуа (2-е изд.), John Wiley & Sons, стр. 237, г. Дои:10.1002/9781118218457, ISBN 978-1-118-07205-9.
^ Вайсштейн, Эрик В. «Циклотомический многочлен». Получено 12 марта 2014.
^ Айзекс, Мартин (2009). Алгебра: выпускной курс. Книжный магазин AMS. п. 310. ISBN 978-0-8218-4799-2.
^ Мейер (2008)
^ Гаусс Д.А., Статьи 356-357.
^ Ризель, стр. 315-316, стр. 436
^ Ризель, стр. 309-315, стр. 443
^ С. Ширали. Теория чисел. Orient Blackswan, 2004. стр. 67. ISBN 81-7371-454-1

использованная литература

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

Гаусс, Карл Фридрих (1986) [1801]. Disquisitiones Arithmeticae. Переведено на английский Кларком, Артуром А. (2-е изд. Корр.). Нью-Йорк: Springer. ISBN 0387962549.
Гаусс, Карл Фридрих (1965) [1801]. Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae и другие статьи по теории чисел). Перевод на немецкий язык Мазером, Х. (2-е изд.). Нью-Йорк: Челси. ISBN 0-8284-0191-8.
Леммермейер, Франц (2000). Законы взаимности: от Эйлера до Эйзенштейна. Берлин: Springer. Дои:10.1007/978-3-662-12893-0. ISBN 978-3-642-08628-1.
Майер, Гельмут (2008), «Анатомия целых чисел и циклотомических многочленов», в Де Конинк, Жан-Мари; Гранвиль, Эндрю; Лука, Флориан (ред.), Анатомия целых чисел. По материалам семинара CRM, Монреаль, Канада, 13-17 марта 2006 г., Материалы и лекции по CRM, 46, Провиденс, Род-Айленд: Американское математическое общество, стр. 89–95, ISBN 978-0-8218-4406-9, Zbl 1186.11010
Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации (2-е изд.). Бостон: Биркхойзер. ISBN 0-8176-3743-5.

внешняя ссылка

[1] Слоан, Н. Дж. А. (ред.). «Последовательность A013595». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.

[2] Ланг, Серж (2002), Алгебра, Тексты для выпускников по математике, 211 (Пересмотренное третье изд.), Нью-Йорк: Springer-Verlag, ISBN 978-0-387-95385-4, Г-Н 1878556

[3] Шрамм, Вольфганг (2015). "Eine Alternative Produktdarstellung für die Kreisteilungspolynome". Elemente der Mathematik. Швейцарское математическое общество. 70 (4): 137–143. Архивировано из оригинал на 2015-12-22. Получено 2015-10-10.

[4] Кокс, Дэвид А. (2012), «Упражнение 12», Теория Галуа (2-е изд.), John Wiley & Sons, стр. 237, г. Дои:10.1002/9781118218457, ISBN 978-1-118-07205-9.

[WolframCyclotomic-5] Вайсштейн, Эрик В. «Циклотомический многочлен». Получено 12 марта 2014.

[6] Айзекс, Мартин (2009). Алгебра: выпускной курс. Книжный магазин AMS. п. 310. ISBN 978-0-8218-4799-2.

[Mei2008-7] Мейер (2008)

[8] Гаусс Д.А., Статьи 356-357.

[9] Ризель, стр. 315-316, стр. 436

[10] Ризель, стр. 309-315, стр. 443

[11] С. Ширали. Теория чисел. Orient Blackswan, 2004. стр. 67. ISBN 81-7371-454-1

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]