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

Первообразный корень по модулю 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)$ , достаточно проверить три условия:

Является ли $g$ числом взаимно простым с $m$ , и если нет - то это не первообразный корень.
Так как $\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 - это возможно первообразный корень.
Далее следует убедиться, что $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 (последовательность в 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

См. также

Примечания

(неопр.) . cp-algorithms.com . Дата обращения: 27 октября 2020. 24 октября 2020 года.
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 с.