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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Примеры[править | править вики-текст]

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

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

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

Свойства[править | править вики-текст]

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

Количество[править | править вики-текст]

По простому модулю[править | править вики-текст]

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

По произвольному модулю[править | править вики-текст]

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

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

Если , то первый множитель не учитывается.

Распределение[править | править вики-текст]

Количество в интервале[править | править вики-текст]

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

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

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

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

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

Верхние оценки[править | править вики-текст]

Пусть  — простое число.

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

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

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

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

Нижние оценки[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Математическая энциклопедия, 1979, с. 785—786.
  2. Walker, R The design and application of modular acoustic diffusing elements. BBC Research Department. Проверено 25 октября 2016.
  3. 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> 

Литература[править | править вики-текст]

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