Квадратичные вычеты по простому модулю.

В этом пункте будем рассматривать сравнения вида x²≡a(mod p), p>2 – простое число.

Теорема 1.

Если а – квадратичный вычет по простому модулю р, то сравнение x²≡a(modp) имеет ровно 2 решения.

Доказательство:

Если а – квадратичный вычет по модулю p, то найдется хотя бы одно решение исходного сравнения: x≡x₁(mod p).

Но, поскольку (—x₁)²=x₁², то решением также является x≡—x₁(mod p), причем x₁ —x₁(mod p), т.к. р – нечетное число.

Более двух решений данное сравнение иметь не может, так как является сравнением второй степени (§4, п.3, Теорема 2).

□

Теорема (о числе квадратичных вычетов)

Приведенная система вычетов по модулю p состоит из квадратичных вычетов и квадратичных невычетов.

Доказательство:

Среди вычетов приведенной системы по модулю p квадратичными вычетами являются только те, что сравнимы с квадратами чисел

…, –2, –1, 1, 2,…, , т.е. с числами 1, 2², 3²,…,

При этом квадраты не сравнимы между собой по модулю p, т.к. иначе из того, что k² ≡ l² (mod p), 0 < k < l следовало бы, что сравнению x²≡l²(mod p) удовлетворяют 4 числа: –l, l,–k, k, что противоречит Теореме 1.

Таким образом, квадратичных вычетов в приведенной системе по модулю p ровно штук. Остальные элементы приведенной системы являются квадратичными невычетами. А поскольку всего в приведенной системе по модулю p содержится p—1 элементов, то квадратичными невычетами являются также элементов.

□

Множество квадратных вычетов по модулю p обозначается Q(p), множество квадратичных невычетов – .