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

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

Чтобы не проверять все от до , достаточно проверить три условия: Является ли числом взаимно простым с , и если нет, то это не первообразный корень. Так как  — всегда чётное число для всех , то имеет как минимум один простой делитель — простое число , следовательно, для того, чтобы отсеять значительное количество не-корней, достаточно проверить для числа, подходящего на первообразный корень по модулю . Если результат +1  m, то g — не корень, в ином случае результат −1  m, когда g — это возможно первообразный корень. Далее следует убедиться, что для всех , где  — простой делитель числа , полученный в результате его факторизации.

Свойства

Существование Первообразные корни существуют только по модулям вида , где ― простое число, ― натуральное. Только в этих случаях мультипликативная группа кольца вычетов по модулю m является циклической группой порядка .

Количество Если по модулю существует первообразный корень , то всего существует различных первообразных корней по модулю m, причём все они имеют вид , где и .

Индекс числа по модулю Для первообразного корня его степени несравнимы между собой по модулю m и образуют приведенную систему вычетов по модулю m. Поэтому для каждого числа , взаимно простого с , найдется показатель , такой, что

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

Минимальный корень Исследования Виноградова показали, что существует такая константа , что для всякого простого существует первообразный корень . Другими словами, для простых модулей минимальный первообразный корень имеет порядок . Математик из Университета Торонто показал, что если «Обобщённая гипотеза Римана» верна, то первообразный корень есть среди первых чисел натурального ряда.

История Первообразные корни для простых модулей были введены Эйлером, но существование первообразных корней для любых простых модулей было доказано лишь Гауссом в «Арифметических исследованиях» (1801 год).

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

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

Категория:Модульная арифметика