§ 3. Разыскание первообразных корней по модулям

Первообразные корни по модулям где — простое нечетное , можно разыскивать, пользуясь следующей общей теоремой:

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

Действительно, если -первообразный корень, то тем самым оно принадлежит показателю с и, следовательно, ни одному из сравнений (1) удовлетворять не может.

Обратно, допустим, что g не удовлетворяет ни одному из сравнений (1). Если бы показатель , которому принадлежит g, оказался меньше с, то, обозначая буквою один из простых делителей , мы имели бы , что противоречит нашему допущению. Значит, и - первообразный корень.

Пример 1. Пусть Имеем Следовательно, для того чтобы число не делящееся на 41, было первообразным корнем по модулю 41, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений

Но, испытывая числа находим (по модулю ее

Отсюда видим, что числа — не первообразные корни, так как каждое из них удовлетворяет, по крайней мере, одному из сравнений (2). Число - первообразный корень, так как оно не удовлетворяет ни одному из сравнений (2).

Пример 2. Пусть Первообразный корень и здесь можно было бы найти, пользуясь общей теоремой. Но мы найдем его проще, применяя теорему , § 2. Зная уже (пример 1), что первообразный корень по модулю 41 есть 6, находим

Чтобы и не делилось на 41, достаточно взять Поэтому в качестве первообразного корня по модулю 1681 можно взять число

Пример 3. Пустьт Первообразный корень и здесь можно было бы найти, пользуясь общей теоремой. Но мы найдем его проще, применяя теорему f, § 2. Зная уже (пример 2), что первообразный корень по модулю 1681 есть 6, в качестве первообразного корня по модулю 3362 можно взять нечетное из чисел т. е. число 1687.