21. Квадратичные вычеты

Если простое число, то квадратичным вычетом для числа называется каждое целое число для которого существует целое число такое, что число делится на Другими словами, целое число называется квадратичным вычетом для если существует квадрат целого числа, дающий при делении на такой же остаток, как и . Целые числа, не являющиеся квадратичными вычетами для называются квадратичными невычетами для

Для числа 2, очевидно, каждое целое число является квадратичным вычетом, так как если нечетное число, то если же — четное число, то

Пусть теперь простое нечетное число. Выясним, сколько в последовательности имеется квадратичных вычетов для

Обозначим через остаток от деления числа на Для целых числа будут, очевидно, всеми квадратичными вычетами для (так как ). Значит, в частности, квадратичным вычетом для будет каждое из чисел

(число натуральное, так как мы предположили, что является простым нечетным числом). Числа последовательности (1), очевидно, отличны от нуля (так как ни одно из чисел , не делится на следовательно, являются числами последовательности Покажем, что они все различные. Предположим, что для некоторых натуральных где мы имеем Это означает,

что числа дают при делении на одинаковые остатки и, следовательно, число делится на Но, в силу неравенства для числа являются натуральными, причем оба они меньше как Таким образом, число должно быть делителем произведения двух натуральных чисел, меньших что невозможно.

Итак, мы доказали, что для

Следовательно, среди чисел последовательности мы имеем по крайней мере квадратичных вычетов для Докажем теперь, что в этой последовательности никаких других квадратичных вычетов для кроме чисел (1), не содержится. Предположим для доказательства, что есть число из последовательности являющееся квадратичным вычетом для Тогда существует целое число а такое, что Отсюда следует, что т. е.

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

Теорема 20. Если есть простое нечетное число, то в последовательности мы имеем точно квадратичных вычетов для (и, очевидно, столько

же квадратичных невычетов для так как

Из доказательства теоремы непосредственно следует, что для получения всех чисел последовательности , являющихся квадратичными вычетами для простого нечетного числа достаточно определить остатки от деления на чисел

Таким путем мы найдем, например, что всеми квадратичными положительными вычетами для 13, меньшими 13, являются числа 1, 4, 9, 3, 12, 10 и, следовательно, невычетами для 13 (среди чисел ) будут числа 2, 5, 6, 7, 8 и 11.

Как мы уже доказали выше, число из последовательности является квадратичным вычетом для простого нечетного тогда и только тогда, когда число делится на Таким образом, если число а из указанной последовательности является квадратичным невычетом для то число не делится на Но, согласно теореме Ферма, число делится на а так как причем первый сомножитель правой части не делится на то должен делиться второй сомножитель, Следовательно, число а из последовательности является квадратичным вычетом для простого нечетного числа если невычетом, если .

Заметим, что для составных чисел дело обстоит иначе. Например, для среди натуральных чисел < 15 только пять (следовательно, меньше чем являются квадратичными вычетами для числа 15, именно числа и 10, а остальные 9 чисел являются квадратичными невычетами для числа 15. Среди натуральных чисел только два, именно числа 1 и 4 являются квадратичными вычетами для числа 8.

Заметим еще, что А. Вале Винс нашел теорему, согласно которой нечетное числа является простым тогда и только тогда, когда ни одно из чисел при делении на не дает в остатке ни 0, ни 1.

Для простых чисел изучены также вычеты кубические, биквадратичные и высших степеней. Можно доказать, что для каждого нечетного числа существует бесконечно много простых чисел для которых каждое целое число является вычетом степени. Так, например, для чисел 5 и 11 каждое целое число является кубическим вычетом, для чисел же 5 и 7 каждое целое число является вычетом 5-й степени.

Доказательство того, что каждое целое число является вычетом 5-й степени для простого числа 7, вытекает непосредственно из следующих формул, которые легко можно проверить:

Можно доказать, что для простых чисел 5 и 17 каждое целое число является вычетом любой нечетной степени. Можно также доказать, что для того чтобы для простого числа каждое целое число было вычетом любой нечетной степени, необходимо и достаточно, чтобы простое число было вида т. е. чтобы оно было простым числом Ферма.