Первообразные корни по простому модулю.
Для описания мультипликативной группы вычетов по простому модулю необходимо изучить числа, имеющие наибольший порядок по этому модулю.
ТЕОРЕМА 5.9. Пусть 
— простое число и d — натуральный делитель числа 
. В приведенной системе вычетов по модулю 
существует точно 
чисел, имеющих порядок 
Доказательство. Пусть В — приведенная система вычетов по модулю 
. Пусть d — некоторый натуральный делитель числа 
Обозначим через 
число элементов из В, порядок которых равен d. Допустим, что существует хотя бы один элемент а В, имеющий порядок 
, т. е. 
Тогда а, 
— различные по модулю 
решения сравнения
и, согласно теореме 4.6, других решений нет. Поэтому все вычеты порядка d должны принадлежать множеству
Согласно предложениям 5.7 и 5.8, число 
имеет порядок d тогда и только тогда, когда 
Отсюда следует, что 
если существует хотя бы один элемент порядка d. Таким образом, 
для любого делителя d числа 
.
Так как каждый вычет имеет некоторый порядок d, являющийся делителем 
то
С другой стороны, согласно теореме 3.11,
поэтому
На основании (2) и (3) заключаем, что 
для любого натурального делителя d числа 
Если вычет а по модулю 
имеет порядок 
, то а называется первообразным корнем по модулю 
.
ТЕОРЕМА. 5.10. Группа вычетов по модулю 
, взаимно простых с модулем, циклично. Число первообразных корней по модулю 
равно 
Эта теорема непосредственно следует из предыдущей теоремы, согласно которой существует 
образующих группы вычетов, взаимно простых с 
.
Если g есть первообразный корень по модулю 
, то 
степеней
несравнимы по модулю 
. Следовательно, верно следующее предложение.
ПРЕДЛОЖЕНИЕ 5.11. Если g есть первообразный корень по модулю 
, то 
степеней 
представляют собой приведенную систему вычетов по модулю 
.
Первообразные корни существуют не для всякого модуля 
, а лишь для 
(
— нечетное простое число).
Пример. Пусть 
Найдем первообразные корни по этому модулю.
Число 
имеет 6 натуральных делителей: 1, 2, 3, 4, 6, 12;
Числа 2, 6, 7, 11 являются первообразными корнями по модулю 13. Число 12 имеет порядок 2; число 3 — порядок 3; числа 5,8 — порядок 4; числа 4,10 — порядок 6, число 1 — порядок 1.
