Докажем, что если — простое, то делится на Заметим, что то есть не является квадратичным вычетом по модулю Тогда из критерия Эйлера, что и требовалось.

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

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