Что значит "первообразный корень"

по модулю m, такое число g, что положительное наименьшее число k, для которого разность gk ≈ 1 делится на m (gk сравнимо с 1 по модулю m), совпадает c j(m), где j(m) ≈ число натуральных чисел, меньших m и взаимно простых с m. Например, при m =7 П. к. по модулю 7 является число 3. Действительно j(7) = 6; числа 31 ≈ 1 = 2, 32 ≈ 1 = 8, 33 ≈ 1 = 26, 34 ≈ 1 = 80, 35 ≈ 1 = 242 не делятся на 7, лишь 36 ≈ 1 = 728 делится на 7. П. к. существуют, когда m = 2, m = 4, m = рa, m = 2pa (где р ≈ простое нечётное число, a ≈ целое ³1), а для других модулей их нет. Число П. к. в этих случаях равно j[j(m)] (числа, разность которых кратна m, не считаются за различные). И. М. Виноградов в 1926 установил, что в интервале (1, 22klnp) найдётся П. к. по модулю р, где р ≈ простое нечётное число, k ≈ число различных простых делителей числа р ≈ 1. См. также Чисел теория , Индексы в теории чисел.

Лит.: Виноградов И. М., Основы теории чисел, 8 изд., М., 1972; его же, Избр. труды. М., 1952, с. 54≈57.

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

• Первообразный корень — общеалгебраическое обобщение теоретико-числового понятия.
• Первообразный корень .

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

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

и

$g^{\ell} \not\equiv 1 \pmod m$ при 1 ≤ ℓ < φ(m), 

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