63
правки
Изменения
→Символ Лежандра, критерий Эйлера
|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) решений не имеет.
}}
