Квадратичный вычет
Целое число
Если указанное сравнение не разрешимо, то число
Квадратичные вычеты широко применяются в теории чисел, они также нашли практические применения в акустике[2], криптографии, теории графов (см. Граф Пэли) и в других областях деятельности.
Понятие квадратичного вычета может также рассматриваться для произвольного кольца или поля. Например, квадратичные вычеты в конечных полях.
Различия в терминологии
Математическая энциклопедия и ряд других источников определяют квадратичный вычет как число
Примеры
Числа
Следствие: поскольку для модуля
По модулю 3 существуют три класса вычетов:
Теория квадратичных вычетов широко применяется, в частности, для исследования возможных целочисленных значений квадратичных форм. Рассмотрим, например, уравнение:
Из него следует, что
Общее квадратное сравнение вида
Свойства
- Критерий Эйлера: Пусть
простое. Число a, взаимно простое с , является квадратичным вычетом по модулю тогда и только тогда, когда[1]:
- и является квадратичным невычетом по модулю p тогда и только тогда, когда
- Квадратичный закон взаимности
- Квадратичные вычеты, взаимно простые с модулем, образуют мультипликативную подгруппу кольца вычетов индекса 2, в частности:
- вычет × вычет = вычет;
- невычет × вычет = невычет.
- невычет × невычет = вычет.
Количество
По простому модулю
Среди ненулевых чисел
Таким образом, ненулевые квадратичные вычеты образуют подгруппу индекса 2 в мультипликативной группе кольца
По произвольному модулю
Вальтер Стангл в 1996 году представил формулу, позволяющую вычислить количество квадратичных вычетов по произвольному модулю
Пусть
Распределение
Количество в интервале
Пусть
И. М. Виноградовым было доказано, что
Из этого следует, что в произвольных интервалах достаточно большой длины (такой, что
Наименьший квадратичный невычет по данному модулю
Обозначим через
Из неравенства
В результате более глубоких исследований Виноградов доказал, что
Существует выдвинутая Виноградовым гипотеза о том, что
Если гипотеза Римана верна, то
См. также
- Символ Лежандра
- См. последовательность A096008 в OEIS — список квадратичных вычетов.
Примечания
- ↑ Перейти обратно: 1,0 1,1 Математическая энциклопедия, 1979, с. 785—786.
- ↑ Walker, R The design and application of modular acoustic diffusing elements . BBC Research Department. Дата обращения: 25 октября 2016. Архивировано 27 марта 2016 года.
- ↑ Виноградов, 1952, Глава 5.
- ↑ MathWorld: Quadratic Residue . Архивировано 16 февраля 2017 года.
- ↑ Нестеренко, 2008, с. 83.
- ↑ Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел.. — М.: Наука, 1965. — С. 59. — 176 с.
- ↑ 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.