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

Определение «Первообразный корень» по БСЭ:
Первообразный корень - по модулю m, такое число g, что положительное наименьшее число k, для которого разность g^k−1 делится на m (g^k сравнимо с 1 по модулю m), совпадает c φ(m), где
φ(m) - число натуральных чисел, меньших m и взаимно простых с m. Например, при m = 7 П. к. по модулю 7 является число 3. Действительно φ(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 = р ^α, m = 2p^α (где p - простое нечётное число, α - целое ≥1), а для других модулей их нет.
Число П. к. в этих случаях равно φ[φ(m)] (числа, разность которых кратна m, не считаются за различные). И. М. Виноградов в 1926 установил, что в интервале (1, 2^2kp ln p) найдётся П. к. по модулю p, где р - простое нечётное число, k - число различных простых делителей числа p−1. См. также Чисел теория, Индексы в теории чисел.
Лит.: Виноградов И. М., Основы теории чисел, 8 изд., М., 1972; его же, Избр. труды. М., 1952, с. 54-57.

Первообразная    Первообразный корень    Первоуральский новотрубный завод