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

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

ТЕОРЕМА 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.