Неприводимый многочлен, корни которого являются корнями n-й степени из единицы
В математике n-й круговой многочлен для любого натурального числа n является уникальным неприводимым многочленом с целыми коэффициентами, который является делителем числа
и не является делителем
для любого k < n. Its корни - все n-е примитивные корни из единицы
, где k пробегает положительные целые числа, не превышающие n, и взаимно простое с n (и i - это мнимая единица ). Другими словами, n-й круговой многочлен равен

Его также можно определить как монический многочлен с целыми коэффициентами, который является минимальным многочленом над поле рациональных чисел любого первообразного корня n-й степени из единицы (
- пример такого корня).
Важным соотношением, связывающим циклотомические многочлены и первообразные корни из единицы, является

показывает, что x является корнем из
, если и только если это 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 = 2p, где p - нечетное простое число, то

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

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

Свойства
Основные инструменты
Циклотомические многочлены являются моническими многочленами с целыми коэффициентами, неприводимыми над полем рациональных чисел. За исключением n, равного 1 или 2, они являются палиндромами четной степени.
Степень
, или, другими словами, количество n-х примитивных корней из единицы составляет
, где
- это функция Эйлера.
Тот факт, что
- неприводимый многочлен степени
в кольцо
- нетривиальный результат из-за Gauss. В зависимости от выбранного определения, нетривиальным результатом является либо значение степени, либо неприводимость. Случай простого n легче доказать, чем общий случай, благодаря критерию Эйзенштейна.
Фундаментальное соотношение, включающее круговые полиномы, имеет вид

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

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

Циклотомический многочлен
может быть вычислено (точно) делением
на циклотомические многочлены собственных делителей n, ранее вычисленных рекурсивно, на те же метод:
(Напомним, что
.)
Эта формула позволяет вычислить
на компьютере для любого n, как только доступны целочисленная факторизация и деление многочленов. Многие системы компьютерной алгебры имеют встроенную функцию для вычисления циклотомических полиномов. Например, эта функция вызывается путем ввода cyclotomic_polynomial (n, x)
в SageMath, numtheory [cyclotomic] (n, x);
в Maple, Cyclotomic [n, x]
в Mathematica и polcyclo (n, x)
в PARI / GP.
Easy случаи для вычисления
Как отмечалось выше, если n - простое число, то

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

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

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

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

Эти формулы можно применять многократно, чтобы получить простое выражение для любого круговой многочлен
в терминах кругового многочлена индекса без квадратов : если q является произведение простых делителей числа n (его радикал ), то

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



Для других значений n вычисление n-го кругового многочлена аналогично сокращается до вычисления
где q - произведение различных нечетных простых делителей числа n. Чтобы разобраться в этом случае, нужно иметь, что для простого p, не делящего n,

Целые числа в виде коэффициентов
Проблема ограничения величины коэффициентов круговых многочленов была объектом ряда исследовательских работ.
Если n имеет не более двух различных нечетных простых множителей, то Миготти показал, что все коэффициенты
входят в набор {1, -1, 0}.
Первый циклотомический многочлен для произведения трех разных нечетных простых множителей равен
он имеет коэффициент -2 (см. его выражение выше). Обратное неверно:
имеет только коэффициенты в {1, −1, 0}.
Если n является произведением нескольких различных нечетных простых множителей, коэффициенты могут увеличиваться до очень высоких значений. Например,
имеет коэффициенты от −22 до 23,
, наименьшее 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. Тогда:

, где и 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), и в этом случае он антипалиндромный.
Первые несколько случаев:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0a83de9b0cde73a918cf03c71e45b6ad3fcdf33)
Пусть n нечетное, без квадратов и больше 3. Тогда

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

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

, где и C n (z), и D n (z) имеет целочисленные коэффициенты, C n (z) имеет степень φ (n), а D n (z) имеет степень φ (n) - 1. Оба C n (z) и D n (z) являются палиндромными.
Первые несколько случаев:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0cca61f37705f3e9001225f94a45b1f9f92919b)
Циклотомические многочлены над конечным полем и над целыми p-адическими числами
Над конечным полем с простым числом p элементов, для любого целого n, не кратного p, циклотомический многочлен
разлагается на
неприводимые многочлены степени d, где
- это функция тотализатора Эйлера, а d - мультипликативный порядок числа p по модулю n. В частности,
неприводимо тогда и только тогда, когда p является примитивным корнем по модулю n, то есть p не делит n, и его мультипликативный порядок по модулю n равен
, степень
.
Эти результаты также верны для целых p-адических чисел, поскольку лемма Хензеля позволяет поднять факторизацию по полю с p элементами до факторизации над целыми p-адическими числами.
Значения полиномов
Если x принимает любое действительное значение, то
для каждого n ≥ 3 (это следует из того факта, что все корни кругового многочлена не являются действительными при n ≥ 3).
Для изучения значений, которые может принимать циклотомический многочлен, когда x задано целое значение, достаточно рассмотреть только случай n ≥ 3, так как случаи n = 1 и n = 2 тривиальны (у одного
и
).
Для n ≥ 2 имеем

, если n не является степенью простого числа,
, если
- степень простого числа с k ≥ 1.
Значения, которые циклотомический многочлен
, который может принимать другие целые значения x, сильно связан с порядком умножения по модулю простого числа.
Точнее, учитывая простое число p и целое число b, взаимно простое с p, мультипликативный порядок b по модулю p - это наименьшее положительное целое число n такое, что p является делителем
Для b>1 мультипликативный порядок b по модулю p также является кратчайшим периодом представления 1 / p в числовое основание b (см. Уникальное простое число ; это объясняет выбор нотации).
Из определения мультипликативного порядка следует, что, если n - мультипликативный порядок b по модулю p, то p является делителем
Обратное неверно, но имеет место следующее.
Если n>0 - целое положительное число, а b>1 - целое, то (см. Доказательство ниже)

где
- 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 делитель p - 1, либо p делитель n. В последнем случае
не делит 
Теорема Зигмонди подразумевает, что единственными случаями, когда b>1 и h = 1, являются

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

- это в точности такие нечетные простые числа p, что n является мультипликативным порядком числа b по модулю p. Эта дробь может быть четным только тогда, когда b нечетно. В этом случае мультипликативный порядок b по модулю 2 всегда равен 1.
Существует много пар (n, b) с b>1, таких что
простое число. Фактически, Буняковский гипотеза подразумевает, что для любого n существует бесконечно много b>1 таких, что
простое число. См. OEIS : A085398 для получения списка наименьших b>1 таких, что
- простое число (наименьшее b>1 такое, что
простое число составляет примерно
, где
равно константа Эйлера – Маскерони, и
- это функция Эйлера ). См. Также OEIS : A206864 для получения списка наименьших простых чисел формы
с n>2 и b>1, и, в более общем смысле, OEIS : A206942, для наименьших положительных целых чисел этой формы.
Доказательства |
---|
- Значения
Если - это степень простого числа, тогда

- Если n не является степенью простого числа, пусть
мы имеем и P является произведением для k делит n и отличается от 1. Если p является простым делителем, кратным m от n, то делят P (x), и их значения при 1 - это m факторов, равных p из Поскольку m - это кратность p в n, p не может делить значение на 1 из других факторов Таким образом, нет простого числа, делящего 
- Если n - порядок умножения b по модулю p, то
По определению, Если , то p разделит другой множитель из и, таким образом, разделит показывая, что, если бы это было так, n не было бы порядком умножения b по модулю p.
- Другие простые делители числа
являются делителями n. Пусть p - простой делитель числа такой, что n не является порядком умножения b по модулю p. Если k - порядок умножения b по модулю p, то p делит как , так и , результат из и можно записать как где P и Q - многочлены. Таким образом, p делит результат. Поскольку k делит n, а результат двух многочленов делит дискриминант любого общего кратного этих многочленов, p делит также дискриминант из Таким образом, p делит n.
- g и h взаимно просты. Другими словами, если p является простым общим делителем n и
, то n не является мультипликативным порядком из b по модулю p. Согласно маленькой теореме Ферма, мультипликативный порядок числа b является делителем p - 1 и, следовательно, меньше n.
- g не содержит квадратов. Другими словами, если p является простым общим делителем n и
, то не делит Пусть n = pm. Достаточно доказать, что не делит S (b) для некоторого многочлена S (x), который кратен Возьмем

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

- Поскольку p простое число и больше 2, все члены, кроме первого, кратны
Это доказывает, что 
|
Приложения
с использованием
, можно дать элементарное доказательство бесконечности простых чисел , конгруэнтных 1 по модулю n, что является частным случаем теоремы Дирихле об арифметических прогрессиях.
Доказательство |
---|
Предположим, что - конечный список простых чисел конгруэнтно по модулю Пусть и рассмотрим . Пусть будет простым множителем (to посмотрите, что разложите его на линейные множители и обратите внимание, что 1 - ближайший корень единицы до ). Поскольку мы знайте, что - это новое простое число, которого нет в списке. Покажем, что 
Пусть будет порядком по модулю Так как у нас есть . Таким образом, . Мы покажем, что .
Предположим для противоречия, что 
мы имеем 
для некоторых - ∏ d ∣ n Φ d (x) ≡ x n - 1 (mod q). {\ displaystyle \ prod _ {d \ mid n} \ Phi _ {d} (x) \ Equiv x ^ {n} -1 {\ pmod {q}}.}

Таким образом, N {\ displaystyle 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} }.}

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