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

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

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

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

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

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

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

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

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

Количествоккорни

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

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

Примеры

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

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

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

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

Число примитивныхккорни

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

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

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

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

Тестирование того,хявляется примитивнымккорень из единицы по модулюн

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

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

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

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

Нахождение нескольких примитивовккорни по модулюн

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Финч, Стивен; Мартин, Грег; Себах, Паскаль (2010). «Корни из единицы и нуля по модулю n» (PDF) . Труды Американского математического общества . 138 (8): 2729–2743. doi : 10.1090/s0002-9939-10-10341-4 . Получено 20.02.2011 .