419
правок
Изменения
Нет описания правки
{{Лемма
|author= Вильсон
|statement=
Если <tex>p</tex> {{- --}} простое, то <tex>(p-1)!+1</tex> делится на <tex>p</tex>.
|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\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\pmod p</tex>. Но <tex>p-1\equiv -1\pmod p</tex>. Следовательно <tex>(p-1)!\equiv -1\pmod p</tex>
}}
{{Теорема
|statement=
Если <tex>p\equiv 1\pmod 4,p\in\mathbb{P}</tex>, то оно представимо в виде суммы двух квадратов.
|proof=
Из леммы Вильсона <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\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>. Что и требовалось доказать.
}}
[[Категория:Теория чисел]]
