- Первообразный корень (теория чисел)
-
Первообразный корень по модулю m ― целое число g такое, что
и
- при
где ― функция Эйлера. Другими словами, первообразный корень — это образующий элемент мультипликативной группы кольца вычетов по модулю m.
Содержание
Свойства
Существование
Первообразные корни существуют только по модулям m вида
- m = 2, 4, pa, 2pa,
где p > 2 ― простое число. Только в этих случаях мультипликативная группа кольца вычетов по модулю m является циклической группой порядка φ(m).
Индекс числа по модулю
Для первообразного корня g его степени g0=1, g, …, gφ(m)-1 несравнимы между собой по модулю m и образуют приведенную систему вычетов по модулю m. Поэтому для каждого числа a, взаимно простого с m, найдется показатель ℓ, 0 ⩽ ℓ ⩽ φ(m)-1, такой, что
Такое число ℓ называется индексом числа a по основанию g.
Количество
Если по модулю m существует первообразный корень g, то всего существует φ(φ(m)) различных первообразных корней по модулю m, причём все их можно получить как gk, где 1 ⩽ k ⩽ φ(m)-1 и k взаимно просто с φ(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 См. также
Ссылки
Категория:- Теория чисел
Wikimedia Foundation. 2010.