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

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

x2a(modm).
  Если указанное сравнение не разрешимо, то число a называется квадратичным невычетом по модулю m. Решение приведенного выше сравнения означает извлечение квадратного корня в кольце классов вычетов.
 Понятие квадратичного вычета широко применяется в теории чисел, оно также нашло практические применения в акустике, криптографии, теории графов (см. Граф Пейли) и в других областях деятельности.
 Понятие квадратичного вычета может также рассматриваться для произвольного кольца или поля. Например, квадратичные вычеты в конечных полях.

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


 Математическая энциклопедия и ряд других источников определяют квадратичный вычет как число a, для которого существует решение сравнения x2a(modm).. В других источниках (например, Г. Хассе. Лекции по теории чисел, 1953) указано дополнительное требование, что число a взаимно просто с m. Часть источников вообще рассматривает только случай нечётного простого модуля . В обоих последних случаях ноль исключается из рассмотрения.

Примеры


 Числа a=0 и a=1 являются квадратичными вычетами по любому модулю, так как сравнения x20(modm) и x21(modm) всегда имеют решения 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) — квадратичные невычеты по модулю 3.

Свойства



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


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

a(p1)/21(modp).


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

Количество


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


 Среди ненулевых чисел 1,2,...,p1, для простого модуля p3 существует ровно p12 квадратичных вычетов и p12 невычетов. \{right)\^2 нет сравнимых по модулю p.
 Пусть такие числа есть и x2y2(modp) при xy и 0x,yp12.
 Так как (x2y2)p, то (xy)(x+y)p и, ввиду того, что p - простое, и $0<|x-y| Таким образом, ненулевые квадратичные вычеты образуют подгруппу индекса 2 в мультипликативной группе кольца Zp.

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


 Вальтер Стангл в 1996 году представил формулу, позволяющую вычислить количество квадратичных вычетов по произвольному модулю n.
 Пусть n=2tp1d1p2d2pkdk — каноническое разложение числа n. Тогда для количества s(n) квадратичных вычетов по модулю n верна формула
s(n)=2t1+53i=1kpidi+1+2pi+22(pi+1)
 Если t=0, то первый множитель не учитывается.

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


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


 Пусть p>3 — простое, $Q И. М. Виноградовым было доказано, что Rp(Q)=Q2+θplnp2, где |θ|<1.
 Из этого следует, что в произвольных интервалах достаточно большой длины (такой, что plnp=o(Q(p))) будет иметь место асимптотическое равенство Rp(Q)Q2, то есть квадратичных вычетов и невычетов асимптотически будет поровну.

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


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

agraphВерхние оценки
 Пусть p — простое число.
 Из неравенства Rp(Q)Q2+plnp2 (см. раздел «количество в интервале»), напрямую следует, что Rp(plnp+1)plnp, то есть T(p)plnp+1.
 В результате более глубоких исследований Виноградов доказал, что T(p)p12e(logp)2.
 Существует выдвинутая Виноградовым гипотеза о том, что T(p)=o(pε)ε>0.
 Если гипотеза Римана верна, то T(p)=O(ln2p).

agraphНижние оценки
 Для наименьшего квадратичного невычета по простому модулю p известна также условная оценка Ω(lnplnlnp) и безусловная оценка Ω(lnplnlnlnp).