Разыскание первообразных корней по модулям рα в 2рα
Первообразные корни по модулям рα и 2рα где p - простое нечетное и α > 1, можно разыскивать, пользуясь следующей общей теоремой:
Теорема 1
Пусть c = φ(m) и q1, q2, …, qk - различные простые делители числа c.
Для того чтобы число g, взаимно простое с m, было первообразным корнем по модулю m необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений
. (1)
Доказательство: Если g - первообразный корень, то тем самым оно принадлежит показателю c и, следовательно, ни одному из сравнений (1) удовлетворять не может.
Обратно, допустим, что g не удовлетворяет ни одному из сравнении (1). Если бы показатель δ, которому принадлежит g, оказался меньше c, то, обозначая буквою q один из простых делителей 
, мы имели бы 
, 
, 
, что противоречит нашему допущению. Значит, δ = c и g - первообразный корень.
Пример: Пусть m = 41. Имеем φ(41) = 40 = 23∙5, 
, 
. Следовательно, для того чтобы число g, не делящееся на 41, было первообразным корнем по модулю 41, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений
. (2)
Но, испытывая числа 2, 3, 4, ..., находим (по модулю 41)
28 ? 10, 38 ? 1, 48 ? 18, 58 ? 18, 68 ? 10,
220 ? 1, 420 ? 1, 520 ? 1, 620 ? 40.
Отсюда видим, что числа 2, 3, 4, 5 - не первообразные корни, так как каждое из них удовлетворяет, по крайней мере, одному из сравнений (2). Число 6 - первообразный корень, так как оно не удовлетворяет ни одному из сравнений (2).
Пример: Пусть m = 1681 = 412. Первообразный корень и здесь можно было бы найти, пользуясь общей теоремой. Но мы найдем его проще, применяя теорему 4, п. 2. Зная уже (предыдущий пример), что первообразный корень по модулю 41 есть 6, находим
640 = 1 + 41(3 + 41l), (6 + 41t)40 = 1 + 41(3 + 41l – 639t + 41T) = 1 + 41u.
Чтобы u не делилось на 41, достаточно взять t = 0. Поэтому в качестве первообразного корня по модулю 1681 можно взять число 6 + 41∙0 = 6.
Пример: Пусть m = 3362 = 2∙1681. Первообразный корень и здесь можно было бы найти, пользуясь общей теоремой. Но мы найдем его проще, применяя теорему 5, п. 2. Зная уже (предыдущий пример), что первообразный корень по модулю 1681 есть 6, в качестве первообразного корня по модулю 3362 можно взять нечетное из чисел 6, 6 + 1681, т. е. число 1687. 4