Изменения

Возьмём <tex>h:h^2+1\vdots p</tex> и <tex>h=g^{\frac{p-1}{4}}</tex>. Запустим алгоритм Евклида на <tex>p,h</tex>. Получим <tex>t_0=p, t_1=h, \cdots, t_k=1</tex>.Докажем, что существуют такое <tex>i</tex>, что <tex>t_ih^2+t_{i+1}^2=\vdots p</tex>.

Разложим Запустим алгоритм Евклида для чисел <tex>\frac{p}{,h}</tex> в цепную дробь . Получим последовательность чисел <tex>\langle a_0t_0=p, t_1=h,\cdots,a_n \ranglet_k=1</tex>.Утверждается, что существуют такое <tex>i</tex>, при этом сделав что <tex>nt_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>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>. Что и требовалось доказать.