Глава 6 первообразные корни и индексы

1 Общие теоремы

1. При (a, m) = 1 существуют положительные γ с условием α^γ ≡ 1(mod т), например (теорема Эйлера) γ = φ(m). Наименьшее из них называется: показатель, которому а принадлежит по модулю т.

Теорема 1

Если а по модулю m принадлежит показателю δ, то числа 1 = а⁰, а¹, …, а^δ-1 по модулю m несравнимы.

Доказательство: Из α^l ≡ α^k(mod т), 0 ≤ k < l < δ следовало бы α^l-k ≡ 1(mod т); 0 < l – k < δ, что противоречит определению δ.

Теорема 2

Если а по модулю m принадлежит показателю δ, то α^γ ≡ α^γ′(mod т) тогда и только тогда, когда γ = γ′(mod δ); в частности (при γ′ = 0), a^γ ≡ 1(mod m) тогда и только тогда, когда γ делится на δ.

Доказательство: Пусть r и r₁ - наименьшие неотрицательные вычеты чисел γ и γ′ по модулю δ; тогда при некоторых q и q₁ имеем γ = δq + r, γ′ = δq₁+ r₁. Отсюда и из a^δ ≡ 1(mod m) следует

,

.

Поэтому α^γ ≡ α^γ′(mod т) тогда и только тогда, когда , т. е. Из Теоремы 1, когда r = r₁.

4. Пусть а по модулю m принадлежит показателю δ. Тогда из Теоремы 2 (γ′ = 0) и из a^φ(m) ≡ 1(mod m) следует, что φ(m) делится на δ. Таким образом, показатели, которым числа принадлежат по модулю т, суть делители φ(m). Наибольший из этих делителей есть само φ(m). Числа, принадлежащие показателю φ(m) (если такие существуют), называются первообразными корнями по модулю т.

2 Первообразные корни по модулям pα и 2рα

1. Пусть p - простое нечетное и α ≥ 0. Докажем существование первообразных корней по модулям p^α и 2p^α.

Теорема 1

Если x по модулю m принадлежит показателю ab, то x^a принадлежит показателю b.

Доказательство: Пусть x^a принадлежит показателю δ. Тогда (x^a)^δ ≡ 1(mod m), откуда x^aδ ≡ 1(mod m); следовательно (Теорема 2, п. 1), aδ делится на ab, т. е. δ делится на b. С другой стороны, x^ab ≡ 1(mod m), откуда (x^a)^b ≡ 1(mod m); следовательно (Теорема, 2 п. 1), bделится на δ. Поэтому δ = b.

Теорема 2

Если x по модулю m принадлежит показателю a, а y - показателю b, причем (a, b) = 1, то xy принадлежит показателю ab.

Доказательство: Пусть xy принадлежит показателю δ. Тогда (xy)^δ ≡ 1(mod m). Отсюда x^bδy^bδ ≡ 1(mod m) и (Теорема 2, п. 1) x^bδ = 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.

Теорема 3

Существуют первообразные корни по модулю p.

Доказательство: Пусть

δ₁, δ₂, ..., δ_r (1)

- все различные показатели, которым по модулю p принадлежат числа 1, 2, ..., (p - 1). Пусть τ - наименьшее общее кратное этих показателей и

- его каноническое разложение. Каждый множитель этого разложения делит по меньшей мере одно число δ_j ряда (1), которое, следовательно, может быть представлено в виде: . Пусть ξ_j - одно из чисел ряда 1, 2, …, p - 1, принадлежащих показателю δ_j. Согласно Теоремы 1 число принадлежит показателю , согласно Теоремы 2 произведение g = η₁, η₂, …, η_k принадлежит показателю . Поэтому (Теорема 1, п. 1) τ – делитель p - 1.

Но поскольку числа (1) делят τ, все 1, 2, ..., p - 1 являются решениями (Теорема 2, п. 1) сравнения x^τ ≡ 1(mod p); поэтому, согласно Теоремы 2, п. 4, главы IV, будем иметь p – 1 < τ. Следовательно, τ = p - 1 и g - первообразный корень.

Теорема 4

Пусть g - первообразный корень по модулю p. Можно указать t с условием, что u, определяемое равенством (g + pt)^p-1 = 1 + up, не делится на p. Соответствующее g +pt будет первообразным корнем по модулю p^α при любом α > 1.

Доказательство: Имеем

g^p-1 = 1 + pT₀, (g + pt)^p-1 = 1 + p(T₀ – g^p-2t + pT) = 1 + pu, (2)

где, одновременно с t, u пробегает полную систему вычетов по модулю р. Поэтому можно указать t с условием, что и не делится на р. При таком t из (2) выводим

,

,

………………………………………….. (3)

,

где все u₂, u₃, …, и_α также не делятся на p. Пусть g + pt принадлежит показателю δ по модулю p^α. Тогда имеем (g + pt)^δ ≡ 1(mod p^α), откуда, в частности, находим g^δ ≡ 1(mod p). Поэтому (Теорема 1, п. 1) δ делится на p - 1 и, будучи (d, п. 1) делителем числа φ(р^α) = p^α-1(р - 1), должно иметь вид δ = p^r-1(p - 1), где r - одно из чисел 1, …, a. А так как равенства (2) и (3) показывают, что сравнение

верно при r = α и неверно при r < α, то (d, п. 1) δ = p^α-1(p - 1) = φ(р^α) и g + pt - первообразный корень по модулю р^α.

Теорема 5

Пусть α ≥ 1 и - первообразный корень по модулю р^α. Нечетное g₀, из чисел g и g + р^α будет первообразным корнем по модулю 2р^α.

Доказательство: φ(р^α) и φ(2р^α) равны между собою (имеем φ(2р^α) = φ(2)φ(р^α) = φ(р^α)); их общее значение обозначим буквою c. Далее легко убедимся, что сравнения и могут выполняться лишь одновременно ( делится на 2). А так как g₀ - первообразный корень по модулю р^α и первое сравнение верно при r = c и неверно при r < c, то тем самым и второе сравнение верно при r = c и неверно при r < c и g₀ - первообразный корень по модулю 2р^α.