|
|
| Строка 6: |
Строка 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>\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>, получаем требуемое.
| |
| − | }}
| |
| − | ==Теорема о <tex>((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)</tex> при <tex>p=4\cdot k+1</tex>==
| |
| − | Рассмотрим сравнение <tex>\left(\cfrac{a}{p}\right)=a^{\frac{p-1}{2}}(mod ~p)</tex>. Если <tex>a=1</tex>, то сравнение примет вид <tex>\left(\cfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}(mod~p)</tex>. То есть <tex>a=-1</tex> будет квадратичным вычетом, если <tex>(-1)^{\frac{p-1}{2}}=1</tex>. Любое нечетное целое число имеет вид <tex>4\cdot k+1</tex>, или <tex>4\cdot k+3</tex>. Рассмотрим <tex>p=4\cdot k+1</tex>, тогда <tex>(-1)^{2\cdot k}=1</tex>, это равенство выполняется при любом <tex>k</tex>. Теперь рассмотрим <tex>p=4 \cdot k+3</tex>, получим <tex>(-1)^{2\cdot k+1}=1</tex>, это равенство не выполняется при любом <tex>k</tex>. Следовательно, <tex>a=-1</tex> будет квадратичным вычетом по модулю всех простых чисел, задаваемых формулой <tex>p=4 \cdot k+1</tex>.
| |
| − | {{Теорема
| |
| − | |id=th2
| |
| − | |statement=
| |
| − | <tex>((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)</tex> при <tex>p=4\cdot k+1</tex>
| |
| − | |proof=
| |
| − | Так как <tex>(p-1)!=-1(mod ~p)</tex>, то подставив в это сравнение <tex>p=4\cdot k+1</tex>, получим <tex>(4 \cdot k)!=-1(mod~p)</tex>. Рассмотрим <tex>((\frac{p-1}{2})!)^2</tex>, подставим <tex>p = 4 \cdot k+1</tex>, получим <tex>((2 \cdot k)!)^2</tex>. Рассмотрим сравнение <tex>(4 \cdot k)!=-1(mod~p)</tex>:
| |
| − | <br>
| |
| − | <tex>1\cdot 2\cdot \dots \cdot (2\cdot k)\cdot (2 \cdot k+1)\cdot \dots \cdot (4 \cdot k)\equiv -1 (mod~p)</tex>
| |
| − | <br>
| |
| − | <tex>1\cdot 2\cdot \dots \cdot (2\cdot k)\cdot (-2 \cdot k)\cdot \dots \cdot (-1)\equiv -1 (mod~p)</tex>
| |
| − | <br>
| |
| − | Так как число отрицательных членов четно, все минусы сократатся, получим:
| |
| − | <br>
| |
| − | <tex>1\cdot 2\cdot \dots \cdot (2\cdot k)\cdot (2 \cdot k)\cdot \dots \cdot (1)\equiv -1 (mod~p)</tex>
| |
| − | <br>
| |
| − | <tex>(2\cdot k)!\cdot(2\cdot k)!\equiv -1 (mod ~p)</tex>
| |
| − | <br>
| |
| − | <tex>((2\cdot k)!)^2\equiv -1 (mod~p)</tex>
| |
| − | <br>
| |
| − | А так как <tex>((2\cdot k)!)^2=((\frac{p-1}{2})!)^2(mod~p)</tex>, то <tex>((\frac{p-1}{2})!)^2=-1(mod~p)</tex>, при <tex>p=4\cdot k+1</tex>.
| |
| − |
| |
| − | }}
| |
| − | ==Лемма Гаусса для вычисления квадратичного характера числа по простому модулю==
| |
| − | {{Лемма
| |
| − | |id=lem1
| |
| − | |author=Гаусс
| |
| − | |about=Вычисление квадратичного характера числа по простому модулю
| |
| − | |statement=
| |
| − | <tex>\left(\cfrac{a}{p}\right)=(-1)^{\mu}</tex>, где <tex>\mu</tex> — чимло отрицательных вычетов в ряде абсолютно-наименьших вычетов произведений <tex>1\cdot a,~2\ cdot a, \dots,~\frac{p-1}{2}\cdot a</tex> по модулю <tex>p</tex>.
| |
| − | |proof=
| |
| − | Пусть <tex>\pm \varepsilon_i</tex> — наименьший вычет для <tex>i \cdot a</tex>, где <texvarepsilon_i</tex> положительно. Когда <tex>i</tex> пробегает значения между 1 и <tex>\frac{p-1}{2}</tex>, <tex>\mu</tex> будет числом получившихся при этом знаков минус.<tex>\varepsilon_i\ne\varepsilon_j</tex>, при <tex>i\ne j</tex>. Перемножая сравнения <tex>1\cdot a \equiv \pm\varepsilon_1(mod~p),~2\cdot a \equiv \pm\varepsilon_2(mod~p), \dots, ~(\frac{p-1}{2})\cdot a \equiv \pm\varepsilon_{\frac{p-1}{2}}(mod~p)</tex>, получаем:
| |
| − | <br>
| |
| − | <tex>(\frac{p-1}{2})!\cdot a^{\frac{p-1}{2}}\equiv (-1)^{\mu}\cdot(\frac{p-1}{2})! (mod~p)</tex>.
| |
| − | <br>
| |
| − | Значит <tex>a^{\frac{p-1}{2}}\equiv (-1)^{\mu}(mod~p);~a^{\frac{p-1}{2}}\equiv \left(\cfrac{a}{p}\right)~\Rightarrow ~ \left(\cfrac{a}{p}\right)=(-1)^{\mu}</tex>.
| |
| − | }}
| |
| | | | |
| | [[Категория: Теория чисел]] | | [[Категория: Теория чисел]] |
