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

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

Рассмотрим [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]

Теорема о [math]((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)[/math] при [math]p=4\cdot k+1[/math]

Рассмотрим сравнение [math]\left(\cfrac{a}{p}\right)=a^{\frac{p-1}{2}}(mod ~p)[/math]. Если [math]a=1[/math], то сравнение примет вид [math]\left(\cfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}(mod~p)[/math]. То есть [math]a=-1[/math] будет квадратичным вычетом, если [math](-1)^{\frac{p-1}{2}}=1[/math]. Любое нечетное целое число имеет вид [math]4\cdot k+1[/math], или [math]4\cdot k+3[/math]. Рассмотрим [math]p=4\cdot k+1[/math], тогда [math](-1)^{2\cdot k}=1[/math], это равенство выполняется при любом [math]k[/math]. Теперь рассмотрим [math]p=4 \cdot k+3[/math], получим [math](-1)^{2\cdot k+1}=1[/math], это равенство не выполняется при любом [math]k[/math]. Следовательно, [math]a=-1[/math] будет квадратичным вычетом по модулю всех простых чисел, задаваемых формулой [math]p=4 \cdot k+1[/math].

Теорема:

[math]((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)[/math] при [math]p=4\cdot k+1[/math]

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

[math]\triangleright[/math]

Так как [math](p-1)!=-1(mod ~p)[/math], то подставив в это сравнение [math]p=4\cdot k+1[/math], получим [math](4 \cdot k)!=-1(mod~p)[/math]. Рассмотрим [math]((\frac{p-1}{2})!)^2[/math], подставим [math]p = 4 \cdot k+1[/math], получим [math]((2 \cdot k)!)^2[/math]. Рассмотрим сравнение [math](4 \cdot k)!=-1(mod~p)[/math]: [math]1\cdot 2\cdot \dots \cdot (2\cdot k)\cdot (2 \cdot k+1)\cdot \dots \cdot (4 \cdot k)\equiv -1 (mod~p)[/math] [math]1\cdot 2\cdot \dots \cdot (2\cdot k)\cdot (-2 \cdot k)\cdot \dots \cdot (-1)\equiv -1 (mod~p)[/math] Так как число отрицательных членов четно, все минусы сократатся, получим: [math]1\cdot 2\cdot \dots \cdot (2\cdot k)\cdot (2 \cdot k)\cdot \dots \cdot (1)\equiv -1 (mod~p)[/math] [math](2\cdot k)!\cdot(2\cdot k)!\equiv -1 (mod ~p)[/math] [math]((2\cdot k)!)^2\equiv -1 (mod~p)[/math] А так как [math]((2\cdot k)!)^2=((\frac{p-1}{2})!)^2(mod~p)[/math], то [math]((\frac{p-1}{2})!)^2=-1(mod~p)[/math], при [math]p=4\cdot k+1[/math].

[math]\triangleleft[/math]

Лемма Гаусса для вычисления квадратичного характера числа по простому модулю

Лемма (Гаусс, Вычисление квадратичного характера числа по простому модулю):

[math]\left(\cfrac{a}{p}\right)=(-1)^{\mu}[/math], где [math]\mu[/math] — чимло отрицательных вычетов в ряде абсолютно-наименьших вычетов произведений [math]1\cdot a,~2\ cdot a, \dots,~\frac{p-1}{2}\cdot a[/math] по модулю [math]p[/math].

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

[math]\triangleright[/math]

Пусть [math]\pm \varepsilon_i[/math] — наименьший вычет для [math]i \cdot a[/math], где <texvarepsilon_i</tex> положительно. Когда [math]i[/math] пробегает значения между 1 и [math]\frac{p-1}{2}[/math], [math]\mu[/math] будет числом получившихся при этом знаков минус.[math]\varepsilon_i\ne\varepsilon_j[/math], при [math]i\ne j[/math]. Перемножая сравнения [math]1\cdot a \equiv \pm\varepsilon_1(mod~p),~2\cdot a \equiv \pm\varepsilon_2(mod~p), \dots, ~(\frac{p-1}{2})\cdot a \equiv \pm\varepsilon_{\frac{p-1}{2}}(mod~p)[/math], получаем: [math](\frac{p-1}{2})!\cdot a^{\frac{p-1}{2}}\equiv (-1)^{\mu}\cdot(\frac{p-1}{2})! (mod~p)[/math]. Значит [math]a^{\frac{p-1}{2}}\equiv (-1)^{\mu}(mod~p);~a^{\frac{p-1}{2}}\equiv \left(\cfrac{a}{p}\right)~\Rightarrow ~ \left(\cfrac{a}{p}\right)=(-1)^{\mu}[/math].

[math]\triangleleft[/math]