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

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

и

при

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

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

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

СвойстваПравить

СуществованиеПравить

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

 ,

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

Индекс числа по модулюПравить

Для первообразного корня g его степени g0=1, g, …, gφ(m) − 1 несравнимы между собой по модулю m и образуют приведенную систему вычетов по модулю m. Поэтому для каждого числа a, взаимно простого с m, найдется показатель ℓ, 0 ⩽ ℓ ⩽ φ(m) − 1, такой, что

 

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

КоличествоПравить

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

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

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

СсылкиПравить