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

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

b.

Теорема 1

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

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

c.

Теорема 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₁.

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