3
$\begingroup$

If you take the continued fraction out of $\sqrt7$, you get [2;1, 1, 1, 4...] which yields: $$2+\frac1{1+\frac1{\frac11+1}}=\frac8{3}$$ and indeed, $$8^2-7⋅3^2=1$$ However, if you take the continued fraction out of $\sqrt13$ you get [3;1, 1, 1, 1, 6...] which yields: $$3+\frac1{1+\frac1{1+\frac1{\frac11+1}}}=\frac{18}5$$ but that gets $$18^2-13⋅5^2=\textbf{-1}$$not $\textbf{1}$ but $\textbf{-1}$! Why? Where is my mistake?

$\endgroup$
  • $\begingroup$ The convergents don't always converge to the root from below, here they oscillate. $\endgroup$ – vonbrand Dec 30 '15 at 19:36
  • $\begingroup$ If the period of the continued fraction is even, you'll get $+1$, if it's odd, it will be $-1$. In that case, the convergents after an even number of periods yield the solutions for $x^2 -dy^2 = +1$. $\endgroup$ – Darth Geek Dec 30 '15 at 19:40
3
$\begingroup$

If you take a prime $p \equiv 1 \pmod 4$ you are guaranteed to get $-1$ first, but get back to $1$ if you repeat the periodic part of the CF.

Note $$18^2 + 13 \cdot 5^2 = 649,$$ $$ 2 \cdot 18 \cdot 5 = 180, $$ $$ 649^2 - 13 \cdot 180^2 = 1. $$

The continued fraction for $\sqrt {13}$ in the display I like. For a convergent $p/q,$ the number directly below is $p^2 - 13 q^2.$ This includes the fake convergent $1/0,$ which needs to be there to start the process.

$$ \small \begin{array}{cccccccccccccccccccccccccccccc} & & 3 & & 1 & & 1 & & 1 & & 1 & & 6 & & 1 & & 1 & & 1 & & 1 & & 6 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{3}{1} & & \frac{4}{1} & & \frac{7}{2} & & \frac{11}{3} & & \frac{18}{5} & & \frac{119}{33} & & \frac{137}{38} & & \frac{256}{71} & & \frac{393}{109} & & \frac{649}{180} & & \frac{4287}{1189} \\ \\ & 1 & & -4 & & 3 & & -3 & & 4 & & -1 & & 4 & & -3 & & 3 & & -4 & & 1 & & -4 \end{array} $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$ $$ 2^2 - 5 \cdot 1^2 = -1,$$ $$2^2 + 5 \cdot 1^2 = 9,$$ $$ 2 \cdot 2 \cdot 1 = 4, $$ $$ 9^2 - 5 \cdot 4^2 = 1. $$ $$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$ $$ 70^2 - 29 \cdot 13^2 = -1,$$ $$70^2 + 29 \cdot 13^2 = 9801,$$ $$ 2 \cdot 70 \cdot 13 = 1820, $$ $$ 9801^2 - 29 \cdot 1820^2 = 1. $$

I put a complete picture for $\sqrt {29}$ at Solving Diophantine Equation - odd Periods

$\endgroup$
  • $\begingroup$ why these $\bigcirc$'s? $\endgroup$ – janmarqz Dec 30 '15 at 20:17
  • $\begingroup$ @janmarqz, just to visually separate the calculations for 13, 5, 29 $\endgroup$ – Will Jagy Dec 30 '15 at 20:29
  • $\begingroup$ Please notice that "p≡1(mod 4)" is not a must, like 99*99 - 58*13*13 == -1 or 43*43 - 74*5*5 and many more. But I have to hugely thank you for helping me with the 66 euler problem! $\endgroup$ – Ran Dec 30 '15 at 21:41
1
$\begingroup$

If $\frac{q_n}{k_n}$ is the nth convergent to the continued fraction, the we have the following equality:

$k_nq_{n-1}-k_{n-1}q_n=(-1)^n$.

So you should choose an even convergent.

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