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

Целое число $a$ называется квадратичным вычетом по модулю $m$ , если разрешимо сравнение[1]:

x^{2}\equiv a{\pmod {m}}.

Если указанное сравнение не разрешимо, то число $a$ называется квадратичным невычетом по модулю $m$ . Решение приведенного выше сравнения означает извлечение квадратного корня в кольце классов вычетов.

Квадратичные вычеты широко применяются в теории чисел, они также нашли практические применения в акустике[2], криптографии, теории графов (см. Граф Пэли) и в других областях деятельности.

Понятие квадратичного вычета может также рассматриваться для произвольного кольца или поля. Например, квадратичные вычеты в конечных полях.

Различия в терминологии

Математическая энциклопедия и ряд других источников определяют квадратичный вычет как число $a$ , для которого существует решение сравнения $x^{2}\equiv a{\pmod {m}}$ . В других источниках (например, Г. Хассе. Лекции по теории чисел, 1953) указано дополнительное требование, что число $a$ взаимно просто с $m$ . Часть источников вообще рассматривает только случай нечётного простого модуля[3][4]. В обоих последних случаях ноль исключается из рассмотрения.

Примеры

Числа $a=0$ и $a=1$ являются квадратичными вычетами по любому модулю, так как сравнения $x^{2}\equiv 0{\pmod {m}}$ и $x^{2}\equiv 1{\pmod {m}}$ всегда имеют решения $x=0$ и $x=1$ соответственно.

Следствие: поскольку для модуля $m=2$ существуют только два класса вычетов $[0]_{2}$ и $[1]_{2},$ любое число по модулю 2 является квадратичным вычетом.

По модулю 3 существуют три класса вычетов: $[0]_{3},[1]_{3},[2]_{3}.$ Их квадраты попадают в классы вычетов $[0]_{3},[1]_{3},[1]_{3}$ соответственно. Отсюда видно, что числа из классов $[0]_{3}$ и $[1]_{3}$ являются квадратичными вычетами, а числа из класса $[2]_{3}$ (например, $2,5,8,-1,-4\dots$ ) — квадратичные невычеты по модулю 3.

Теория квадратичных вычетов широко применяется, в частности, для исследования возможных целочисленных значений квадратичных форм. Рассмотрим, например, уравнение:

x^{2}-5y^{2}=3

Из него следует, что $x^{2}\equiv 3{\pmod {5}}.$ Однако квадраты чисел $0,1,2,3,4$ дают по модулю 5 только вычеты $0,1,4;$ то есть 3 является квадратичным невычетом по модулю 5. Отсюда следует, что приведенное уравнение не имеет решений в целых числах[5].

Общее квадратное сравнение вида $ax^{2}\equiv b{\pmod {m}},$ где числа $a,b$ взаимно просты и не являются делителями модуля $m,$ может быть исследовано следующим образом: находится решение $a^{-1}$ сравнения $ax\equiv 1{\pmod {m}},$ затем исходное квадратное сравнение умножается на $a^{-1},$ получая сравнение вида: $x^{2}\equiv a^{-1}b{\pmod {m}}.$ Осталось определить[6], является ли $a^{-1}b$ квадратичным вычетом по модулю $m$ .

Свойства

Критерий Эйлера: Пусть $p>2$ простое. Число a, взаимно простое с $p$ , является квадратичным вычетом по модулю $p$ тогда и только тогда, когда[1]:
$a^{(p-1)/2}\equiv 1{\pmod {p}},$

и является квадратичным невычетом по модулю p тогда и только тогда, когда

a^{(p-1)/2}\equiv -1{\pmod {p}}.

Квадратичный закон взаимности
Квадратичные вычеты, взаимно простые с модулем, образуют мультипликативную подгруппу кольца вычетов индекса 2, в частности:
- вычет × вычет = вычет;
- невычет × вычет = невычет.
- невычет × невычет = вычет.

Количество

По простому модулю

Среди ненулевых чисел $1,2,...,p-1$ , для простого модуля $p\geq 3$ существует ровно ${\frac {p-1}{2}}$ квадратичных вычетов и ${\frac {p-1}{2}}$ невычетов.

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

Так как $x^{2}\equiv (p-x)^{2}{\pmod {p}}$ , то достаточно показать, что среди чисел $0^{2},1^{2},2^{2},\dots ,\left({\frac {p-1}{2}}\right)^{2}$ нет сравнимых по модулю $p$ .

Пусть такие числа есть и $x^{2}\equiv y^{2}{\pmod {p}}$ при $x\not =y$ и $0\leq x,y\leq {\frac {p-1}{2}}$ .

Так как $p\mid (x^{2}-y^{2})$ , то $p\mid (x-y)(x+y)$ и, ввиду того, что $p$ - простое, и $0<|x-y|<p$ , имеем $p\mid (x+y)$ , что невозможно потому, что $x+y\leq p-1$

Таким образом, ненулевые квадратичные вычеты образуют подгруппу индекса 2 в мультипликативной группе кольца $\mathbb {Z} _{p}$ .

По произвольному модулю

Вальтер Стангл в 1996 году представил формулу, позволяющую вычислить количество квадратичных вычетов по произвольному модулю $n$ .[7]

Пусть $n=2^{t}{p_{1}}^{d_{1}}{p_{2}}^{d_{2}}\dots {p_{k}}^{d_{k}}$ — каноническое разложение числа $n$ . Тогда для количества $s(n)$ квадратичных вычетов по модулю $n$ верна формула

$s(n)=\left\lfloor {\frac {2^{t-1}+5}{3}}\right\rfloor \prod \limits _{i=1}^{k}{\left\lfloor {\frac {{p_{i}}^{d_{i}+1}+2p_{i}+2}{2(p_{i}+1)}}\right\rfloor }$

Распределение

Количество в интервале

Пусть $p>3$ — простое, $Q<p$ . Обозначим через ${R_{p}}(Q)$ количество квадратичных вычетов по модулю $p$ среди чисел $1,\dots ,Q$ .

И. М. Виноградовым было доказано, что ${R_{p}}(Q)={\frac {Q}{2}}+\theta {\frac {{\sqrt {p}}\ln {p}}{2}}$ , где $|\theta |<1$ .

Из этого следует, что в произвольных интервалах достаточно большой длины (такой, что ${\sqrt {p}}\ln {p}=o(Q(p))$ ) будет иметь место асимптотическое равенство ${R_{p}}(Q)\sim {\frac {Q}{2}}$ , то есть квадратичных вычетов и невычетов асимптотически будет поровну.

Наименьший квадратичный невычет по данному модулю

Обозначим через $T(p)$ минимальный положительный квадратичный невычет по простому модулю $p$ .

Из неравенства ${R_{p}}(Q)\leq {\frac {Q}{2}}+{\frac {{\sqrt {p}}\ln {p}}{2}}$ (см. раздел «количество в интервале»), напрямую следует, что ${R_{p}}(\left\lfloor {{\sqrt {p}}\ln {p}}\right\rfloor +1)\leq \left\lfloor {{\sqrt {p}}\ln {p}}\right\rfloor$ , то есть $T(p)\leq {\sqrt {p}}\ln {p}+1$ .

В результате более глубоких исследований Виноградов доказал, что $T(p)\leq p^{\frac {1}{2{\sqrt {e}}}}\left({\log {p}}\right)^{2}$ .

Существует выдвинутая Виноградовым гипотеза о том, что $T(p)=o(p^{\varepsilon })\forall \varepsilon >0$ .

Если гипотеза Римана верна, то $T(p)=O({\ln ^{2}}{p})$ .

См. также

Символ Лежандра
См. последовательность A096008 в OEIS — список квадратичных вычетов.

Примечания

Математическая энциклопедия, 1979, с. 785—786.
Walker, R The design and application of modular acoustic diffusing elements (неопр.). BBC Research Department. Дата обращения: 25 октября 2016.
Виноградов, 1952, Глава 5.
MathWorld: Quadratic Residue (неопр.).
Нестеренко, 2008, с. 83.
Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел.. — М.: Наука, 1965. — С. 59. — 176 с.
Stangl, Walter D. (October 1996), Counting Squares in ℤ_n, Mathematics Magazine Т. 69 (4): 285–289, doi:10.2307/2690536, <http://www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf>

Литература

Виноградов И. М. Основы теории чисел. — М.—Л.: ГИТТЛ, 1952. — 180 с.
Квадратичный вычет // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1979. — Т. 2.
Нестеренко Ю. В. Теория чисел. — М.: Издательский центр «Академия», 2008. — С. 132—133. — 272 с. — ISBN 9785769546464.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[VIN-1] Математическая энциклопедия, 1979, с. 785—786.

[2] Walker, R The design and application of modular acoustic diffusing elements (неопр.). BBC Research Department. Дата обращения: 25 октября 2016.

[_c1ac94e85fd47840-3] Виноградов, 1952, Глава 5.

[4] MathWorld: Quadratic Residue (неопр.).

[_b751644457eb50ef-5] Нестеренко, 2008, с. 83.

[6] Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел.. — М.: Наука, 1965. — С. 59. — 176 с.

[7] Stangl, Walter D. (October 1996), Counting Squares in ℤ_n, Mathematics Magazine Т. 69 (4): 285–289, doi:10.2307/2690536, <http://www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf>