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

У этого термина существуют и другие значения, см. Первообразный корень.

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

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

и

${\displaystyle g^{\ell }\not \equiv 1{\pmod {m}}}$ при ${\displaystyle 1\leqslant \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 =\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}{\pmod {m}}}$, где ${\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 ,1\leq \ell \leq \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

См. также

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