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

 Целое число 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).