Первообразные корни по модулям pα и 2рα
a. Пусть p - простое нечетное и α ≥ 0. Докажем существование первообразных корней по модулям pα и 2pα.
b.
Теорема 1
Если x по модулю m принадлежит показателю ab, то xa принадлежит показателю b.
Доказательство: Пусть xa принадлежит показателю δ. Тогда (xa)δ ? 1(mod m), откуда xaδ ? 1(mod m); следовательно (Теорема 2, п. 1), aδ делится на ab, т. е. δ делится на b. С другой стороны, xab ? 1(mod m), откуда (xa)b ? 1(mod m); следовательно (Теорема, 2 п. 1), bделится на δ. Поэтому δ = b.
c.
Теорема 2
Если x по модулю m принадлежит показателю a, а y - показателю b, причем (a, b) = 1, то xy принадлежит показателю ab.
Доказательство: Пусть xy принадлежит показателю δ. Тогда (xy)δ ? 1(mod m). Отсюда xbδybδ ? 1(mod m) и (Теорема 2, п. 1) xbδ = 1 (mod m). Поэтому (Теорема 2, п. 1) bδ делится на a, и ввиду (b, a) = 1δ делится на a. Так же находим, что δ делится на b. Делясь же на a и на b, ввиду (a, b) = 1δ делится и на ab. С другой стороны, из (xy)ab ? 1(mod m) следует (Теорема 2, п. 1), что ab делится на δ. Поэтому δ = ab.
d.
Теорема 3
Существуют первообразные корни по модулю p.
Доказательство: Пусть
δ1, δ2, ..., δr (1)
- все различные показатели, которым по модулю p принадлежат числа 1, 2, ..., (p - 1). Пусть τ - наименьшее общее кратное этих показателей и
- его каноническое разложение. Каждый множитель 
этого разложения делит по меньшей мере одно число δj ряда (1), которое, следовательно, может быть представлено в виде: 
.
принадлежит показателю , согласно Теоремы 2 произведение g = η1, η2, …, ηk принадлежит показателю 
. Поэтому (Теорема 1, п. 1) τ – делитель p - 1. Но поскольку числа (1) делят τ, все 1, 2, ..., p - 1 являются решениями (Теорема 2, п. 1) сравнения xτ ? 1(mod p); поэтому, согласно Теоремы 2, п. 4, главы IV, будем иметь p – 1 < τ. Следовательно, τ = p - 1 и g - первообразный корень.
e.
Теорема 4
Пусть g - первообразный корень по модулю p. Можно указать t с условием, что u, определяемое равенством (g + pt)p-1 = 1 + up, не делится на p. Соответствующее g +pt будет первообразным корнем по модулю pα при любом α > 1.
Доказательство: Имеем
gp-1 = 1 + pT0, (g + pt)p-1 = 1 + p(T0 – gp-2t + pT) = 1 + pu, (2)
где, одновременно с t, u пробегает полную систему вычетов по модулю р. Поэтому можно указать t с условием, что и не делится на р. При таком t из (2) выводим
,
,
………………………………………….. (3)
,
где все u2, u3, …, иα также не делятся на p. Пусть g + pt принадлежит показателю δ по модулю pα. Тогда имеем (g + pt)δ ? 1(mod pα), откуда, в частности, находим gδ ? 1(mod p).
Поэтому (Теорема 1, п. 1) δ делится на p - 1 и, будучи (d, п. 1) делителем числа φ(рα) = pα-1(р - 1), должно иметь вид δ = pr-1(p - 1), где r - одно из чисел 1, …, a. А так как равенства (2) и (3) показывают, что сравнение
верно при r = α и неверно при r < α, то (d, п. 1) δ = pα-1(p - 1) = φ(рα) и g + pt - первообразный корень по модулю рα.
f.
Теорема 5
Пусть α ≥ 1 и - первообразный корень по модулю рα. Нечетное g0, из чисел g и g + рα будет первообразным корнем по модулю 2рα.
Доказательство: φ(рα) и φ(2рα) равны между собою (имеем φ(2рα) = φ(2)φ(рα) = φ(рα)); их общее значение обозначим буквою c. Далее легко убедимся, что сравнения 
и 
могут выполняться лишь одновременно (
делится на 2). А так как g0 - первообразный корень по модулю рα и первое сравнение верно при r = c и неверно при r < c, то тем самым и второе сравнение верно при r = c и неверно при r < c и g0 - первообразный корень по модулю 2рα. 3