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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition= Рассмотрим <tex>p\in\mathbb{P}\text{, }p>2</tex>. Если сравнение <tex>x^2\equiv a(mod\text{ }p)</tex> …»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 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>.
 
−
}}
 

Текущая версия на 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].

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Квадратичные_вычеты&oldid=84592»