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

Линейное сравнение по простому модулю имеет решение всегда, когда коэффициент при $x\not\equiv 0 \pmod p$.

Рассмотрим сравнение $x^2 \equiv 5 \pmod7$.

$\begin{array}{c|ccccccc} x & 0& 1& 2& 3& 4& 5& 6\\ \hline x^2 & 0& 1& 4& 2& 2& 4& 1 \end{array}$

Определение. Число $a\not\equiv 0 \pmod p$ называется квадратичным вычетом по модулю $p$, если сравнение $x^2\equiv a\pmod p$ имеет решение.

Определение. Число $a\not\equiv 0\pmod p$ называется невычетом, если сравнение $x^2\equiv a\pmod p$ не имеет решения.

Далее везде будем считать, что $p\in \mathbb {P}\backslash \{ 2\}$.

Утверждение. Вычетов по mod  $p$ ровно $\frac{p-1}{2}$, невычетов столько же.

$\blacktriangle$
$1^2, 2^2, \ldots , \left(\frac{p-1}{2}\right)^2$ — вычеты. Они все различны, т.к. если $k^2 = l^2 \pmod p$, $k, l \in [0, \frac{p-1}{2}]$, то $x^2 \equiv k^2\pmod p$ имеет 4 различных корня, противоречие по Т. Лагранжа.

Квадраты чисел после $\frac{p-1}{2}$ будут совпадать с уже рассмотренными, т.к. $(-k)^2 = k^2$ $\Rightarrow$  все остальные числа — невычеты.
$\blacksquare$

Утверждение.

1. Число $a$ — вычет mod $p \iff a^{\frac{p-1}{2}} \equiv 1\pmod p$.

2. Число $a$ — невычет mod $p \iff a^{\frac{p-1}{2}} \equiv -1\pmod p$.

$\blacktriangle$

1. $x^{\frac{p-1}{2}} \equiv 1\pmod p$.

   $1^2, 2^2, \ldots , \left( \frac{p-1}{2}\right)^2$ — его корни по МТФ.

   Больше корней нет по Т.Лагранжа.

2. $x^{p-1} \equiv 0\pmod p$.

   $(x^{\frac{p-1}{2}} - 1)(x^{\frac{p-1}{2}} + 1) \equiv 0\pmod p$.

   Если $a$ — невычет, то $x^{\frac{p-1}{2}} -1 \not\equiv 0\pmod p$.

   Тогда $x^{\frac{p-1}{2}} + 1 \equiv 0\pmod p$.
   $\blacksquare$