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

В тривиальном случае имеем решения и и наоборот.

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

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