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

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

Первообразный корень по модулю 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 с.