Теорема о (((p-1)/2)!)^2=-1(mod p)

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Теорема о [math]((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)[/math] при [math]p=4\cdot k+1[/math]

Рассмотрим сравнение [math]\left(\cfrac{a}{p}\right)=a^{\frac{p-1}{2}}(mod ~p)[/math]. Если [math]a=-1[/math], то сравнение примет вид [math]\left(\cfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}(mod~p)[/math]. То есть [math]a=-1[/math] будет квадратичным вычетом, если [math](-1)^{\frac{p-1}{2}}=1[/math]. Любое нечетное целое число имеет вид [math]4\cdot k+1[/math], или [math]4\cdot k+3[/math]. Рассмотрим [math]p=4\cdot k+1[/math], тогда [math](-1)^{2\cdot k}=1[/math], это равенство выполняется при любом [math]k[/math]. Теперь рассмотрим [math]p=4 \cdot k+3[/math], получим [math](-1)^{2\cdot k+1}=1[/math], это равенство не выполняется при любом [math]k[/math]. Следовательно, [math]a=-1[/math] будет квадратичным вычетом по модулю всех простых чисел, задаваемых формулой [math]p=4 \cdot k+1[/math].

Теорема:
[math]((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)[/math] при [math]p=4\cdot k+1[/math]
Доказательство:
[math]\triangleright[/math]

Так как [math](p-1)!=-1(mod ~p)[/math], то подставив в это сравнение [math]p=4\cdot k+1[/math], получим [math](4 \cdot k)!=-1(mod~p)[/math]. Рассмотрим [math]((\frac{p-1}{2})!)^2[/math], подставим [math]p = 4 \cdot k+1[/math], получим [math]((2 \cdot k)!)^2[/math]. Рассмотрим сравнение [math](4 \cdot k)!=-1(mod~p)[/math]:
[math]1\cdot 2\cdot \dots \cdot (2\cdot k)\cdot (2 \cdot k+1)\cdot \dots \cdot (4 \cdot k)\equiv -1 (mod~p)[/math]
[math]1\cdot 2\cdot \dots \cdot (2\cdot k)\cdot (-2 \cdot k)\cdot \dots \cdot (-1)\equiv -1 (mod~p)[/math]
Так как число отрицательных членов четно, все минусы сократятся, получим:
[math]1\cdot 2\cdot \dots \cdot (2\cdot k)\cdot (2 \cdot k)\cdot \dots \cdot (1)\equiv -1 (mod~p)[/math]
[math](2\cdot k)!\cdot(2\cdot k)!\equiv -1 (mod ~p)[/math]
[math]((2\cdot k)!)^2\equiv -1 (mod~p)[/math]

А так как [math]((2\cdot k)!)^2=((\frac{p-1}{2})!)^2(mod~p)[/math], то [math]((\frac{p-1}{2})!)^2=-1(mod~p)[/math], при [math]p=4\cdot k+1[/math].
[math]\triangleleft[/math]