Представление простых в виде суммы двух квадратов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
{{В разработке}}
 
 
 
{{Лемма
 
{{Лемма
 
|author= Вильсон
 
|author= Вильсон
Строка 19: Строка 17:
 
Рассмотрим пары чисел <tex>(m,s)</tex> такие, что <tex>0\leqslant m, s \leqslant [\sqrt{p}]</tex>. Число таких пар равно <tex>([\sqrt{p}]+1)^2>p</tex>. Значит по крайней мере для двух различных пар <tex>(m_1,s_1),(m_2,s_2)</tex> остатки от деления <tex>m_1+Ns_1, m_2+Ns_2</tex> на <tex>p</tex> будут одинаковыми, т.е. число <tex>a+Nb</tex>, где <tex>a=m_1-m_2, b=s_1-s_2</tex>, будет делится на <tex>p</tex>. При этом <tex>~|a|<\sqrt{p},~|b|<\sqrt{p}</tex>. Но тогда число <tex>a^2-N^2b^2=(a-Nb)(a+Nb)</tex> делится на <tex>p</tex>. Учитывая, что <tex>N^2\equiv -1(mod p)</tex>, получим, что <tex>a^2+b^2\equiv 0(mod p) \Rightarrow a^2+b^2=rp</tex>, где <tex>r\in\mathbb{N}</tex>. Но <tex>a^2+b^2<2p\Rightarrow r=1</tex>, а значит <tex>a^2+b^2=p</tex>.
 
Рассмотрим пары чисел <tex>(m,s)</tex> такие, что <tex>0\leqslant m, s \leqslant [\sqrt{p}]</tex>. Число таких пар равно <tex>([\sqrt{p}]+1)^2>p</tex>. Значит по крайней мере для двух различных пар <tex>(m_1,s_1),(m_2,s_2)</tex> остатки от деления <tex>m_1+Ns_1, m_2+Ns_2</tex> на <tex>p</tex> будут одинаковыми, т.е. число <tex>a+Nb</tex>, где <tex>a=m_1-m_2, b=s_1-s_2</tex>, будет делится на <tex>p</tex>. При этом <tex>~|a|<\sqrt{p},~|b|<\sqrt{p}</tex>. Но тогда число <tex>a^2-N^2b^2=(a-Nb)(a+Nb)</tex> делится на <tex>p</tex>. Учитывая, что <tex>N^2\equiv -1(mod p)</tex>, получим, что <tex>a^2+b^2\equiv 0(mod p) \Rightarrow a^2+b^2=rp</tex>, где <tex>r\in\mathbb{N}</tex>. Но <tex>a^2+b^2<2p\Rightarrow r=1</tex>, а значит <tex>a^2+b^2=p</tex>.
 
}}
 
}}
 +
 +
[[Категория:Теория чисел]]

Версия 20:36, 2 июля 2010

Лемма (Вильсон):
Если [math]p[/math] - простое, то [math](p-1)!+1[/math] делится на [math]p[/math].
Доказательство:
[math]\triangleright[/math]

При [math]p=2, p=3[/math] доказательство очевидно. Докажем для [math]p\geqslant 5[/math]. Так как [math]\mathbb{Z}_p[/math] - поле, то для каждого [math]x[/math] есть такое [math]y[/math], что [math]xy\equiv 1(mod p)[/math]. Может оказаться, что для некоторых [math]0\leqslant x\leqslant p-1[/math] выполнено [math]x=y[/math]. Найдём все такие [math]x[/math], что [math]x^2\equiv 1(mod p)[/math]. [math]x^2-1\equiv 0(mod p) \Rightarrow (x-1)(x+1)\equiv 0(mod p)[/math]. Значит [math]x\equiv 1(mod p)[/math] или [math]x\equiv p-1(mod p)[/math].

Из этого следует, что множество [math]{2,3,\cdots,p-2}[/math] разбивается на пары такие, что произведение чисел внутри каждой из них сравнимо с [math]1[/math] по модулю[math]p[/math]. Таким образом [math](p-2)!\equiv 1(mod p)[/math]. Но [math]p-1\equiv -1(mod p)[/math]. Следовательно [math](p-1)!\equiv -1(mod p)[/math]
[math]\triangleleft[/math]
Теорема:
Если [math]p\equiv 1(mod 4),p\in\mathbb{P}[/math], то оно представимо в виде суммы двух квадратов.
Доказательство:
[math]\triangleright[/math]

Из леммы Вильсона [math](p-1)!\equiv 1(mod p) \Rightarrow (4n)!+1\equiv 0 (mod p) [/math]. Следовательно [math]1\cdot 2\cdots (2n)\cdot(p-2n)\cdots(p-1)+1 \equiv ((2n)!)^2+1(mod p)[/math]. Теперь говорим, что [math] N = (2n)![/math], тогда [math]N^2 \equiv -1(mod p)[/math].

Рассмотрим пары чисел [math](m,s)[/math] такие, что [math]0\leqslant m, s \leqslant [\sqrt{p}][/math]. Число таких пар равно [math]([\sqrt{p}]+1)^2\gt p[/math]. Значит по крайней мере для двух различных пар [math](m_1,s_1),(m_2,s_2)[/math] остатки от деления [math]m_1+Ns_1, m_2+Ns_2[/math] на [math]p[/math] будут одинаковыми, т.е. число [math]a+Nb[/math], где [math]a=m_1-m_2, b=s_1-s_2[/math], будет делится на [math]p[/math]. При этом [math]~|a|\lt \sqrt{p},~|b|\lt \sqrt{p}[/math]. Но тогда число [math]a^2-N^2b^2=(a-Nb)(a+Nb)[/math] делится на [math]p[/math]. Учитывая, что [math]N^2\equiv -1(mod p)[/math], получим, что [math]a^2+b^2\equiv 0(mod p) \Rightarrow a^2+b^2=rp[/math], где [math]r\in\mathbb{N}[/math]. Но [math]a^2+b^2\lt 2p\Rightarrow r=1[/math], а значит [math]a^2+b^2=p[/math].
[math]\triangleleft[/math]