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

Эта статья может потребовать очистки, чтобы соответствовать стандартам качества Википедии . Конкретная проблема: отсутствие контекста, отсутствие явных примеров, отсутствие объяснения основных различий с Корнем единицы и Конечным полем § Корни единицы . Пожалуйста, помогите улучшить эту статью, если можете. ( Октябрь 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

Корни единства [ править ]

Свойства [ править ]

• Если x - корень k -й степени из единицы по модулю n , то x - единица (обратимая), обратная которой есть . То есть, х и п являются взаимно простыми .${\ Displaystyle х ^ {к-1}}$
• Если х является единицей, то это (примитивный) K -го корень из единицы по модулю п , где к является мультипликативный порядок по х по модулю п .
• Если 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 -й корней [ править ]

Из-за отсутствия общепринятого символа мы обозначаем количество корней 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 l\implies f(n,k)\mid f(n,l)}$где черта обозначает делимость
• ${\displaystyle f(n,\mathrm {lcm} (a,b))=\mathrm {lcm} (f(n,a),f(n,b))}$где обозначает наименьшее общее кратное${\displaystyle \mathrm {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}$

Первобытные корни единства [ править ]

Свойства [ править ]

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

Количество примитивных корней k [ править ]

Из-за отсутствия общепринятого символа мы обозначаем количество примитивных корней 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)}$с тем totient функцией Эйлера${\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 [ править ]

Вы можете проверить это с помощью быстрого возведения в степень . Если это так, 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 -й степени из единицы по модулю n [ править ]

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

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

Если у вас есть примитивный корень k -й степени из единицы x , каждая степень является корнем -й степени из единицы, но не обязательно примитивной. Сила является примитивным -й корень из единицы , если и только если и являются взаимно простыми . Доказательство заключается в следующем: если не примитивен, то существует делитель из с , и так и взаимно просты, то существует обратная по модулю . Это дает , что означает, что это не примитивный корень -й степени из единицы, потому что существует меньшая степень .${\displaystyle x^{l}}$${\displaystyle k}$${\displaystyle x^{l}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle l}$${\displaystyle x^{l}}$${\displaystyle m}$${\displaystyle k}$${\displaystyle (x^{l})^{m}\equiv 1{\pmod {n}}}$${\displaystyle k}$${\displaystyle l}$${\displaystyle l^{-1}}$${\displaystyle l}$${\displaystyle k}$${\displaystyle 1\equiv ((x^{l})^{m})^{l^{-l}}\equiv x^{m}{\pmod {n}}}$${\displaystyle x}$${\displaystyle k}$${\displaystyle m}$

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

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

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

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

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

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

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

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

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

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

Ссылки [ править ]