Перейти к содержанию

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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

x2a(modm).

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

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

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

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

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

Примеры

Числа 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.

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

x25y2=3

Из него следует, что x23(mod5). Однако квадраты чисел 0,1,2,3,4 дают по модулю 5 только вычеты 0,1,4; то есть 3 является квадратичным невычетом по модулю 5. Отсюда следует, что приведенное уравнение не имеет решений в целых числах[5].

Общее квадратное сравнение вида ax2b(modm), где числа a,b взаимно просты и не являются делителями модуля m, может быть исследовано следующим образом: находится решение a1 сравнения ax1(modm), затем исходное квадратное сравнение умножается на a1, получая сравнение вида: x2a1b(modm). Осталось определить[6], является ли a1b квадратичным вычетом по модулю m.

Свойства

и является квадратичным невычетом по модулю p тогда и только тогда, когда
a(p1)/21(modp).

Количество

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

Среди ненулевых чисел 1,2,...,p1, для простого модуля p3 существует ровно p12 квадратичных вычетов и p12 невычетов.

Таким образом, ненулевые квадратичные вычеты образуют подгруппу индекса 2 в мультипликативной группе кольца Zp.

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

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

Пусть n=2tp1d1p2d2pkdk — каноническое разложение числа n. Тогда для количества s(n) квадратичных вычетов по модулю n верна формула

s(n)=2t1+53i=1kpidi+1+2pi+22(pi+1)

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

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

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

И. М. Виноградовым было доказано, что Rp(Q)=Q2+θplnp2, где |θ|<1.

Из этого следует, что в произвольных интервалах достаточно большой длины (такой, что plnp=o(Q(p))) будет иметь место асимптотическое равенство Rp(Q)Q2, то есть квадратичных вычетов и невычетов асимптотически будет поровну.

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

Обозначим через T(p) минимальный положительный квадратичный невычет по простому модулю 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).

См. также

Примечания

  1. Перейти обратно: 1,0 1,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, Mathematics Magazine Т. 69 (4): 285–289, doi:10.2307/2690536, <http://www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf>  Архивная копия от 24 декабря 2015 на Wayback Machine

Литература

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