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

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

[math]\displaystyle{ g^{\varphi(m)} \equiv 1 \pmod m }[/math],

где [math]\displaystyle{ \varphi(m) }[/math] ― функция Эйлера, при этом для любого меньшего числа [math]\displaystyle{ 1\le\ n \lt \varphi(m), }[/math] [math]\displaystyle{ g^{n} \not\equiv 1 \pmod m }[/math]. Последовательные степени числа g, начиная с [math]\displaystyle{ g^{0} }[/math], образуют приведённую систему вычетов по модулю m. В терминах теории колец первообразный корень — это порождающий элемент мультипликативной группы кольца вычетов по модулю m.

Свойства

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

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

[math]\displaystyle{ m=2,4,p^a,2p^a }[/math],

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

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

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

[math]\displaystyle{ g^{\ell} \equiv a \pmod m. }[/math]

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

Количество

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

Оценка минимального корня

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

История

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

Примеры

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

[math]\displaystyle{ 3^1 \equiv 3\ \pmod 7 }[/math]

[math]\displaystyle{ 3^2 \equiv 2\ \pmod 7 }[/math]

[math]\displaystyle{ 3^3 \equiv 6\ \pmod 7 }[/math]

[math]\displaystyle{ 3^4 \equiv 4\ \pmod 7 }[/math]

[math]\displaystyle{ 3^5 \equiv 5\ \pmod 7 }[/math]

[math]\displaystyle{ 3^6 \equiv 1\ \pmod 7 }[/math]

Примеры наименьших первообразных корней по модулю 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

См. также

Примечания

↑ 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.

[1] Bach, Eric; Shallit, Jeffrey. Algorithmic Number Theory (Vol I: Efficient Algorithms). — Cambridge: The MIT Press, 1996. — P. 254. — ISBN 978-0-262-02405-1.

[1]