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

Поделись знанием:
Перейти к: навигация, поиск

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

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

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





Свойства

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

Количество

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

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

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

По произвольному модулю

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

Пусть <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) = \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}</math>

Если <math>t=0</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>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>.

Нижние оценки

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

См. также

Напишите отзыв о статье "Квадратичный вычет"

Примечания

  1. Stangl, Walter D. (October 1996), "[www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf Counting Squares in ℤn]", Mathematics Magazine Т. 69 (4): 285–289, doi:[dx.doi.org/10.2307%2F2690536 10.2307/2690536], <www.maa.org/sites/default/files/Walter_D22068._Stangl.pdf> 

Литература

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

Отрывок, характеризующий Квадратичный вычет

Так же весело в жарких лучах полуденного солнца вьются пчелы вокруг обезматочившего улья, как и вокруг других живых ульев; так же издалека пахнет от него медом, так же влетают и вылетают из него пчелы. Но стоит приглядеться к нему, чтобы понять, что в улье этом уже нет жизни. Не так, как в живых ульях, летают пчелы, не тот запах, не тот звук поражают пчеловода. На стук пчеловода в стенку больного улья вместо прежнего, мгновенного, дружного ответа, шипенья десятков тысяч пчел, грозно поджимающих зад и быстрым боем крыльев производящих этот воздушный жизненный звук, – ему отвечают разрозненные жужжания, гулко раздающиеся в разных местах пустого улья. Из летка не пахнет, как прежде, спиртовым, душистым запахом меда и яда, не несет оттуда теплом полноты, а с запахом меда сливается запах пустоты и гнили. У летка нет больше готовящихся на погибель для защиты, поднявших кверху зады, трубящих тревогу стражей. Нет больше того ровного и тихого звука, трепетанья труда, подобного звуку кипенья, а слышится нескладный, разрозненный шум беспорядка. В улей и из улья робко и увертливо влетают и вылетают черные продолговатые, смазанные медом пчелы грабительницы; они не жалят, а ускользают от опасности. Прежде только с ношами влетали, а вылетали пустые пчелы, теперь вылетают с ношами. Пчеловод открывает нижнюю колодезню и вглядывается в нижнюю часть улья. Вместо прежде висевших до уза (нижнего дна) черных, усмиренных трудом плетей сочных пчел, держащих за ноги друг друга и с непрерывным шепотом труда тянущих вощину, – сонные, ссохшиеся пчелы в разные стороны бредут рассеянно по дну и стенкам улья. Вместо чисто залепленного клеем и сметенного веерами крыльев пола на дне лежат крошки вощин, испражнения пчел, полумертвые, чуть шевелящие ножками и совершенно мертвые, неприбранные пчелы.
Пчеловод открывает верхнюю колодезню и осматривает голову улья. Вместо сплошных рядов пчел, облепивших все промежутки сотов и греющих детву, он видит искусную, сложную работу сотов, но уже не в том виде девственности, в котором она бывала прежде. Все запущено и загажено. Грабительницы – черные пчелы – шныряют быстро и украдисто по работам; свои пчелы, ссохшиеся, короткие, вялые, как будто старые, медленно бродят, никому не мешая, ничего не желая и потеряв сознание жизни. Трутни, шершни, шмели, бабочки бестолково стучатся на лету о стенки улья. Кое где между вощинами с мертвыми детьми и медом изредка слышится с разных сторон сердитое брюзжание; где нибудь две пчелы, по старой привычке и памяти очищая гнездо улья, старательно, сверх сил, тащат прочь мертвую пчелу или шмеля, сами не зная, для чего они это делают. В другом углу другие две старые пчелы лениво дерутся, или чистятся, или кормят одна другую, сами не зная, враждебно или дружелюбно они это делают. В третьем месте толпа пчел, давя друг друга, нападает на какую нибудь жертву и бьет и душит ее. И ослабевшая или убитая пчела медленно, легко, как пух, спадает сверху в кучу трупов. Пчеловод разворачивает две средние вощины, чтобы видеть гнездо. Вместо прежних сплошных черных кругов спинка с спинкой сидящих тысяч пчел и блюдущих высшие тайны родного дела, он видит сотни унылых, полуживых и заснувших остовов пчел. Они почти все умерли, сами не зная этого, сидя на святыне, которую они блюли и которой уже нет больше. От них пахнет гнилью и смертью. Только некоторые из них шевелятся, поднимаются, вяло летят и садятся на руку врагу, не в силах умереть, жаля его, – остальные, мертвые, как рыбья чешуя, легко сыплются вниз. Пчеловод закрывает колодезню, отмечает мелом колодку и, выбрав время, выламывает и выжигает ее.