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

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

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

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

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

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

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

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

Примеры

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

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

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

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

${\displaystyle x^{2}-5y^{2}=3}$

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

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

Свойства

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

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

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

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

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

Количество

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 )}}$

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

1. Математическая энциклопедия, 1979, с. 785—786.
2. Walker, R The design and application of modular acoustic diffusing elements  (неопр.). BBC Research Department. Дата обращения: 25 октября 2016. Архивировано 27 марта 2016 года.
3. Виноградов, 1952, Глава 5.
4. MathWorld: Quadratic Residue  (неопр.). Архивировано 16 февраля 2017 года.
5. Нестеренко, 2008, с. 83.
6. Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел.. — М.: Наука, 1965. — С. 59. — 176 с.
7. Stangl, Walter D. (October 1996), "Counting Squares in ℤ_n" (PDF), Mathematics Magazine, 69 (4): 285—289, doi:10.2307/2690536, Архивировано (PDF) 24 декабря 2015, Дата обращения: 29 июля 2015 Источник  (неопр.). Дата обращения: 29 июля 2015. Архивировано 24 декабря 2015 года.

Литература

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