Квадратичный вычет: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Строка 18:
== Распределение ==
=== Количество ===
==== По простому модулю ====
Для простого модуля <math>p>3</math> существует ровно <math>\frac{p+1}{2}</math> квадратичных вычетов и <math>\frac{p-1}{2}</math> невычетов.
{{Hider|
Строка 31 ⟶ 32 :
Так как <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>.
Пусть <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>, то первый множитель учитывается.
== См. также ==
| |||