imported>Alex NB OT: Форматирование дат согласно Википедия:Техническое соглашение о датах и времени и Википедия:Обсуждение правил/Википедия:Техническое соглашение о датах и времени

2025-08-21T09:45:46Z

Форматирование дат согласно Википедия:Техническое соглашение о датах и времени и Википедия:Обсуждение правил/Википедия:Техническое соглашение о датах и времени

Новая страница

[[Целое число]] <math>a</math> называется '''квадратичным вычетом''' по модулю <math>m</math>, если разрешимо [[Сравнение по модулю|сравнение]]{{sfn|Математическая энциклопедия|1979|с=785—786|name=VIN}}:
: <math>x^2 \equiv a \pmod{m}.</math>

Если указанное сравнение не разрешимо, то число <math>a</math> называется квадратичным '''невычетом''' по модулю <math>m</math>. Решение приведенного выше сравнения означает извлечение квадратного корня в [[Кольцо (математика)|кольце]] [[Сравнение по модулю|классов вычетов]].

Квадратичные вычеты широко применяются в [[теория чисел|теории чисел]], они также нашли практические применения в [[Акустика|акустике]]<ref>{{cite web|last=Walker|first=R|title=The design and application of modular acoustic diffusing elements|url=http://downloads.bbc.co.uk/rd/pubs/reports/1990-15.pdf|publisher=BBC Research Department|access-date=2016-10-25|archive-date=2016-03-27|archive-url=https://web.archive.org/web/20160327222208/http://downloads.bbc.co.uk/rd/pubs/reports/1990-15.pdf|url-status=live}}</ref>, [[Криптография|криптографии]], [[Теория графов|теории графов]] (см. [[Граф Пэли]]) и в других областях деятельности.

Понятие квадратичного вычета может также рассматриваться для произвольного [[Кольцо (математика)|кольца]] или [[Поле (алгебра)|поля]]. Например, квадратичные вычеты в [[Конечное поле|конечных полях]].

== Различия в терминологии ==
[[Математическая энциклопедия]] и ряд других источников определяют квадратичный вычет как число <math>a</math>, для которого существует решение сравнения <math>x^2 \equiv a \pmod{m}</math>. В других источниках (например, ''Г. Хассе.'' Лекции по теории чисел, 1953) указано дополнительное требование, что число <math>a</math> взаимно просто с <math>m</math>. Часть источников вообще рассматривает только случай нечётного [[Простое число|простого]] модуля{{sfn |Виноградов|1952|loc=Глава 5}}<ref>{{cite web |title=MathWorld: Quadratic Residue |url=http://mathworld.wolfram.com/QuadraticResidue.html |publisher= |access-date= |archive-date=2017-02-16 |archive-url=https://web.archive.org/web/20170216125354/http://mathworld.wolfram.com/QuadraticResidue.html |url-status=live }}</ref>. В обоих последних случаях ноль исключается из рассмотрения.

== Примеры ==
Числа <math>a=0</math> и <math>a=1</math> являются квадратичными вычетами по любому модулю, так как сравнения <math>x^2 \equiv 0 \pmod{m}</math> и <math>x^2 \equiv 1 \pmod{m}</math> всегда имеют решения <math>x=0</math> и <math>x=1</math> соответственно.

''Следствие'': поскольку для модуля <math>m=2</math> существуют только два класса вычетов <math>[0]_2</math> и <math>[1]_2,</math> любое число по модулю 2 является квадратичным вычетом.

По модулю 3 существуют три класса вычетов: <math>[0]_3, [1]_3, [2]_3.</math> Их квадраты попадают в классы вычетов <math>[0]_3, [1]_3, [1]_3</math> соответственно. Отсюда видно, что числа из классов <math>[0]_3</math> и <math>[1]_3</math> являются квадратичными вычетами, а числа из класса <math>[2]_3</math> (например, <math>2, 5, 8, -1, -4\dots</math>) — квадратичные невычеты по модулю 3.

Теория квадратичных вычетов широко применяется, в частности, для исследования возможных целочисленных значений [[Квадратичная форма|квадратичных форм]]. Рассмотрим, например, уравнение:
: <math>x^2-5y^2=3</math>
Из него следует, что <math>x^2 \equiv 3 \pmod{5}.</math> Однако квадраты чисел <math>0,1,2,3,4</math> дают по модулю 5 только вычеты <math>0,1,4;</math> то есть 3 является квадратичным невычетом по модулю 5. Отсюда следует, что приведенное уравнение не имеет решений в целых числах{{sfn|Нестеренко|2008|с=83}}.

Общее квадратное сравнение вида <math>ax^2 \equiv b \pmod{m},</math> где числа <math>a,b</math> [[Взаимно простые числа|взаимно просты]] и не являются делителями модуля <math>m,</math> может быть исследовано следующим образом: находится решение <math>a^{-1}</math> сравнения <math>ax \equiv 1 \pmod{m},</math> затем исходное квадратное сравнение умножается на <math>a^{-1}, </math> получая сравнение вида: <math>x^2 \equiv a^{-1}b \pmod{m}.</math> Осталось определить<ref>{{книга |автор=Дэвенпорт Г. |заглавие=Высшая арифметика. Введение в теорию чисел. |место=М.|издательство=Наука |год=1965 |страниц=176 |страницы=59 }}</ref>, является ли <math>a^{-1}b</math> квадратичным вычетом по модулю <math>m</math>.

== Свойства ==
* [[Критерий Эйлера]]: Пусть <math>p>2</math> простое. Число a, [[взаимно простые числа|взаимно простое]] с <math>p</math>, является квадратичным вычетом по модулю <math>p</math> тогда и только тогда, когда<ref name=VIN/>:
*: <math>a^{\frac{p-1}{2}} \equiv 1\pmod{p},</math>
: и является квадратичным невычетом по модулю ''p'' тогда и только тогда, когда
:: <math>a^{\frac{p-1}{2}} \equiv -1\pmod{p}.</math>
* [[Квадратичный закон взаимности]]
* Квадратичные вычеты, взаимно простые с модулем, образуют [[Мультипликативная группа кольца вычетов|мультипликативную подгруппу]] [[кольцо вычетов|кольца вычетов]] [[индекс подгруппы|индекса]] 2, в частности:
** вычет × вычет = вычет;
** невычет × вычет = невычет.
** невычет × невычет = вычет.

== Количество ==

=== По простому модулю ===
Среди ненулевых чисел <math>1, 2, ..., p-1</math>, для простого модуля <math>p\geq3</math> существует ровно <math>\frac{p-1}{2}</math> квадратичных вычетов и <math>\frac{p-1}{2}</math> невычетов.
{{Hider|
title = Доказательство|
hidden = 1 |
title-style = text-align: left; |
content-style = text-align: left; |
content =
Так как <math>x^2 \equiv (p-x)^2 \pmod{p}</math>, то достаточно показать, что среди чисел <math>0^2, 1^2, 2^2, \dots, \left({\frac{p-1}{2}}\right)^2</math> нет сравнимых по модулю <math>p</math>.

Пусть такие числа есть и <math>x^2 \equiv y^2 \pmod{p}</math> при <math>x \not = y</math> и <math>0 \le x,y \le \frac{p-1}{2}</math>.

Так как <math>p \mid (x^2-y^2)</math>, то <math>p \mid (x-y)(x+y)</math> и, ввиду того, что <math>p</math> - простое, и <math>0<|x-y|<p</math>, имеем <math>p \mid(x+y)</math>, что невозможно потому, что <math>x+y \le p-1</math>
}}

Таким образом, ненулевые квадратичные вычеты образуют подгруппу индекса 2 в [[Мультипликативная группа кольца вычетов|мультипликативной группе]] кольца <math>\mathbb{Z}_p</math>.

=== По произвольному модулю ===
Вальтер Стангл в 1996 году представил формулу, позволяющую вычислить количество квадратичных вычетов по произвольному модулю <math>n</math>.<ref>{{Citation |last=Stangl |first=Walter D. |title=Counting Squares in ℤ<sub>''n''</sub> |journal=Mathematics Magazine |volume=69 |issue=4 |pages=285–289 |date=1996-10 |url=http://www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf |doi=10.2307/2690536 |access-date=2015-07-29 |archive-date=2015-12-24 |archive-url=https://web.archive.org/web/20151224013638/http://www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf |url-status=live }} {{Cite web |url=http://www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf |title=Источник |access-date=2015-07-29 |archive-date=2015-12-24 |archive-url=https://web.archive.org/web/20151224013638/http://www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf |url-status=unfit }}</ref>

Пусть <math>n = 2^t {p_1}^{d_1} {p_2}^{d_2} \dots {p_k}^{d_k}</math> — [[Основная теорема арифметики|каноническое разложение]] числа <math>n</math>. Тогда для количества <math>s(n)</math> квадратичных вычетов по модулю <math>n</math> верна формула

<math>s(n) = \Biggl( \begin{cases}
{2^{t-1}+4 \over 3}, & \text{if }t\text{ is even}
\\ {2^{t-1}+5 \over 3}, & \text{if }t\text{ is odd}
\end{cases}\Biggr)
\prod \limits_{i=1}^{k}
\Biggl( \begin{cases}
{{p_i}^{{d_i}+1}+{p_i}+2 \over 2({p_i}+1)}, & \text{if }{d_i}\text{ is even}
\\ {{p_i}^{{d_i}+1}+2{p_i}+1 \over 2({p_i}+1)}, & \text{if }{d_i}\text{ is odd}
\end{cases}\Biggr)
</math>

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

=== Количество в интервале ===
Пусть <math>p>3</math> — простое, <math>Q<p</math>. Обозначим через <math>{R_p}(Q)</math> количество квадратичных вычетов по модулю <math>p</math> среди чисел <math>1, \dots, Q</math>.

[[Иван Матвеевич Виноградов|И. М. Виноградовым]] было доказано, что <math>{R_p}(Q) = \frac{Q}{2} + \theta \frac{\sqrt{p} \ln{p}}{2}</math>, где <math>|\theta|<1</math>.

Из этого следует, что в произвольных интервалах достаточно большой длины (такой, что <math>\sqrt{p} \ln{p} = o(Q(p))</math>) будет иметь место асимптотическое равенство <math>{R_p}(Q) \sim \frac{Q}{2}</math>, то есть квадратичных вычетов и невычетов асимптотически будет поровну.

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

Обозначим через <math>T(p)</math> минимальный положительный квадратичный невычет по простому модулю <math>p</math>.

Из неравенства <math>{R_p}(Q) \le \frac{Q}{2} + \frac{\sqrt{p} \ln{p}}{2}</math> (см. раздел «количество в интервале»), напрямую следует, что <math>{R_p}(\left\lfloor{\sqrt{p} \ln{p}}\right\rfloor + 1) \le \left\lfloor{\sqrt{p} \ln{p}}\right\rfloor</math>, то есть <math>T(p) \le \sqrt{p} \ln{p} + 1</math>.

В результате более глубоких исследований Виноградов доказал, что <math>T(p) \le p^{\frac{1}{2\sqrt{e}}} \left({\log{p}}\right)^2</math>.

Существует выдвинутая Виноградовым гипотеза о том, что <math>T(p)=o(p^{\varepsilon}) \forall \varepsilon > 0</math>.

Если [[гипотеза Римана]] верна, то <math>T(p) = O({\ln^2}{p})</math>.

== См. также ==
* [[Символ Лежандра]]
* См. {{OEIS|id=A096008}} — список квадратичных вычетов.

== Примечания ==
{{примечания}}

== Литература ==
* {{книга |автор=Виноградов И. М. |заглавие=Основы теории чисел
|издательство=ГИТТЛ |место=М.-Л. |год=1952 |страниц=180
|ссылка=http://math.ru/lib/book/djvu/vinogradov.djvu |ref=Виноградов}}
* {{книга |часть=Квадратичный вычет |заглавие=Математическая энциклопедия (в 5 томах)
|место=М. |ref=Математическая энциклопедия |том=2 |год=1979
|издательство=[[Большая Российская энциклопедия (издательство)|Советская Энциклопедия]] }}
* {{книга |автор=Нестеренко Ю. В. |заглавие=Теория чисел
|место=М. |издательство =Издательский центр «Академия» |год=2008
|страницы=132—133 |страниц=272 |isbn=9785769546464 |ref=Нестеренко }}

[[Категория:Теория чисел]]

Квадратичный вычет - История изменений