63
правки
Изменения
Новая страница: «{{В разработке}} ==Символ Лежандра, критерий Эйлера== {{Определение |definition= <tex>\left(\cfrac{a}{p}\right)</t…»
{{В разработке}}
==Символ Лежандра, критерий Эйлера==
{{Определение
|definition=
<tex>\left(\cfrac{a}{p}\right)</tex> — называется символом Лежандра, если <tex>\left(\cfrac{a}{p}\right)=1</tex>, когда <tex>a</tex> - квадратичный вычет по модулю <tex>p</tex>, и <tex>\left(\cfrac{a}{p}\right)=-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>\left(\cfrac{a}{p}\right)\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) решений не имеет.
}}
{{Утверждение
|id=prop1
|statement=Произведение двух квадратичных вычетов будет вычетом, двух невычетов — вычетом, вычета и невычета — невычетом.
|proof=
<tex>\left(\cfrac{a\cdot b}{p}\right)=(a\cdot b)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}\cdot b^{\frac{p-1}{2}}=\left(\cfrac{a}{p}\right)\cdot \left(\cfrac{b}{p}\right)</tex>. Зная, что <tex>1\cdot 1=1,~(-1)\cdot(-1)=1, ~ 1 \cdot (-1)=-1</tex>, получаем требуемое.
}}
[[Категория: Теория чисел]]
==Символ Лежандра, критерий Эйлера==
{{Определение
|definition=
<tex>\left(\cfrac{a}{p}\right)</tex> — называется символом Лежандра, если <tex>\left(\cfrac{a}{p}\right)=1</tex>, когда <tex>a</tex> - квадратичный вычет по модулю <tex>p</tex>, и <tex>\left(\cfrac{a}{p}\right)=-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>\left(\cfrac{a}{p}\right)\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) решений не имеет.
}}
{{Утверждение
|id=prop1
|statement=Произведение двух квадратичных вычетов будет вычетом, двух невычетов — вычетом, вычета и невычета — невычетом.
|proof=
<tex>\left(\cfrac{a\cdot b}{p}\right)=(a\cdot b)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}\cdot b^{\frac{p-1}{2}}=\left(\cfrac{a}{p}\right)\cdot \left(\cfrac{b}{p}\right)</tex>. Зная, что <tex>1\cdot 1=1,~(-1)\cdot(-1)=1, ~ 1 \cdot (-1)=-1</tex>, получаем требуемое.
}}
[[Категория: Теория чисел]]
