Proof about continued fractions Let $p$ be prime with $p \equiv 1 \pmod 4$, and let $u^2 \equiv -1 \pmod p$. Write $u / p$ as a continued fraction $\langle a_0,a_1, \ldots, a_n\rangle$, and let $i$ be the largest integer with $k_i \leq \sqrt{p}$  (the sequence $\{k_n\}$ is defined here.)  Show that $|h_i/k_i - u/p| < 1/(k_i \sqrt{p})$. Furthermore, let $x = k_i$, $y = h_ip - uk_i$, and show that $0 < x^2 + y^2 < 2p$ and $x^2 + y^2 \equiv 0 \pmod p$.
Any suggestions on how to start? I know the formula $\langle a_0;a_1, \ldots, a_{j-1}, a_j\rangle = h_j/k_j$, but I'm not sure how to use it here. I would appreciate some hints to put me in the right direction.
 A: In the sequence of continued fraction approximations, we have
$$
\left|\,\frac{h_i}{k_i}-\frac{h_{i+1}}{k_{i+1}}\,\right|=\frac1{k_i\,k_{i+1}}\tag{1}
$$
Since $\frac up$ is between $\frac{h_i}{k_i}$ and $\frac{h_{i+1}}{k_{i+1}}$, and $k_{i+1}\gt\sqrt{p}$, we have
$$
\begin{align}
\left|\,\frac{h_i}{k_i}-\frac up\,\right|
&\le\frac1{k_i\,k_{i+1}}\\
&\lt\frac1{k_i\sqrt{p}}\tag{2}
\end{align}
$$
Multiplying $(2)$ by $k_ip$ implies that $y^2=(h_ip-uk_i)^2\lt p$. Furthermore, by the choice of $k_i\lt\sqrt{p}$, we have $0\lt x^2=k_i^2\lt p$. This means
$$
0\lt x^2+y^2\lt 2p\tag{3}
$$
Furthermore
$$
\begin{align}
x^2+y^2
&=(h_ip-uk_i)^2+k_i^2\\
&\equiv u^2k_i^2+k_i^2&\pmod{p}\\
&\equiv (u^2+1)\,k_i^2&\pmod{p}\\
&\equiv0&\pmod{p}\tag{4}
\end{align}
$$
A: I figured it out! We have $u / p - h_i/k_i = \frac{(-1)^i}{k_i\left(\xi_{i + 1}k_i + k_{i - 1}\right)} \implies |u / p - h_i/k_i| = \frac{1}{k_i\left(\xi_{i + 1}k_i + k_{i - 1}\right)}$. We are also given that $k_{i + 1} = a_{i + 1}k_i + k_{i - 1}> \sqrt{p}$, but $a_i = \lfloor \xi_i \rfloor \implies a_i \leq \xi_i$, so $\sqrt{p} < a_{i + 1}k_i + k_{i - 1} \leq \xi_{i + 1}k_i + k_{i - 1}$. It then follows that $\frac{1}{k_i\left(\xi_{i + 1}k_i + k_{i - 1}\right)} < \frac{1}{k_i\sqrt{p}}$. For the second part, we have 
$$x^2 + y^2  = (k_i)^2 + (h_ip - uk_i)^2 = k_i^2 + k_i^2p^2 - 2h_ik_iup + u^2k_i^2 \equiv k_i^2 - k_i^2 \equiv 0 \pmod p$$
and using the previous inequality we also get $|uk_i - h_ip| < \sqrt{p} \implies (h_ip - uk_i)^2 < p$, so $x^2 + y^2 < p + k_i^2 \leq p + p= 2p$.
