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

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

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

Для первообразного корня g его степени g⁰=1, g, …, g^{φ(m) − 1} несравнимы между собой по модулю m и образуют приведенную систему вычетов по модулю m. Поэтому для каждого числа a, взаимно простого с m, найдется показатель ℓ, 0 ⩽ ℓ ⩽ φ(m) − 1, такой, что

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

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

Количество

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

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

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

История

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

См. также

Примечания

Primitive Root - Competitive Programming Algorithms (неопр.). cp-algorithms.com. Дата обращения: 27 октября 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 с.

Ссылки

«Первообразные корни» на сайте MAXimal
Weisstein, Eric W. Primitive Root (англ.) на сайте Wolfram MathWorld.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Primitive Root - Competitive Programming Algorithms (неопр.). cp-algorithms.com. Дата обращения: 27 октября 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.