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

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

Квадратичный вычет по простому модулю p — число a, для которого разрешимо сравнение

x^2 \equiv a \pmod{p}.

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

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

и является квадратичным невычетом по модулю p тогда и только тогда, когда
a^{(p-1)/2}\equiv -1\pmod{p}.

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

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

Для простого модуля p>3 существует ровно \frac{p+1}{2} квадратичных вычетов и \frac{p-1}{2} невычетов.

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

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

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

s(n) = \left\lfloor{\frac{2^{t-1}+5}{3}}\right\rfloor \prod \limits_{i=1}^{k} {\left\lfloor{\frac{{p_i}^{d_i + 1} + 2 p_i + 2}{2(p_i + 1)}}\right\rfloor}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для наименьшего квадратичного вычета по простому модулю p известна также условная оценка \Omega(\ln{p} \ln\ln{p}) и безусловная оценка \Omega(\ln{p} \ln\ln\ln{p}).

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

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

  • Нестеренко Ю. В. Теория чисел. — М.: Издательский центр «Академия», 2008. — С. 132-133. — 272 с. — ISBN 9785769546464.