|
|
| (не показано 7 промежуточных версий 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) решений не имеет.
| |
| − | }}
| |
| − | {{Утверждение
| |
| − | |id=prop1
| |
| − | |statement=Произведение двух квадратичных вычетов будет вычетом, двух невычетов — вычетом, вычета и невычета — невычетом.
| |
| − | |proof=
| |
| − | <tex>(\frac{a\cdot b}{p})=(a\cdot b)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}\cdot b^{\frac{p-1}{2}}=(\frac{a}{p})\cdot (\frac{b}{p})</tex>. Зная, что <tex>1\cdot 1=1,~(-1)\cdot(-1)=1, ~ 1 \cdot (-1)=-1</tex>, получаем требуемое.
| |
| − | }}
| |
Эта статья находится в разработке!
| Определение: |
| Рассмотрим [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].
