Русская Википедия:Квадратичный вычет

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Целое число <math>a</math> называется квадратичным вычетом по модулю <math>m</math>, если разрешимо сравнениеШаблон:Sfn:

<math>x^2 \equiv a \pmod{m}.</math>

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

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

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

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

Математическая энциклопедия и ряд других источников определяют квадратичный вычет как число <math>a</math>, для которого существует решение сравнения <math>x^2 \equiv a \pmod{m}</math>. В других источниках (например, Г. Хассе. Лекции по теории чисел, 1953) указано дополнительное требование, что число <math>a</math> взаимно просто с <math>m</math>. Часть источников вообще рассматривает только случай нечётного простого модуляШаблон:Sfn[2]. В обоих последних случаях ноль исключается из рассмотрения.

Примеры

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

Общее квадратное сравнение вида <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> Осталось определить[3], является ли <math>a^{-1}b</math> квадратичным вычетом по модулю <math>m</math>.

Свойства

  • Критерий Эйлера: Пусть <math>p>2</math> простое. Число a, взаимно простое с <math>p</math>, является квадратичным вычетом по модулю <math>p</math> тогда и только тогда, когда[4]:
    <math>a^{(p-1)/2}\equiv 1\pmod{p},</math>
и является квадратичным невычетом по модулю p тогда и только тогда, когда
<math>a^{(p-1)/2}\equiv -1\pmod{p}.</math>

Количество

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

Среди ненулевых чисел <math>1, 2, ..., p-1</math>, для простого модуля <math>p\geq3</math> существует ровно <math>\frac{p-1}{2}</math> квадратичных вычетов и <math>\frac{p-1}{2}</math> невычетов. Шаблон:Hider\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>.[5]

Пусть <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>.

См. также

Примечания

Шаблон:Примечания

Литература

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite web
  3. ↑ Шаблон:Книга
  4. ↑ Ошибка цитирования Неверный тег <ref>; для сносок VIN не указан текст
  5. ↑ Шаблон:Citation Шаблон:Wayback
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Квадратичный_вычет&oldid=10105375