Квадратичные вычеты
Если p - простое число, и a больше 0, но меньше p, то a представляет собой квадратичный вычет по модулю p, если
x2 ? a (mod p), для некоторых x
Не все значения a соответствуют этому требованию. Чтобы a было квадратичным вычетом по n, оно должно быть квадратичным вычетом по модулю всех простых сомножителей n. Например, если p = 7, квадратичными вычетами являются числа 1, 2, и 4:
12 = 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)
Заметьте, что каждый квадратичный вычет дважды появляется в этом списке. Значений x, удовлетворяющих любому из следующих уравнений, не существует:
x2 ? 3 (mod 7)
x2 ? 5 (mod 7)
x2 ? 6 (mod 7)
Эти числа - 3, 5 и 6 - не являются квадратичными вычетами по модулю 7.
Хотя я этого и не делаю, несложно доказать, что когда p нечетно, существует в точности (p - 1)/2 квадратичных вычетов по модулю p, и столько же чисел, не являющихся квадратичными вычетами по модулю p. Кроме того, если a - это квадратичный вычет по модулю p, то у a в точности два квадратных корня, один между 0 и (p-1)/2, а второй - между (p - 1)/2 и (p - 1). Один из этих квадратных корней одновременно является квадратичным остатком по модулю p, он называется главным квадратным корнем.
Если n является произведением двух простых чисел, p и q, то существует ровно (p - l)(q - 1)/4 квадратичных вычетов по модулю n. Квадратичный вычет по модулю n является совершенным квадратом по модулю n, потому что для того, чтобы быть квадратом по модулю n, вычет должен быть квадратом по модулю p и квадратом по модулю q. Например, существует одиннадцать квадратичных остатков mod 35: 1, 4, 9, 11, 15, 16, 21, 25, 29 и 30. У каждого квадратичного вычета ровно четыре квадратных корня.