5 Следствия предыдущей теории
Пусть р - простое нечетное; α ≥ 1, m - одно из чисел pα, 2pα, наконец, c = φ(m).
Теорема 1
Пусть (n, c) = d; тогда:
Сравнение
xn ≡ a(mod m); (a, m) = 1 (1)
разрешимо (и тем самым a есть вычет степени n по модулю m) тогда и только тогда, когда ind a кратен d. В случае разрешимости сравнение имеет d решений.
В приведенной системе вычетов по модулю 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 утверждение.
Пример: Для сравнения
x8 ≡ 23(mod 41) (3)
имеем (8, 40) = 8, причем ind 23 = 36 не делится на 8. Поэтому сравнение (3) неразрешимо.
Пример: Для сравнения
x12 ≡ 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. Число чисел ряда (5) есть .
С утверждением Теоремы 1. 1 тесно связано следующая теорема.
Теорема 2
Число a есть вычет степени n по модулю m тогда и только тогда, когда
. (6)
Доказательство: Условие ind a ≡ 0(mod d) равносильно такому: . Последнее же равносильно условию (6).
Пример: В теореме 1 п. 3 невозможность сравнения равносильна условию, что g - невычет степени q по модулю m. В частности, невозможность сравнения равносильна условию, g - квадратичный невычет по модулю m (Теорема 1, п. 2, глава V).
Теорема 3
Показатель δ, которому a принадлежит по модулю m, определяется равенством ; в частности, принадлежность a к числу первообразных корней по модулю m определяется равенством (ind а, c) = 1.
В приведенной системе вычетов по модулю m число чисел, принадлежащих показателю δ, есть φ(δ); в частности, число первообразных корней есть φ(c).
Доказательство: δ есть наименьший делитель c с условием aδ ≡ 1(mod m). Это условие равносильно
δind a ≡ 0(mod c),
или
.
Значит, δ - наименьший делитель c, при котором делит ind a, отсюда - наибольший делитель c, делящий ind a, т.е. . Поэтому верно 1 утверждение.
Среди чисел 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).