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

Определение:

Рассмотрим [math]p\in\mathbb{P}\text{, }p\gt 2[/math]. Если сравнение [math]x^2\equiv a(mod\text{ }p)[/math] имеет решения, то число [math]a[/math] называется квадратичным вычетом по модулю [math]p[/math]. Если решения нет, то [math]a[/math] называется квадратичным невычетом по модулю [math]p[/math].

Число квадратичных вычетов по простому модулю

[math]x=1,2,...,p-1[/math]; [math]x^2=1^2,2^2,...,(p-1)^2[/math] — Среди этих квадратов будет [math]\frac{p-1}{2}[/math] различных по модулю [math]p[/math], так как квадраты чисел [math]a[/math], и [math]p-a\equiv -a[/math] равны. Следовательно, количество квадратичных вычетов и невычетов по модулю [math]p[/math] равно [math]\frac{p-1}{2}[/math].

Символ Лежандра, критерий Эйлера

Определение:

[math](\frac{a}{p})[/math] — называется символом Лежандра, если [math](\frac{a}{p})=1[/math], когда [math]a[/math] - квадратичный вычет по модулю [math]p[/math], и [math](\frac{a}{p})=-1[/math], когда [math]a[/math] — квадратичный невычет по модулю [math]p[/math], [math]p\in\mathbb{P}[/math].

Теорема (Критерий Эйлера):

Пусть [math]p\gt 2 \text{; }p \in \mathbb{P}[/math]. Число [math]a[/math], взаимнопростое с [math]p[/math], является квадратичным вычетом по модулю [math]p[/math] тогда и только тогда, когда [math]a^{\frac{p-1}{2}}\equiv 1(mod\text{ }p)[/math], и является квадратичным невычетом по модулю [math]p[/math] тогда и только тогда, когда [math]a^{\frac{p-1}{2}}\equiv -1(mod\text{ }p)[/math]. То есть [math](\frac{a}{p})\equiv a^{\frac{p-1}{2}}(mod\text{ }p)[/math].