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

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

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

и

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

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

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

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

Свойства

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

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

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

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

Количество

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

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

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

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

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

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

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

История

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

Примеры

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

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

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

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

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

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

$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

См. также

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

Литература

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

Ссылки

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