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

(a) По индукции несложно доказать, что для всех натуральных Тогда понятно, что Заметим, что то есть не является квадратичным вычетом по модулю . Тогда из критерия Эйлера, что и требовалось.

(b) Пусть — составное число, и выполнена делимость. Отметим, что и взаимно просты (), поэтому определено понятие показателя по модулю Рассмотрим показатель числа по модулю Из получаем откуда делится на то есть является степенью двойки. С другой стороны из первого сравнения получаем откуда

Теперь воспользуемся теоремой Эйлера: согласно ей, Поскольку  – составное, то Получается, что но причем  – натуральное число. Это невозможно, поэтому мы достигли противоречия.