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

(a) Пусть — квадратичный невычет по модулю — множество всех квадратичных вычетов по данному модулю. В силу мултипликативности символа Лежандра, для любого имеет место равенство

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

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

Пусть тогда — обратный остаток существует, поскольку каждое из чисел не кратно Составим систему линейных уравнений, решив ее, получим решения

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

Заметим, что каждому решению исходного уравнения соответствует ровно 4 решения (возможно совпадающих) уравнения важного сравнения —

В случае, если то все четыре решения являются различными. Если то что невозможно, поскольку является квадратичным вычетом по данному модулю. Если то и имеет место только при когда является невычетом по модулю

Наконец, мы показали, что в случае среди пар решений важного сравнения все различны, следовательно, решений исходного уравнения ровно в 4 раза меньше и равно

Если то количество пар уменьшится на то есть станет А значит количество решений исходного уравнения равно

(b) Заметим, что общее количество пар в которых является квадратичным невычетом по модулю совпадает с количеством всевозможных квадратичных невычетов. Таким образом, в случае имеем

а в случае