63
правки
Изменения
→Теорема о ((\frac{p-1}{2})!)^2\equiv -1 (mod ~p) при p=4\cdot k+1
А так как <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>.
}}
