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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 7 промежуточных версий 1 участника)
Строка 1: Строка 1:
{{Требует доработки
+
{{В разработке}}
|item1=Надо привести более конструктивное доказательство теоремы. Так, чтобы получился алгоритм. И привести время работы этого алгоритма. Алгоритм должен эффективно работать для простых чисел порядка <tex>10^{300}</tex>.
 
}}
 
  
 
{{Лемма
 
{{Лемма
Строка 8: Строка 6:
 
Если <tex>p</tex> {{---}} простое, то <tex>(p-1)!+1</tex> делится на <tex>p</tex>.
 
Если <tex>p</tex> {{---}} простое, то <tex>(p-1)!+1</tex> делится на <tex>p</tex>.
 
|proof=
 
|proof=
При <tex>p=2, p=3</tex> доказательство очевидно. Докажем для <tex>p\geqslant 5</tex>. Так как <tex>\mathbb{Z}_p</tex> - поле, то для каждого <tex>x</tex> есть такое <tex>y</tex>, что <tex>xy\equiv 1(mod p)</tex>. Может оказаться, что для некоторых <tex>0\leqslant x\leqslant p-1</tex> выполнено <tex>x=y</tex>. Найдём все такие <tex>x</tex>, что <tex>x^2\equiv 1(mod p)</tex>.  <tex>x^2-1\equiv 0(mod p)   \Rightarrow (x-1)(x+1)\equiv 0(mod p)</tex>. Значит <tex>x\equiv 1(mod p)</tex> или <tex>x\equiv p-1(mod p)</tex>.
+
При <tex>p=2, p=3</tex> доказательство очевидно. Докажем для <tex>p\geqslant 5</tex>. Так как <tex>\mathbb{Z}_p</tex> - поле, то для каждого <tex>x</tex> есть такое <tex>y</tex>, что <tex>xy\equiv 1\pmod p</tex>. Может оказаться, что для некоторых <tex>0\leqslant x\leqslant p-1</tex> выполнено <tex>x=y</tex>. Найдём все такие <tex>x</tex>, что <tex>x^2\equiv 1\pmod p</tex>.  <tex>x^2-1\equiv 0\pmod p  \Rightarrow (x-1)(x+1)\equiv 0\pmod p</tex>. Значит <tex>x\equiv 1\pmod p</tex> или <tex>x\equiv p-1\pmod p</tex>.
  
Из этого следует, что множество <tex>{2,3,\cdots,p-2}</tex> разбивается на пары такие, что произведение чисел внутри каждой из них сравнимо с <tex>1</tex> по модулю<tex>p</tex>. Таким образом <tex>(p-2)!\equiv 1(mod p)</tex>. Но <tex>p-1\equiv -1(mod p)</tex>. Следовательно <tex>(p-1)!\equiv -1(mod p)</tex>
+
Из этого следует, что множество <tex>{2,3,\cdots,p-2}</tex> разбивается на пары такие, что произведение чисел внутри каждой из них сравнимо с <tex>1</tex> по модулю<tex>p</tex>. Таким образом <tex>(p-2)!\equiv 1\pmod p</tex>. Но <tex>p-1\equiv -1\pmod p</tex>. Следовательно <tex>(p-1)!\equiv -1\pmod p</tex>
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если <tex>p\equiv 1(mod 4),p\in\mathbb{P}</tex>, то оно представимо в виде суммы двух квадратов.
+
Если <tex>p\equiv 1\pmod 4,p\in\mathbb{P}</tex>, то оно представимо в виде суммы двух квадратов.
 
|proof=
 
|proof=
Из леммы Вильсона <tex>(p-1)!\equiv 1(mod p) \Rightarrow (4n)!+1\equiv 0 (mod p) </tex>. Следовательно <tex>1\cdot 2\cdots (2n)\cdot(p-2n)\cdots(p-1)+1 \equiv ((2n)!)^2+1(mod p)</tex>. Теперь говорим, что <tex> N = (2n)!</tex>, тогда <tex>N^2 \equiv -1(mod p)</tex>.
+
Из леммы Вильсона <tex>(p-1)!\equiv 1\pmod p \Rightarrow (4n)!+1\equiv 0 \pmod p </tex>. Следовательно <tex>1\cdot 2\cdots (2n)\cdot(p-2n)\cdots(p-1)+1 \equiv ((2n)!)^2+1\pmod p</tex>. Теперь говорим, что <tex> N = (2n)!</tex>, тогда <tex>N^2 \equiv -1\pmod 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>.
+
Рассмотрим пары чисел <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\pmod p</tex>, получим, что <tex>a^2+b^2\equiv 0\pmod 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>.
 
}}
 
}}
  
 +
{{Теорема
 +
|statement=
 +
Если <tex>p\equiv 1 \pmod 4,p\in\mathbb{P}</tex>, то оно представимо в виде суммы двух квадратов. (В форме алгоритма)
 +
|proof=
 +
Возьмём <tex>h</tex> такое, что <tex>h^2+1\vdots p</tex>.
 +
 +
Запустим алгоритм Евклида для чисел <tex>p,h</tex>. Получим последовательность чисел <tex>t_0=p, t_1=h, \cdots, t_k=1</tex>.
 +
Утверждается, что существуют такое <tex>i</tex>, что <tex>t_i^2+t_{i+1}^2=p</tex>. Докажем это.
 +
 +
Разложим <tex>\frac{p}{h}</tex> в цепную дробь <tex>\langle a_0,\cdots,a_n \rangle</tex>, при этом сделав <tex>n</tex> чётным. Для этого разложения верно <tex>a_0 = p \:\: div\:\: h \:\: a_1 = h \:\: div\:\: t_2 \dots</tex>
 +
 +
Также <tex>\frac{p_{n-1}}{q_{n-1}}=\frac{p}{h}</tex>
 +
 +
Запишем свойство цепных дробей.
 +
<tex>P_{n-1}Q_{n-2}-P_{n-2}Q_{n-1}=(-1)^{n}</tex>. По тому, какое мы взяли <tex>h</tex> получаем <tex>h^2+1\vdots p \: \Rightarrow p_{n-2}\%p=(-1)^{n+1}(h^{-1}\%p) = (-1)^n h</tex>. Так как взяли чётную <tex>n</tex>, то <tex>p_{n-2} = h</tex>
 +
 +
На данном этапе имеем : <tex>p_{n-1}=t_0 \:\: p_{n-2}=t_1 </tex>.  И <tex>p_{n-3}=p_{n-1}\% p_{n-2}=t_0\% t_1=t_2</tex> Проделав так далее, получаем <tex>P_{n-i-1} = t_i</tex>.
 +
 +
Распишем дробь <tex>\frac{p}{h}=\frac{\alpha P_i +P_{i-1}}{\alpha Q_i + Q_{i-1}}. \;\; \alpha=\frac{t_{i+1}}{t_{i+2}}</tex> , следовательно <tex>\frac{p}{h}=\frac{t_{i+1}P_i+t_{i+2}P_{i-1}}{t_{i+1}Q_i+t_{i+2}Q_{i-1}}</tex>. По вышесказанному <tex>t_{i+1}P_i+t_{i+2}P_{i-1}=t_{i+1}t_{n-i-1}+t_{i+2}t_{n-i}</tex>. Теперь возьмём <tex>i=\frac{n}{2}-1 \Rightarrow \frac{p}{h}=\frac{t_{\frac{n}{2}}^2+t_{\frac{n}{2}+1}^2}{t_{\frac{n}{2}}Q_{\frac{n}{2}-1}+t_{\frac{n}{2}+1}Q_{\frac{n}{2}-2}}</tex>. Так как <tex> t_i</tex> взаимно просты, то числитель и знаменатель взаимно просты, следовательно <tex>p=t_{\frac{n}{2}}^2+t_{\frac{n}{2}+1}^2</tex>. Что и требовалось доказать.
 +
}}
 
[[Категория:Теория чисел]]
 
[[Категория:Теория чисел]]

Текущая версия на 23:11, 17 января 2012

Эта статья находится в разработке!
Лемма (Вильсон):
Если [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\pmod p[/math]. Может оказаться, что для некоторых [math]0\leqslant x\leqslant p-1[/math] выполнено [math]x=y[/math]. Найдём все такие [math]x[/math], что [math]x^2\equiv 1\pmod p[/math]. [math]x^2-1\equiv 0\pmod p \Rightarrow (x-1)(x+1)\equiv 0\pmod p[/math]. Значит [math]x\equiv 1\pmod p[/math] или [math]x\equiv p-1\pmod p[/math].

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

Из леммы Вильсона [math](p-1)!\equiv 1\pmod p \Rightarrow (4n)!+1\equiv 0 \pmod p [/math]. Следовательно [math]1\cdot 2\cdots (2n)\cdot(p-2n)\cdots(p-1)+1 \equiv ((2n)!)^2+1\pmod p[/math]. Теперь говорим, что [math] N = (2n)![/math], тогда [math]N^2 \equiv -1\pmod 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\pmod p[/math], получим, что [math]a^2+b^2\equiv 0\pmod 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]
Теорема:
Если [math]p\equiv 1 \pmod 4,p\in\mathbb{P}[/math], то оно представимо в виде суммы двух квадратов. (В форме алгоритма)
Доказательство:
[math]\triangleright[/math]

Возьмём [math]h[/math] такое, что [math]h^2+1\vdots p[/math].

Запустим алгоритм Евклида для чисел [math]p,h[/math]. Получим последовательность чисел [math]t_0=p, t_1=h, \cdots, t_k=1[/math]. Утверждается, что существуют такое [math]i[/math], что [math]t_i^2+t_{i+1}^2=p[/math]. Докажем это.

Разложим [math]\frac{p}{h}[/math] в цепную дробь [math]\langle a_0,\cdots,a_n \rangle[/math], при этом сделав [math]n[/math] чётным. Для этого разложения верно [math]a_0 = p \:\: div\:\: h \:\: a_1 = h \:\: div\:\: t_2 \dots[/math]

Также [math]\frac{p_{n-1}}{q_{n-1}}=\frac{p}{h}[/math]

Запишем свойство цепных дробей. [math]P_{n-1}Q_{n-2}-P_{n-2}Q_{n-1}=(-1)^{n}[/math]. По тому, какое мы взяли [math]h[/math] получаем [math]h^2+1\vdots p \: \Rightarrow p_{n-2}\%p=(-1)^{n+1}(h^{-1}\%p) = (-1)^n h[/math]. Так как взяли чётную [math]n[/math], то [math]p_{n-2} = h[/math]

На данном этапе имеем : [math]p_{n-1}=t_0 \:\: p_{n-2}=t_1 [/math]. И [math]p_{n-3}=p_{n-1}\% p_{n-2}=t_0\% t_1=t_2[/math] Проделав так далее, получаем [math]P_{n-i-1} = t_i[/math].

Распишем дробь [math]\frac{p}{h}=\frac{\alpha P_i +P_{i-1}}{\alpha Q_i + Q_{i-1}}. \;\; \alpha=\frac{t_{i+1}}{t_{i+2}}[/math] , следовательно [math]\frac{p}{h}=\frac{t_{i+1}P_i+t_{i+2}P_{i-1}}{t_{i+1}Q_i+t_{i+2}Q_{i-1}}[/math]. По вышесказанному [math]t_{i+1}P_i+t_{i+2}P_{i-1}=t_{i+1}t_{n-i-1}+t_{i+2}t_{n-i}[/math]. Теперь возьмём [math]i=\frac{n}{2}-1 \Rightarrow \frac{p}{h}=\frac{t_{\frac{n}{2}}^2+t_{\frac{n}{2}+1}^2}{t_{\frac{n}{2}}Q_{\frac{n}{2}-1}+t_{\frac{n}{2}+1}Q_{\frac{n}{2}-2}}[/math]. Так как [math] t_i[/math] взаимно просты, то числитель и знаменатель взаимно просты, следовательно [math]p=t_{\frac{n}{2}}^2+t_{\frac{n}{2}+1}^2[/math]. Что и требовалось доказать.
[math]\triangleleft[/math]