Квадратичный вычет: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Строка 35:
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>
}}
== Распределение ==
=== Количество ===
Для простого модуля <math>p>3</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>(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>
}}
| |||