Следствия предыдущей теории

a. Пусть р - простое нечетное; α ≥ 1, m - одно из чисел p^α, 2p^α, наконец, c = φ(m).

b.

Теорема 1

Пусть (n, c) = d; тогда:

1) Сравнение

xⁿ ? a(mod m); (a, m) = 1 (1)

разрешимо (и тем самым a есть вычет степени n по модулю m) тогда и только тогда, когда ind a кратен d.

2) В приведенной системе вычетов по модулю m число вычетов степени n есть .

Доказательство: Сравнение (1) равносильно такому:

nind x ? ind a(mod c), (2)

которое разрешимо тогда и только тогда, когда ind a кратен d (Теорема 1, п. 2, глава IV).

В случае разрешимости сравнения (2) найдем d несравнимых по модулю c значений для ind x; им отвечает d несравнимых по модулю m значений для x.

Таким образом, верно 1 утверждение.

Среди чисел 0, 1, ..., c - 1, являющихся наименьшими индексами вычетов приведенной системы по модулю m, имеется кратных d. Поэтому верно 2 утверждение.

Пример: Для сравнения

x⁸ ? 23(mod 41) (3)

имеем (8, 40) = 8, причем ind 23 = 36 не делится на 8. Поэтому сравнение (3) неразрешимо.

Пример: Для сравнения

x¹² ? 37(mod 41) (4)

имеем (12, 40) = 4, причем ind 37 = 32 делится на 4. Поэтому сравнение (4) разрешимо, причем это сравнение имеет 4 решения. Указанные решения найдем следующим образом.

Сравнение (4) равносильно таким:

12ind x ? 32(mod 40), ind x ? 6(mod 10).

Отсюда для ind x найдем 4 несравнимых по модулю 40 значения:

ind x = 6, 16, 26, 36,

соответственно чему найдем 4 решения сравнения (4)

x ? 39; 18; 2; 23(mod 41).

Пример: Числа

1, 4, 10, 16, 18, 23, 25, 31, 37, 40, (5)

индексы которых кратны 4, суть все биквадратичные вычеты (или также все вычеты любой степени n = 4, 12, 28, …, где (n, 40) = 4), имеющиеся среди наименьших положительных вычетов по модулю 41.

c. С утверждением Теоремы 1. 1 тесно связано следующая теорема.

Теорема 2

Число a есть вычет степени n по модулю m тогда и только тогда, когда

. (6)

Доказательство: Условие ind a ? 0(mod d) равносильно такому: . Последнее же равносильно условию (6).

Пример: В теореме 1 п. 3 невозможность сравнения равносильна условию, что g - невычет степени q по модулю m. В частности, невозможность сравнения равносильна условию, g - квадратичный невычет по модулю m (Теорема 1, п. 2, глава V).

d.

Теорема 3

1) Показатель δ, которому a принадлежит по модулю m, определяется равенством ; в частности, принадлежность a к числу первообразных корней по модулю m определяется равенством (ind а, c) = 1.

2) В приведенной системе вычетов по модулю m число чисел, принадлежащих показателю δ, есть φ(δ); в частности, число первообразных корней есть φ(c).

Доказательство: δ есть наименьший делитель c с условием a^δ ? 1(mod m). Это условие равносильно

δind a ? 0(mod c),

или

.

Значит, δ - наименьший делитель c, при котором делит ind a, отсюда - наибольший делитель c, делящий ind a, т.е. .

Среди чисел 0, 1, ..., c - 1, являющихся наименьшими индексами вычетов приведенной системы по модулю m, кратными являются числа вида , где y = 0, 1, …, δ - 1. Условие равносильно условию (у, δ) = 1; последнему удовлетворяет φ(δ) значений у. Поэтому верно 2 утверждение.

Пример: В приведенной системе вычетов по модулю 41 числами, принадлежащими показателю 10, являются числа a с условием , т. е. числа

4, 23, 25, 31.

Число этих чисел есть 4 = φ(10).

Пример: В приведенной системе вычетов по модулю 41 первообразными корнями являются числа a с условием (ind a, 40) = 1, т.е. числа

6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35.

Число этих первообразных корней есть 16 = φ(40). 6