Изменения
Нет описания правки
<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>\frac{p}{h}</tex> в цепную дробь <tex>\langle a_0,\cdots,a_n \rangle</tex>.
<tex>P_{n-1}Q_{n-2}-P_{n-2}Q_{n-1}=(-1)^{n}</tex>
<tex>P_{n-2}=(-1)^{n}h</tex>. Берём <tex>n</tex> чётным и получаем <tex>P_{n-2}=h=t1</tex>.
<tex>P_{n-1}=a_{n-1}P_{n-2}+P_{n-3}</tex> ... <tex>P_{n-3}=P_n%P_{n-2}=t2</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>p=t_{\frac{n}{2}}^2+t_{\frac{n}{2}+1}^2</tex>
}}
[[Категория:Теория чисел]]
