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

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

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

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

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

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

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

Примеры править

Числа   и   являются квадратичными вычетами по любому модулю, так как сравнения   и   всегда имеют решения   и   соответственно.

Следствие: поскольку для модуля   существуют только два класса вычетов   и   любое число по модулю 2 является квадратичным вычетом.

По модулю 3 существуют три класса вычетов:   Их квадраты попадают в классы вычетов   соответственно. Отсюда видно, что числа из классов   и   являются квадратичными вычетами, а числа из класса   (например,  ) — квадратичные невычеты по модулю 3.

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

 

Из него следует, что   Однако квадраты чисел   дают по модулю 5 только вычеты   то есть 3 является квадратичным невычетом по модулю 5. Отсюда следует, что приведенное уравнение не имеет решений в целых числах[5].

Общее квадратное сравнение вида   где числа   взаимно просты и не являются делителями модуля   может быть исследовано следующим образом: находится решение   сравнения   затем исходное квадратное сравнение умножается на   получая сравнение вида:   Осталось определить[6], является ли   квадратичным вычетом по модулю  .

Свойства править

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

Количество править

По простому модулю править

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

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

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

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

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

 

Распределение править

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

Пусть   — простое,  . Обозначим через   количество квадратичных вычетов по модулю   среди чисел  .

И. М. Виноградовым было доказано, что  , где  .

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

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

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

Из неравенства   (см. раздел «количество в интервале»), напрямую следует, что  , то есть  .

В результате более глубоких исследований Виноградов доказал, что  .

Существует выдвинутая Виноградовым гипотеза о том, что  .

Если гипотеза Римана верна, то  .

См. также править

Примечания править

  1. 1 2 Математическая энциклопедия, 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 Источник. Дата обращения: 29 июля 2015. Архивировано 24 декабря 2015 года.

Литература править

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