Пусть $p$ - простое нечетное число. Тогда число $a$, такое, что $GCD(a, p)=1$, называется вычетом степени $n$, если $\exists(x):x^{n}\equiv a ~mod~{p}.$
В обратном случае число $a$ называется невычетом степени $n$. При $n=2$ вычет (невычет) $a$ называется квадратичным, при $n=3$ - кубическим, а при $n=4$ - биквадратичным. При $n=2$ слово квадратичный опускают и называют $a$ просто вычетом (невычетом).
Рассмотрим группу $\mathbb{Z}_{p}^{*}=\{1, 2, ... , p-1\}$ с заданной операцией умножения по модулю $p$. Элементы, являющиеся квадратами какого-то числа в $\mathbb{Z}_{p}^{*}$, - вычеты.
Примеры:
Пусть $p=7$, $\mathbb{Z}_{p}^{*}=\{1, 2, 3, 4, 5, 6\}$.
$1^{2}=1 ~mod~{7},$
$2^{2}=4 ~mod~{7},$
$3^{2}=2 ~mod~{7},$
$4^{2}=2 ~mod~{7},$
$5^{2}=4 ~mod~{7},$
$6^{2}=1 \pmod{7}.$
Числа $1,2,4$ будут являться квадратичными вычетами, а числа $3,5,6$ - квадратичными невычетами.
Утверждение 1. В $\mathbb{Z}_{p}^{*}$ существует ровно $\frac{p-1}{2}$ квадратичных вычетов, сравнимых с числами: $1^2, 2^2,...,\frac{p-1}{2}^2$.
Доказательство.
Сначала покажем, что приведенный список чисел содержит квадраты всех элементов из $\mathbb{Z}_{p}^{*}$.
Это становится очевидно, если представить $\mathbb{Z}_{p}^{*}$ как $\{-\frac{p-1}{2},..., -2, -1, 1, 2, ...,\frac{p-1}{2}\}$.
Теперь пусть $\exists i, j\in \mathbb{Z}_{p}^{*}: i^2\equiv j^2 ~ mod ~ {p}, 0<i<j\leq\frac{p-1}{2}$. Тогда сравнению $x^2\equiv i^2 ~mod~{p}$ удовлетворяло бы 4 корня: $x=\pm i, \pm j$, чего быть не может, а значит все числа из списка $1^2, 2^2,...,\frac{p-1}{2}^2$ различны по модулю $p$.
Таким образом, приведенный список $1^2, 2^2,...,\frac{p-1}{2}^2$ состоит из $\frac{p-1}{2}$ различных по модулю $p$ чисел, представляющих все вычеты в группе $\mathbb{Z}_{p}^{*}$.
Утверждение 2. Если $\mathbb{Z}_{p}^{*}=\{1, \theta, \theta^{2},..., \theta^{p-2}\}$, где $\theta$ - порождающий элемент, то справедливо следующее: $a=\theta^{j}$ - квадратичный вычет $\Leftrightarrow$ $j$ - четное.
Пусть $a=\theta^{j}$ - квадратичный вычет. Тогда $\exists x: x^{2}\equiv a ~ mod ~{p}$.
Так как $\theta$ - порождающий элемент, значит $\exists i: x=\theta^{i}$, откуда следует, что $\theta^{2i}=\theta^{j}$, то есть \textit{j} - четное.
В обратную сторону, пусть $j$ - четное. Тогда $j=2i$ для некоторого $i$, то есть $a=\theta^{2i}$. Это значит, что $\exists x=\theta^{i}: x^{2}\equiv a ~ mod ~ {p}$, то есть $a$ - квадратичный вычет.
