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

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

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

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

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

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

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

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

Примеры

Числа $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. Отсюда следует, что приведенное уравнение не имеет решений в целых числах.

Общее квадратное сравнение вида $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}}.$ Осталось определить, является ли $a^{-1}b$ квадратичным вычетом по модулю $m$.

Свойства

• Критерий Эйлера: Пусть $p>2$ простое. Число a, взаимно простое с $p$, является квадратичным вычетом по модулю $p$ тогда и только тогда, когда:

  $a^{\frac {p-1}{2}}\equiv 1{\pmod {p}},$

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

$a^{\frac {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$.

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

$s(n)={\Biggl (}{\begin{cases}{2^{t-1}+4 \over 3},&{\text{if }}t{\text{ is even}}\\{2^{t-1}+5 \over 3},&{\text{if }}t{\text{ is odd}}\end{cases}}{\Biggr )}\prod \limits _{i=1}^{k}{\Biggl (}{\begin{cases}{{p_{i}}^{{d_{i}}+1}+{p_{i}}+2 \over 2({p_{i}}+1)},&{\text{if }}{d_{i}}{\text{ is even}}\\{{p_{i}}^{{d_{i}}+1}+2{p_{i}}+1 \over 2({p_{i}}+1)},&{\text{if }}{d_{i}}{\text{ is odd}}\end{cases}}{\Biggr )}$

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

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

Пусть $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 — список квадратичных вычетов.

Литература

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