Сравнения высших степеней (стр. 4 )

Следствие 1. для всех .

2. .

3. Если , то

.

Теорема 8. Пусть - простое число, - нечетное, то имеет место

. (18)

Доказательство. Рассмотрим сравнения:

(19)

где - абсолютно наименьший вычет , - его модуль, так что .

Числа образуют ПрСВ по модулю ; их абсолютно наименьшие вычеты суть . Положительные из последних, то есть , должны совпадать с числами . Перемножая теперь сравнения (19) и сокращая на , получим

. (20)

Далее находим

,

что будет четным или нечетным, в зависимости от того, будет ли наименьший неотрицательный вычет числа меньше или больше , то есть будет ли или . Отсюда, очевидно, , и потому из (20) находим

.

Предполагая нечетным, преобразуем последнее равенство. Имеем ( - нечетное)

.

Откуда и следует утверждение теоремы.

Из этой теоремы как следствие вытекает свойство 6.

Доказательство свойства 7. Так как будет нечетным лишь в случае, когда оба числа и будут вида , и четным, если хоть одно из этих чисел будет вида , то указанное свойство можно сформулировать так:

Если оба числа и будут вида , то , если хоть одно из этих чисел будет вида , то .

Для доказательства заметим, что ввиду свойства 6 формула (18) принимает вид

. (21)

Полагая теперь , рассмотрим пар чисел, получаемых, когда в выражениях числа и независимо друг от друга пробегают системы значений . Никогда не может быть , потому что из этого равенства следовало бы, что кратно , что в виду (так как ) невозможно. Поэтому мы можем положить , где - число пар с , и - число пар с . Очевидно, есть также число пар с ( этому не противоречит неравенство , так как из следует ). Поэтому

.

Аналогично убеждаемся, что

.

Но тогда равенство (21) дает нам

поэтому

,

откуда и следует свойство 7.

Полезным обобщением символа Лежандра является символ Якоби. Пусть - нечетное, большее единицы, и - разложение его на простые множители ( среди них могут быть и равные). Пусть, далее, . Тогда символ Якоби определяется равенством

.

Известные свойства символа Лежандра дают возможность установить аналогичные свойства и для символа Якоби.

Пример 1. Решить сравнение

(1)

Решение. Нуль удовлетворяет сравнению, т. е. есть одно из решений. Остальные решения (если они существуют) взаимно просты с модулем, поэтому по теореме Ферма они удовлетворяют сравнению: (2)

Следовательно, для отыскания остальных решений сравнения (1) и (2) решаем совместно, т. е. подставим (2) в (1).

Получаем или

, , отсюда находим , .

Ответ: , , .

Пример 2. С помощью критерия Эйлера среди чисел 3, 5, 7 и 9 найти квадратичные вычеты по модулю 13.

Решение. Замечаем, что каждое из данных чисел взаимно просто с модулем, поэтому критерий Эйлера применим. Имеем