Если/; - простое число, и а больше 0, но меньше р, то а представляет собой квадратичный вычет по модулю р, если
х2 = a (mod/;), для некоторых х
Не все значения а соответствуют этому требованию. Чтобы а было квадратичным вычетом по п, оно должно быть квадратичным вычетом по модулю всех простых сомножителей п. Например, если р = 1, квадратичными вычетами являются числа 1, 2, и 4:
I2 = 1 = 1 (mod 7)
22 = 4 = 4 (mod 7)
32 = 9 = 2 (mod 7)
42 = 16=2 (mod 7)
52 = 25=4 (mod 7)
62 = 36 = 1 (mod 7)
Заметьте, что каждый квадратичный вычет дважды появляется в этом списке. Значений х, удовлетворяющих любому из следующих уравнений, не существует:
х2 = 3 (mod 7)
х2 = 5 (mod 7)
х2 = 6 (mod 7)
Эти числа - 3, 5 и 6 - не являются квадратичными вычетами по модулю 7.
Хотя я этого и не делаю, несложно доказать, что когда р нечетно, существует в точности (р - 1)12 квадратичных вычетов по модулю р, и столько же чисел, не являющихся квадратичными вычетами по модулю р. Кроме того, если а - это квадратичный вычет по модулю р, то у а в точности два квадратных корня, один между 0 и (р-Х)12, а второй - между (р - 1)/2 и (р - 1). Один из этих квадратных корней одновременно является квадрата ч-ным остатком по модулю р, он называется главным квадратным корнем
Если п является произведением двух простых чисел, р и q, то существует ровно (р - ){q - l)/4 квадратичных вычетов по модулю п. Квадратичный вычет по модулю п является совершенным квадратом по модулю п, потому что для того, чтобы быть квадратом по модулю и, вычет должен быть квадратом по модулю р и квадратом по модулю q. Например, существует одиннадцать квадратичных остатков mod 35: 1, 4, 9, И, 15, 16, 21, 25, 29 и 30. У каждого квадратичного вычета ровно четыре квадратных корня.