§ 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).

А так как - первообразный корень по модулю и первое сравнение верно при и неверно при то тем самым и второе сравнение верно при и неверно при и - первообразный корень по модулю