Теорема о (((p-1)/2)!)^2=-1(mod p) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о ((\frac{p-1}{2})!)^2\equiv -1 (mod ~p) при p=4\cdot k+1)
(Теорема о ((\frac{p-1}{2})!)^2\equiv -1 (mod ~p) при p=4\cdot k+1)
 
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 
==Теорема о <tex>((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)</tex> при <tex>p=4\cdot k+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>.
+
Рассмотрим сравнение <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
 
|id=th2

Текущая версия на 14:49, 27 мая 2012

Эта статья находится в разработке!

Теорема о [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]