Линейное сравнение по простому модулю имеет решение всегда, когда коэффициент при $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$