63
правки
Изменения
м
→Символ Лежандра, критерий Эйлера
{{Определение
|definition=
<tex>\left(\fraccfrac{a}{p}\right)</tex> — называется символом Лежандра, если <tex>\left(\fraccfrac{a}{p}\right)=1</tex>, когда <tex>a</tex> - квадратичный вычет по модулю <tex>p</tex>, и <tex>\left(\fraccfrac{a}{p}\right)=-1</tex>, когда <tex>a</tex> — квадратичный невычет по модулю <tex>p</tex>, <tex>p\in\mathbb{P}</tex>.
}}
{{Теорема
|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>\left(\fraccfrac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(mod\text{ }p)</tex>.
|proof=
Рассмотрим три утверждения:
|statement=Произведение двух квадратичных вычетов будет вычетом, двух невычетов — вычетом, вычета и невычета — невычетом.
|proof=
<tex>\left(\fraccfrac{a\cdot b}{p}\right)=(a\cdot b)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}\cdot b^{\frac{p-1}{2}}=\left(\fraccfrac{a}{p}\right)\cdot \left(\fraccfrac{b}{p}\right)</tex>. Зная, что <tex>1\cdot 1=1,~(-1)\cdot(-1)=1, ~ 1 \cdot (-1)=-1</tex>, получаем требуемое.
}}
