Квадратичные вычеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Символ Лежандра, критерий Эйлера)
м (rollbackEdits.php mass rollback)
 
(не показано 8 промежуточных версий 2 участников)
Строка 1: Строка 1:
 +
{{В разработке}}
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
Строка 5: Строка 6:
 
==Число квадратичных вычетов по простому модулю==
 
==Число квадратичных вычетов по простому модулю==
 
<tex>x=1,2,...,p-1</tex>; <tex>x^2=1^2,2^2,...,(p-1)^2</tex> — Среди этих квадратов будет <tex>\frac{p-1}{2}</tex> различных по модулю <tex>p</tex>, так как квадраты чисел <tex>a</tex>, и <tex>p-a\equiv -a</tex> равны. Следовательно, количество квадратичных вычетов и невычетов по модулю <tex>p</tex> равно <tex>\frac{p-1}{2}</tex>.
 
<tex>x=1,2,...,p-1</tex>; <tex>x^2=1^2,2^2,...,(p-1)^2</tex> — Среди этих квадратов будет <tex>\frac{p-1}{2}</tex> различных по модулю <tex>p</tex>, так как квадраты чисел <tex>a</tex>, и <tex>p-a\equiv -a</tex> равны. Следовательно, количество квадратичных вычетов и невычетов по модулю <tex>p</tex> равно <tex>\frac{p-1}{2}</tex>.
==Символ Лежандра, критерий Эйлера==
+
 
{{Определение
+
[[Категория: Теория чисел]]
|definition=
 
<tex>(\frac{a}{p})</tex> — называется символом Лежандра, если <tex>(\frac{a}{p})=1</tex>, когда <tex>a</tex> - квадратичный вычет по модулю <tex>p</tex>, и <tex>(\frac{a}{p})=-1</tex>, когда <tex>a</tex> — квадратичный невычет по модулю <tex>p</tex>, <tex>p\in\mathbb{P}</tex>.
 
}}
 
{{Теорема
 
|id=euler
 
|about=Критерий Эйлера
 
|statement=
 
Пусть <tex>p>2 \text{; }p \in \mathbb{P}</tex>. Число <tex>a</tex>, взаимнопростое с <tex>p</tex>, является квадратичным вычетом по модулю <tex>p</tex> тогда и только тогда, когда <tex>a^{\frac{p-1}{2}}\equiv 1(mod\text{ }p)</tex>, и является квадратичным невычетом по модулю <tex>p</tex> тогда и только тогда, когда <tex>a^{\frac{p-1}{2}}\equiv -1(mod\text{ }p)</tex>. То есть <tex>(\frac{a}{p})\equiv a^{\frac{p-1}{2}}(mod\text{ }p)</tex>.
 
|proof=
 
Рассмотрим три утверждения:
 
<br>
 
(1) <tex>x^2\equiv a (mod~ p)</tex>
 
<br>
 
(2) <tex>a^{\frac{p-1}{2}}\equiv 1 (mod~p)</tex>
 
<br>
 
(3) <tex>a^{\frac{p-1}{2}}\equiv -1 (mod~p)</tex>
 
<br>
 
Сначала докажем, что <tex>a</tex> одновременно удовлетворяет только одному сравнению (2) или (3).
 
<tex>a^{\phi (p)}=1(mod ~ p)</tex>, отсюда <tex>0=a^{\phi(p)}-1 (mod ~p)=a^{p-1}-1 (mod ~p)= (a^{\frac{p-1}{2}}-1)\cdot(a^{\frac{p-1}{2}}+1) (mod ~ p)</tex>, значит хотя бы один из сомножителей должен делиться на <tex>p</tex>. Но они не могут делиться на <tex>p</tex> одновременно, так как их разность равна <tex>\pm 2</tex>, а <tex>p>2</tex>
 
<br>
 
Теперь возведем обе части сравнения (1) в степень <tex>\frac{p-1}{2}</tex>. Получим <tex>x^{p-1}=a^{\frac{p-1}{2}} (mod ~p)</tex>. Но <tex>x^{p-1}=1(mod ~p)</tex>, значит если <tex>a</tex> удовлетворяет сравнению (1), то выполняется и сравнение (2). Рассмотрим последовательность чисел <tex>1,~2,~\dots ,~ p-1</tex>, или, что то же самое, <tex>1,~2,~\dots,~\frac{p-1}{2},~ \frac{p+1}{2}-1,~\dots,~p-1</tex>. Очевидно, что <tex>1^2\equiv (p-1)^2,~ 2^2\equiv (p-2)^2,~\dots (\frac{p-1}{2})^2 \equiv (\frac{p+1}{2})^2</tex> по модулю <tex>p</tex>. Значит существует только <tex>\frac{p-1}{2}</tex> различных квадратов чисел по модулю <tex>p</tex>. Обозначим их <tex>a_1,~a_2,~\dots,~a_{\frac{p-1}{2}}</tex>. Если <tex>a</tex> равно любому <tex>a_i</tex>, то сравнение (1) имеет решение, следовательно сравнение (2) так же выполняется для всех <tex>a_i</tex>. Но сравнение (2) не может иметь более <tex>\frac{p-1}{2}</tex> различных решений, следовательно оно имеет ровно столько решений. Отсюда же следует, что и сравнение (3) имеет ровно <tex>\frac{p-1}{2}</tex> различных решений, и при <tex>a</tex>, равном любому из этих решений, сравнение (1) решений не имеет.
 
}}
 

Текущая версия на 19:12, 4 сентября 2022

Эта статья находится в разработке!
Определение:
Рассмотрим [math]p\in\mathbb{P}\text{, }p\gt 2[/math]. Если сравнение [math]x^2\equiv a(mod\text{ }p)[/math] имеет решения, то число [math]a[/math] называется квадратичным вычетом по модулю [math]p[/math]. Если решения нет, то [math]a[/math] называется квадратичным невычетом по модулю [math]p[/math].

Число квадратичных вычетов по простому модулю

[math]x=1,2,...,p-1[/math]; [math]x^2=1^2,2^2,...,(p-1)^2[/math] — Среди этих квадратов будет [math]\frac{p-1}{2}[/math] различных по модулю [math]p[/math], так как квадраты чисел [math]a[/math], и [math]p-a\equiv -a[/math] равны. Следовательно, количество квадратичных вычетов и невычетов по модулю [math]p[/math] равно [math]\frac{p-1}{2}[/math].