Proof about continued fractions

Question

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.

Answer 1

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} $$

Answer 2

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$.