Первообразный корень (теория чисел)

Первообразный корень по модулю m ― целое число g такое, что

${\displaystyle g^{\varphi (m)}\equiv 1{\pmod {m}}}$

и

${\displaystyle g^{\ell }\not \equiv 1{\pmod {m}}}$ при ${\displaystyle 1\leq \ell <\varphi (m),}$

где ${\displaystyle \varphi (m)}$ ― функция Эйлера. Другими словами, первообразный корень — это образующий элемент мультипликативной группы кольца вычетов по модулю m.

Чтобы не проверять все ${\displaystyle \ell }$ от ${\displaystyle 1}$ до ${\displaystyle \varphi (m)}$, достаточно проверить три условия:

1. Является ли ${\displaystyle g}$ числом взаимно простым с ${\displaystyle m}$, и если нет - то это не первообразный корень.
2. Так как ${\displaystyle \varphi (m)}$ - всегда чётное число для всех ${\displaystyle m>2}$, то ${\displaystyle \varphi (m)}$ имеет как минимум один простой делитель - простое число ${\displaystyle 2}$, следовательно, для того, чтобы отсеять значительное количество не-корней, достаточно проверить ${\displaystyle g^{\varphi (m)/2}\not \equiv 1{\pmod {m}}}$ для числа, подходящего на первообразный корень по модулю ${\displaystyle m}$.^[1] Если результат +1 ${\displaystyle \equiv }$ m , то g - не корень, в ином случае результат -1 ${\displaystyle \equiv }$ m, когда g - это возможно первообразный корень.
3. Далее следует убедиться, что ${\displaystyle g^{\ell }\not \equiv 1{\pmod {m}}}$ для всех ${\displaystyle \ell ={\frac {\varphi (m)}{p}}}$, где ${\displaystyle p}$ - простой делитель числа ${\displaystyle \varphi (m)}$, полученный в результате его факторизации.

Свойства

Существование

Первообразные корни существуют только по модулям ${\displaystyle m}$ вида

${\displaystyle m=2,4,p^{a},2p^{a}}$,

где ${\displaystyle p>2}$ ― простое число, ${\displaystyle a\geqslant 1}$ ― натуральное. Только в этих случаях мультипликативная группа кольца вычетов по модулю m является циклической группой порядка ${\displaystyle \varphi (m)}$.

Количество

Если по модулю ${\displaystyle m}$ существует первообразный корень ${\displaystyle g}$, то всего существует ${\displaystyle \varphi (\varphi (m))}$ различных первообразных корней по модулю m, причём все они имеют вид ${\displaystyle g^{k}}$, где ${\displaystyle 1\leq k<\varphi (m)}$ и ${\displaystyle (k,\varphi (m))=1}$.

Индекс числа по модулю

Для первообразного корня ${\displaystyle g}$ его степени ${\displaystyle g^{\varphi (m)}=1,g,\dots g^{\varphi (m)-1}}$ несравнимы между собой по модулю m и образуют приведенную систему вычетов по модулю m. Поэтому для каждого числа ${\displaystyle a}$, взаимно простого с ${\displaystyle m}$, найдется показатель ${\displaystyle \ell ,0\leq \ell <\varphi (m)}$, такой, что

${\displaystyle g^{\ell }\equiv a{\pmod {m}}.}$

Такое число ${\displaystyle \ell }$ называется индексом числа a по основанию g.

Минимальный корень

Исследования Виноградова показали, что существует такая константа ${\displaystyle C}$, что для всякого простого ${\displaystyle p}$ существует первообразный корень ${\displaystyle g<C{\sqrt {p}}}$. Другими словами, для простых модулей ${\displaystyle p}$ минимальный первообразный корень имеет порядок ${\displaystyle O({\sqrt {p}})}$. Математик Виктор Шуп^[англ.] из Университета Торонто показал, что если «Обобщённая гипотеза Римана» верна, то первообразный корень есть среди первых ${\displaystyle O(\log ^{6}{p})}$ чисел натурального ряда^[2].

История

Первообразные корни для простых модулей ${\displaystyle p}$ были введены Эйлером, но существование первообразных корней для любых простых модулей ${\displaystyle p}$ было доказано лишь Гауссом в «Арифметических исследованиях» (1801 год).

Примеры

Число 3 является первообразным корнем по модулю 7. Чтобы в этом убедиться, достаточно каждое число от 1 до 6 представить как некоторую степень тройки по модулю 7:

${\displaystyle 3^{1}\equiv 3\ {\pmod {7}}}$

${\displaystyle 3^{2}\equiv 2\ {\pmod {7}}}$

${\displaystyle 3^{3}\equiv 6\ {\pmod {7}}}$

${\displaystyle 3^{4}\equiv 4\ {\pmod {7}}}$

${\displaystyle 3^{5}\equiv 5\ {\pmod {7}}}$

${\displaystyle 3^{6}\equiv 1\ {\pmod {7}}}$

Примеры наименьших первообразных корней по модулю m (последовательность A046145 в OEIS):

Модуль m	2	3	4	5	6	7	8	9	10	11	12	13	14
Первообразный корень	1	2	3	2	5	3	—	2	3	2	—	2	3

См. также

• Гипотеза Артина
• Дискретное логарифмирование
• Показатель числа по модулю

Примечания

1. Primitive Root - Competitive Programming Algorithms  (неопр.). cp-algorithms.com. Дата обращения: 27 октября 2020. Архивировано 24 октября 2020 года.
2. Bach, Eric; Shallit, Jeffrey. Algorithmic Number Theory (Vol I: Efficient Algorithms). — Cambridge: The MIT Press, 1996. — P. 254. — ISBN 978-0-262-02405-1.

Литература

• Виноградов И. М. Глава 6. Первообразные корни и индексы // Основы теории чисел. — 1952. — 182 с.
• Нестеренко Ю. В. Глава 7. Первообразные корни и индексы // Теория чисел. — М.: «Академия», 2008. — 464 с.

Ссылки

• «Первообразные корни» на сайте MAXimal Архивная копия от 1 декабря 2011 на Wayback Machine
• Weisstein, Eric W. Primitive Root (англ.) на сайте Wolfram MathWorld.