# Problem in a Pell equation

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?

• The convergents don't always converge to the root from below, here they oscillate. – vonbrand Dec 30 '15 at 19:36
• 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$. – Darth Geek Dec 30 '15 at 19:40

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

• why these $\bigcirc$'s? – janmarqz Dec 30 '15 at 20:17
• @janmarqz, just to visually separate the calculations for 13, 5, 29 – Will Jagy Dec 30 '15 at 20:29
• 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! – Ran Dec 30 '15 at 21:41

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.