§ 2. Первообразные корни по модулям
а. Пусть 
— простое нечетное 
Докажем существование первообразных корней по модулям 
b. Если 
по модулю 
принадлежит показателю 
то 
принадлежит показателю b.
Действительно, пусть 
принадлежит показателю 
. Тогда 
, откуда 
; следовательно 
делится на 
т. е. 
делится на b.
С другой стороны, 
, откуда 
следовательно 
§ 1), b делится на 8. Поэтому 
c. Если 
по модулю 
принадлежит показателю а, а у — показателю b, причем 
то 
принадлежит показателю 
Действительно, пусть 
принадлежит показателю 
. Тогда 
Отсюда 
. Поэтому (с, § 1) 66 делится на а, и ввиду 
делится на а. Так же находим, что 
делится на b. Делясь же на а и на b, ввиду 
делится и на 
. С другой стороны, из 
следует (с, § 1), что 
делится на 
. Поэтому 
d. Существуют первообразные корни по модулю 
.
Действительно, пусть
— все различные показатели, которым по модулю 
принадлежат числа 
. Пусть 
— общее наименьшее кратное этих показателей и
— его каноническое разложение. Каждый множитель q этого разложения делит по меньшей мере одно число 
ряда (1), которое, следовательно, может быть представлено в виде: 
Пусть 
— одно из чисел ряда 
принадлежащих показателю 
Согласно b число 
принадлежит показателю q, согласно с произведение 
принадлежит показателю 
. Поэтому (d, § 1) 
— делитель 
Но поскольку числа (1) делят 
, все 
являются решениями (с, § 1) сравнения 
; поэтому, согласно с, § 4, гл. IV, будем иметь 
. Следовательно, 
— первообразный корень.
e. Пусть g — первообразный корень по модулю 
. Можно указать t с условием, что и, определяемое равенством 
не делится на 
. Соответствующее 
будет первообразным корнем по модулю 
при любом а 
Действительно, имеем
где, одновременно с 
и пробегает полную систему вычетов по модулю 
. Поэтому можно указать t с условием, что и не делится на 
. При таком t из (2) выводим
где все 
также не делятся на 
. Пусть 
принадлежит показателю 
по модулю 
Тогда имеем 
откуда, в частности, находим 
. Поэтому (с, § 1) 
делится на 
и, будучи (d, § 1) делителем числа 
, должно иметь вид 
, где 
— одно из чисел 
. А так как равенства (2) и (3) показывают, что сравнение
верно при 
и неверно при 
, то 
— первообразный корень по модулю 
f. Пусть 
— первообразный корень по модулю 
. Нечетное 
из чисел g и 
будет первообразным корнем по модулю 
.
Действительно, 
равны между собою (имеем 
) 
их общее значение обозначим буквою с. Далее легко убедимся, что сравнения 
могут выполняться лишь одновременно 
делится на 2).
- первообразный корень по модулю 
и первое сравнение верно при 
и неверно при 
то тем самым и второе сравнение верно при 
и неверно при 
и 
- первообразный корень по модулю 