Первообразный корень

Определение "Первообразный корень" в Большой Советской Энциклопедии

Первообразный корень по модулю m, такое число g, что положительное наименьшее число k, для которого разность g^k — 1 делится на m (g^k сравнимо с 1 по модулю m), совпадает c j(m), где j(m) — число натуральных чисел, меньших m и взаимно простых с m. Например, при m =  7 Первообразный корень по модулю 7 является число 3. Действительно j(7) = 6; числа 3¹ — 1 = 2, 3² — 1 = 8, 3³ — 1 = 26, 3⁴ — 1 = 80, 3⁵ — 1 = 242 не делятся на 7, лишь 3⁶ — 1 = 728 делится на 7. Первообразный корень существуют, когда m = 2, m = 4, m = р^a, m = 2p^a (где р — простое нечётное число, a — целое ³1), а для других модулей их нет. Число Первообразный корень в этих случаях равно j[j(m)] (числа, разность которых кратна m, не считаются за различные). И. М. Виноградов в 1926 установил, что в интервале (1, 2^2klnp) найдётся Первообразный корень по модулю р, где р — простое нечётное число, k — число различных простых делителей числа р — 1. См. также Чисел теория, Индексы в теории чисел.
Лит.: Виноградов И. М., Основы теории чисел, 8 изд., М., 1972; его же, Избр. труды. М., 1952, с. 54—57.