Корень из единицы по модулю n

В чисел теории корень k-й степени из единицы по модулю n для натуральных чисел k , n ≥ 2, является корнем из единицы в кольце целых чисел по модулю n ; есть решение x уравнения то (или сравнения ) $x^{k}\equiv 1{\pmod {n}}$. Если k является наименьшим таким показателем для x , то x называется примитивным корнем k- й степени из единицы по модулю n . См. модульную арифметику для обозначения и терминологии.

Корнями из единицы по модулю n являются в точности целые числа, взаимно простые с n . Фактически, эти целые числа являются корнями из единицы по модулю n по теореме Эйлера , а другие целые числа не могут быть корнями из единицы по модулю n , поскольку они являются делителями нуля по модулю n .

Примитивный корень по модулю n является генератором группы единиц кольца целых чисел по модулю n . существуют Примитивные корни по модулю n тогда и только тогда, когда $\lambda (n)=\varphi (n),$ где $\lambda$ и $\varphi$ являются соответственно функцией Кармайкла и функцией Эйлера .

Корень из единицы по модулю n — это примитивный корень k-й степени из единицы по модулю n для некоторого делителя k числа $\lambda (n),$ и, наоборот, существуют примитивные k- корни й степени из единицы по модулю n тогда и только тогда, когда k является делителем числа $\lambda (n).$

Корни единства

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

• Если x — корень k-й степени из единицы по модулю n , то x — единица (обратимая), обратная которой равна $x^{k-1}$. То есть x и n просты взаимно .
• Если x — единица, то это (примитивный) корень k- й степени из единицы по модулю n , где k — мультипликативный порядок по x модулю n .
• Если x — корень k-й степени из единицы и $x-1$ не является делителем нуля , то $\sum _{j=0}^{k-1}x^{j}\equiv 0{\pmod {n}}$, потому что

$(x-1)\cdot \sum _{j=0}^{k-1}x^{j}\equiv x^{k}-1\equiv 0{\pmod {n}}.$

Количество k- х корней

За неимением общепринятого обозначения, мы обозначаем число корней k- й степени из единицы по модулю n через $f(n,k)$.Он удовлетворяет ряду свойств:

• $f(n,1)=1$ для $n\geq 2$
• $f(n,\lambda (n))=\varphi (n)$ где λ обозначает функцию Кармайкла и $\varphi$ обозначает функцию Эйлера
• $n\mapsto f(n,k)$ это мультипликативная функция
• $k\mid \ell \implies f(n,k)\mid f(n,\ell )$ где черта означает делимость
• $f(n,\operatorname {lcm} (a,b))=\operatorname {lcm} (f(n,a),f(n,b))$ где $\operatorname {lcm}$ обозначает наименьшее общее кратное
• Для премьер $p$, $\forall i\in \mathbb {N} \ \exists j\in \mathbb {N} \ f(n,p^{i})=p^{j}$. Точное отображение из $i$ к $j$ не известно. Если бы он был известен, то вместе с предыдущим законом это дало бы возможность оценить $f$ быстро.

Примеры

Позволять $n=7$ и $k=3$. В этом случае имеется три кубических корня из единицы (1, 2 и 4). Когда $n=11$ однако существует только один кубический корень из единицы - сама единица 1. Такое поведение сильно отличается от поля комплексных чисел, где каждое ненулевое число имеет корни k k- й степени.

Первобытные корни единства

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

• Максимально возможный показатель системы счисления для примитивных корней по модулю $n$ является $\lambda (n)$, где λ обозначает функцию Кармайкла .
• Показатель системы счисления для примитивного корня из единицы делителем является $\lambda (n)$.
• Каждый делитель $k$ из $\lambda (n)$ дает примитив $k$корень единства. Такой корень можно получить, выбрав $\lambda (n)$примитивный корень из единицы (который должен существовать по определению λ), называемый $x$ и вычислить мощность $x^{\lambda (n)/k}$.
• Если x — примитивный корень k-й степени из единицы, а также (не обязательно примитивный) корень ℓ -й степени из единицы, то k является делителем ℓ. Это верно, поскольку тождество Безу дает целочисленную линейную комбинацию k , и ℓ равную $\gcd(k,\ell )$. Поскольку k минимально, оно должно быть $k=\gcd(k,\ell )$ и $\gcd(k,\ell )$ является делителем ℓ .

Количество примитивных k- го типа корней

Из-за отсутствия общепринятого символа мы обозначаем число примитивных k- корней й степени из единицы по модулю n через $g(n,k)$.Он удовлетворяет следующим свойствам:

• $g(n,k)={\begin{cases}>0&{\text{if }}k\mid \lambda (n),\\0&{\text{otherwise}}.\end{cases}}$
• Следовательно, функция $k\mapsto g(n,k)$ имеет $d(\lambda (n))$ значения, отличные от нуля, где $d$ вычисляет количество делителей .
• $g(n,1)=1$
• $g(4,2)=1$
• $g(2^{n},2)=3$ для $n\geq 3$, поскольку -1 всегда является квадратным корнем из 1.
• $g(2^{n},2^{k})=2^{k}$ для $k\in [2,n-1)$
• $g(n,2)=1$ для $n\geq 3$ и $n$ в (последовательность A033948 в OEIS )
• $\sum _{k\in \mathbb {N} }g(n,k)=f(n,\lambda (n))=\varphi (n)$ с $\varphi$ будучи полной функцией Эйлера
• Связь между $f$ и $g$ можно элегантно записать с помощью свертки Дирихле :

$f=\mathbf {1} *g$, то есть $f(n,k)=\sum _{d\mid k}g(n,d)$

Можно вычислить значения $g$ рекурсивно из $f$ используя эту формулу, которая эквивалентна формуле обращения Мёбиуса .

Проверка того, является ли x примитивным корнем k-й степени из единицы по модулю n

Путем быстрого возведения в степень можно проверить, что $x^{k}\equiv 1{\pmod {n}}$. Если это правда, то x — корень k-й степени из единицы по модулю n , но не обязательно примитивный. Если это не первообразный корень, то существовал бы некоторый делитель ℓ числа k с $x^{\ell }\equiv 1{\pmod {n}}$. Чтобы исключить такую ​​возможность, достаточно проверить несколько ℓ, равных k, разделенному на простое число. То есть необходимо проверить:

$\forall p{\text{ prime dividing}}\ k,\quad x^{k/p}\not \equiv 1{\pmod {n}}.$

Нахождение примитивного корня k-й степени из единицы по модулю n

Среди примитивных корней k-й степени из единицы примитивный $\lambda (n)$корни встречаются наиболее часто.Поэтому рекомендуется попробовать некоторые целые числа на предмет примитивности. $\lambda (n)$й корень, что быстро получится.Для примитива $\lambda (n)$корень x , число $x^{\lambda (n)/k}$ это примитив $k$корень единства.Если k не делит $\lambda (n)$ не будет , то корней k- й степени из единицы вообще .

Нахождение нескольких примитивных k-го корней порядка по модулю n

примитивный корень k-й степени из единицы x , каждая степень Как только получен $x^{\ell }$ это $k$корень из единицы, но не обязательно примитивный. Сила $x^{\ell }$ это примитив $k$корень из единицы тогда и только тогда, когда $k$ и $\ell$ взаимнопросты ​ . Доказательство следующее: если $x^{\ell }$ не примитивен, то существует делитель $m$ из $k$ с $(x^{\ell })^{m}\equiv 1{\pmod {n}}$, и поскольку $k$ и $\ell$ взаимно просты, существуют целые числа $a,b$ такой, что $ak+b\ell =1$. Это дает

$x^{m}\equiv (x^{m})^{ak+b\ell }\equiv (x^{k})^{ma}((x^{\ell })^{m})^{b}\equiv 1{\pmod {n}}$,

это означает, что $x$ это не примитив $k$корень из единицы, потому что есть меньший показатель степени $m$.

То есть, возведя x в степень , можно получить $\varphi (k)$ различные примитивные корни k-й степени из единицы, но это могут быть не все такие корни. Однако найти их всех не так-то просто.

Нахождение n с примитивным корнем k-й степени из единицы по модулю n

В каких кольцах целочисленных классов вычетов существует примитивный корень k- й степени из единицы? Его можно использовать для вычисления дискретного преобразования Фурье (точнее, теоретико-числового преобразования ) $k$-мерный целочисленный вектор . Чтобы выполнить обратное преобразование, разделите на $k$; то есть k также является единицей по модулю $n.$

Простой способ найти такое n — проверить наличие примитивных корней k- й степени по модулям арифметической прогрессии. $k+1,2k+1,3k+1,\dots$ Все эти модули взаимно просты с k , и, следовательно, k является единицей. Согласно теореме Дирихле об арифметических прогрессиях, в прогрессии бесконечно много простых чисел, и для простого числа $p$, оно держится $\lambda (p)=p-1$. Таким образом, если $mk+1$ является простым, то $\lambda (mk+1)=mk$, и, таким образом, существуют примитивные корни k- й степени из единицы. Но критерий для простых чисел слишком строг, и могут существовать другие подходящие модули.

Нахождение n с кратными примитивными корнями из единицы по модулю n

Чтобы найти модуль $n$ такие, что есть примитивные $k_{1}{\text{th}},k_{2}{\text{th}},\ldots ,k_{m}{\text{th}}$ корни единицы по модулю $n$, следующая теорема сводит задачу к более простой:

Для данного $n$ есть примитивные $k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}$ корни единицы по модулю $n$ тогда и только тогда, когда существует примитив $\operatorname {lcm} (k_{1},\ldots ,k_{m})$корень из единицы по модулю n .

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

Обратное направление:Если есть примитив $\operatorname {lcm} (k_{1},\ldots ,k_{m})$корень из единицы по модулю $n$ называется $x$, затем $x^{\operatorname {lcm} (k_{1},\ldots ,k_{m})/k_{l}}$ это $k_{l}$корень из единицы по модулю $n$.

Направление вперед:Если есть примитивные $k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}$ корни единицы по модулю $n$, то все показатели $k_{1},\dots ,k_{m}$ являются делителями $\lambda (n)$. Это подразумевает $\operatorname {lcm} (k_{1},\dots ,k_{m})\mid \lambda (n)$ а это, в свою очередь, означает, что существует примитив $\operatorname {lcm} (k_{1},\ldots ,k_{m})$корень из единицы по модулю $n$.