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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

и

при

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

Чтобы не проверять все от до , достаточно проверить три условия:

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

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

[править | править код]

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

,

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

Количество

[править | править код]

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

Индекс числа по модулю

[править | править код]

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

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

Минимальный корень

[править | править код]

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

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

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

Примечания

[править | править код]
  1. Primitive Root - Competitive Programming Algorithms. cp-algorithms.com. Дата обращения: 27 октября 2020. Архивировано 24 октября 2020 года.
  2. Bach, Eric; Shallit, Jeffrey. Algorithmic Number Theory (Vol I: Efficient Algorithms). — Cambridge: The MIT Press, 1996. — P. 254. — ISBN 978-0-262-02405-1.

Литература

[править | править код]
  • Виноградов И. М. Глава 6. Первообразные корни и индексы // Основы теории чисел. — 1952. — 182 с.
  • Нестеренко Ю. В. Глава 7. Первообразные корни и индексы // Теория чисел. — М.: «Академия», 2008. — 464 с.