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

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

Рассмотрим [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]\left(\cfrac{a}{p}\right)[/math] — называется символом Лежандра, если [math]\left(\cfrac{a}{p}\right)=1[/math], когда [math]a[/math] - квадратичный вычет по модулю [math]p[/math], и [math]\left(\cfrac{a}{p}\right)=-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]\left(\cfrac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(mod\text{ }p)[/math].

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

[math]\triangleright[/math]

Рассмотрим три утверждения: (1) [math]x^2\equiv a (mod~ p)[/math] (2) [math]a^{\frac{p-1}{2}}\equiv 1 (mod~p)[/math] (3) [math]a^{\frac{p-1}{2}}\equiv -1 (mod~p)[/math] Сначала докажем, что [math]a[/math] одновременно удовлетворяет только одному сравнению (2) или (3). [math]a^{\phi (p)}=1(mod ~ p)[/math], отсюда [math]0=a^{\phi(p)}-1 (mod ~p)=a^{p-1}-1 (mod ~p)= (a^{\frac{p-1}{2}}-1)\cdot(a^{\frac{p-1}{2}}+1) (mod ~ p)[/math], значит хотя бы один из сомножителей должен делиться на [math]p[/math]. Но они не могут делиться на [math]p[/math] одновременно, так как их разность равна [math]\pm 2[/math], а [math]p\gt 2[/math] Теперь возведем обе части сравнения (1) в степень [math]\frac{p-1}{2}[/math]. Получим [math]x^{p-1}=a^{\frac{p-1}{2}} (mod ~p)[/math]. Но [math]x^{p-1}=1(mod ~p)[/math], значит если [math]a[/math] удовлетворяет сравнению (1), то выполняется и сравнение (2). Рассмотрим последовательность чисел [math]1,~2,~\dots ,~ p-1[/math], или, что то же самое, [math]1,~2,~\dots,~\frac{p-1}{2},~ \frac{p+1}{2}-1,~\dots,~p-1[/math]. Очевидно, что [math]1^2\equiv (p-1)^2,~ 2^2\equiv (p-2)^2,~\dots (\frac{p-1}{2})^2 \equiv (\frac{p+1}{2})^2[/math] по модулю [math]p[/math]. Значит существует только [math]\frac{p-1}{2}[/math] различных квадратов чисел по модулю [math]p[/math]. Обозначим их [math]a_1,~a_2,~\dots,~a_{\frac{p-1}{2}}[/math]. Если [math]a[/math] равно любому [math]a_i[/math], то сравнение (1) имеет решение, следовательно сравнение (2) так же выполняется для всех [math]a_i[/math]. Но сравнение (2) не может иметь более [math]\frac{p-1}{2}[/math] различных решений, следовательно оно имеет ровно столько решений. Отсюда же следует, что и сравнение (3) имеет ровно [math]\frac{p-1}{2}[/math] различных решений, и при [math]a[/math], равном любому из этих решений, сравнение (1) решений не имеет.

[math]\triangleleft[/math]

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

Произведение двух квадратичных вычетов будет вычетом, двух невычетов — вычетом, вычета и невычета — невычетом.

[math]\triangleright[/math]

[math]\left(\cfrac{a\cdot b}{p}\right)=(a\cdot b)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}\cdot b^{\frac{p-1}{2}}=\left(\cfrac{a}{p}\right)\cdot \left(\cfrac{b}{p}\right)[/math]. Зная, что [math]1\cdot 1=1,~(-1)\cdot(-1)=1, ~ 1 \cdot (-1)=-1[/math], получаем требуемое.

[math]\triangleleft[/math]