Открыть главное меню

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

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

и

при

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

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

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

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

 ,

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

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

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

 

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

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

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

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

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

ИсторияПравить

Первообразные корни для простых модулей   были введены Эйлером, но существование первообразных корней для любых простых модулей   было доказано лишь Гауссом в «Арифметических исследованиях» (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

См. такжеПравить

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

ЛитератураПравить

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