# Solving Quadratics Using Continued Fractions/Nonsimple to Simple Continued Fractions

Let's say we want to find the continued fraction that solves the equation $x^2 - 2x - 1 = 0$.

Solution: $$x = 2 + \frac1x = 2 + \dfrac1{2 + \dfrac1x} = 2 + \dfrac1{2 + \dfrac1{2 + \dfrac1x}} = [2;\overline2]$$

However, what happens if the quadratic is a bit more complicated, say, $2x^2 - 5x + 1 = 0$. If we use non-simple continued fractions to solve this, we get $$x = \frac52 -\dfrac{\frac12}{\frac52-\dfrac{\frac12}{\frac52-\ddots}} \stackrel{how?}= [ 2; \overline{3, 1, 1} ]$$ My question is: How to convert non-simple continued fractions to simple continued fractions and in general how to solve quadratics using simple continued fractions?

• Note that quadratics have (in general) two solutions, and whatever procedure you use to find a continued fraction, it will only give you one of the two solutions. – Gerry Myerson Jul 8 '18 at 4:02

## 1 Answer

$f(x)=2x^2-5x+1$.

$f(\alpha)=0$ for a number $\alpha$ with $2<\alpha<3$. So $a_0=2$, and $\alpha_1=1/(\alpha-a_0)$ is a zero of $f_1(x)=-x^2f(x^{-1}+2)=x^2-3x-2$.

Then $3<\alpha_1<4$, so $a_1=3$, and $f_2(x)=-x^2f_1(x^{-1}+3)=2x^2-3x-1$.

Then $a_2=1$, and $f_3(x)=-x^2f_2(x^{-1}+1)=2x^2-x-2$.

Then $a_3=1$, and $f_4(x)=-x^2f_3(x^{-1}+1)=x^2-3x-2=f_1(x)$, so from here on it repeats, giving $[2;\overline{3,1,1}]$.

This works not just for quadratics, but for any real algebraic number (although of course it's not periodic for nonquadratics).

Some references:

Cantor et al., A continued fraction algorithm for real algebraic numbers, Math Comp 26 (1972) 785-791.

Lang and Trotter, Continued fractions for soe algebraic numbers, J Reine Angew Math 255 (1972) 112-134; Addendum, 267 (1974) 219-220.

Richtmyer et al., Continued fraction expansions of algebraic numbers, Numer Math 4 (1962) 68-84.

Bombieri and van der Poorten, Continued fractions of algebraic numbers, in Computational Algebra and Number Theory, Sydney, 1992, Math Appl 325 (1995) 137-152.

Brent et al., A comparative study of algorithms for computing continued fractions of algebraic numbers, in Algorithmic Number Theory, Lecture Notes in Computer Science 1122 (Springer, 1996) 35-47.

• Great answer! Do you know if there is an efficient way to convert non-simple (generalized) continued fractions to simple continued fractions. – Misha Shklyar Jul 8 '18 at 14:04
• I was looking for that in the book, Neverending Fractions, by Borwein et al., but I couldn't find it there. Maybe I missed it, or maybe it's in one of Alf van der Poorten's many papers on continued fractions (or maybe it just isn't possible). – Gerry Myerson Jul 8 '18 at 23:17