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

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

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

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

и

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

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

Свойства

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

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

m = 2, 4, p^a, 2p^a,

где p > 2 ― простое число. Только в этих случаях мультипликативная группа кольца вычетов по модулю m является циклической группой порядка φ(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 ⩽ k ⩽ φ(m)-1 и k взаимно просто с φ(m).

История

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

Примеры

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

$3^0 \equiv 1\ \pmod 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$

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

См. также

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

Ссылки

• "Первообразные корни" на сайте MAXimal