1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Presumably your first line should contain $u$ in place of $x$ (twice), since you define $x$ later. Let $\xi=u/p$ be the number you're taking the continued fraction of. Do you have a formula at hand for the exact value of $|\xi-h_i/k_i|$? $\endgroup$ – Greg Martin Nov 22 '16 at 7:42
  • $\begingroup$ @GregMartin Yes! It is the last thing we learned today :) $\endgroup$ – shmth Nov 22 '16 at 8:00
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.