# periodic continued fractions represent quadratic irrationals

###### Definition 1.

A periodic simple continued fraction is a simple continued fraction

 $[a_{0},a_{1},a_{2},\ldots]$

such that for some $k\geq 0$ there is $m>0$ such that whenever $r\geq k$, we have $a_{r}=a_{r+m}$. Informally, a periodic continued fraction  is one that eventually repeats. A purely periodic simple continued fraction is one for which $k=0$; that is, one whose repeating period starts with the initial element.

If

 $[a_{0},a_{1},\ldots,a_{k-1},a_{k},\ldots,a_{k+j-1},a_{k},\ldots,a_{k+j-1},a_{k% },\ldots]$

is a periodic continued fraction, we write it as

 $[a_{0},a_{1},\ldots,a_{k-1},\overline{a_{k},\ldots,a_{k+j-1}}].$
###### Theorem 1.

If

 $\alpha=[a_{0},a_{1},\ldots,a_{r},\overline{b_{1},\ldots,b_{t}}]$

is a periodic simple continued fraction, then $\alpha$ is a quadratic irrational $p+q\sqrt{d}$ for $p,q$ rational and $d$ squarefree  . Conversely, every such quadratic irrational is represented by such a continued fraction.

###### Proof.

The forward direction is pretty straightforward. Given such a continued fraction, let $\beta$ be the $(r+1)^{\mathrm{st}}$ complete convergent, i.e.

 $\beta=[\overline{b_{1},\ldots,b_{t}}]$

Note first that $\beta$ must be irrational since the continued fraction for any rational number terminates. Then the article on convergents to a continued fraction shows that

 $\beta=\frac{\beta p_{t}+p_{t-1}}{\beta q_{t}+q_{t-1}}$

where the $p_{i},q_{i}$ are the convergents to the continued fraction for $\beta$. Thus

 $q_{t}\beta^{2}+(q_{t-1}-p_{t})\beta-p_{t-1}=0$

and thus $\beta$ is irrational and satisfies a quadratic equation so is a quadratic irrational. A simple computation then shows that $\alpha$ is as well.

In the other direction, suppose that $\alpha$ is a quadratic irrational satisfying

 $a\alpha^{2}+b\alpha+c=0$
 $\alpha=[a_{0},a_{1},\ldots]$

Then for any $n>0$, we have

 $\alpha=\frac{t_{n}p_{n-1}+p_{n-2}}{t_{n}q_{n-1}+q_{n-2}}$

where the $t_{i}$ are the complete convergents of the continued fraction, so that from the quadratic equation we have

 $A_{n}t_{n}^{2}+B_{n}t_{n}+C_{n}=0$

where

 $\displaystyle A_{n}=ap_{n-1}^{2}+bp_{n-1}q_{n-1}+cq_{n-1}^{2}$ $\displaystyle B_{n}=2ap_{n-1}p_{n-2}+b(p_{n-1}q_{n-2}+p_{n-2}q_{n-1})+2cq_{n-1% }q_{n-2}$ $\displaystyle C_{n}=ap_{n-2}^{2}+bp_{n-2}q_{n-2}+cq_{n-2}^{2}=A_{n-1}$

Note that $A_{n}\neq 0$ for each $n>0$ since otherwise

 $ap_{n-1}^{2}+bp_{n-1}q_{n-1}+cq_{n-1}^{2}=0$

so that

 $a\left(\frac{p_{n-1}}{q_{n-1}}\right)^{2}+b\frac{p_{n-1}}{q_{n-1}}+c=0$

and the quadratic equation would have a rational root, contradicting the fact that $\alpha$ is irrational.

The remainder of the proof is an elaborate computation that shows we can bound each of $A_{n},B_{n},C_{n}$ independent of $n$. Assuming that, it follows that there are only a finite number of possibilities for the triples $(A_{n},B_{n},C_{n})$, so we can choose $n_{1},n_{2},n_{3}$ such that

 $(A_{n_{1}},B_{n_{1}},C_{n_{1}})=(A_{n_{2}},B_{n_{2}},C_{n_{2}})=(A_{n_{3}},B_{% n_{3}},C_{n_{3}})$

Then each of $t_{n_{1}},t_{n_{2}},t_{n_{3}}$ is a root of (say)

 $A_{n_{1}}t^{2}+B_{n_{1}}t+C_{n_{1}}$

so that two of them must be equal. But then $t_{n_{1}}=t_{n_{2}}$ (say), and

 $\displaystyle t_{n_{1}}=[a_{n_{1}},a_{n_{1}+1},\ldots]$ $\displaystyle t_{n_{2}}=[a_{n_{2}},a_{n_{2}+1},\ldots]$

and the continued fraction is periodic.

We proceed to find the bounds. We know that

 $\left\lvert\alpha-\frac{p_{n-1}}{q_{n-1}}\right\rvert<\frac{1}{q_{n-1}^{2}}$

so that

 $\alpha-\frac{p_{n-1}}{q_{n-1}}=\frac{\epsilon}{q_{n-1}^{2}}$

for some $\epsilon$ (depending on $n$) with $\left\lvert\epsilon\right\rvert<1$. Thus

 $\displaystyle A_{n}$ $\displaystyle=ap_{n-1}^{2}+bp_{n-1}q_{n-1}+cq_{n-1}^{2}$ $\displaystyle=a\left(\alpha q_{n-1}+\frac{\epsilon}{q_{n-1}}\right)^{2}+bq_{n-% 1}\left(\alpha q_{n-1}+\frac{\epsilon}{q_{n-1}}\right)+cq_{n-1}^{2}$ $\displaystyle=(a\alpha^{2}+b\alpha+c)q_{n-1}^{2}+2a\alpha\epsilon+a\frac{% \epsilon^{2}}{q_{n-1}^{2}}+b\epsilon$ $\displaystyle=2a\alpha\epsilon+a\frac{\epsilon^{2}}{q_{n-1}^{2}}+b\epsilon$

so that

 $\left\lvert A_{n}\right\rvert=\left\lvert 2a\alpha\epsilon+a\frac{\epsilon^{2}% }{q_{n-1}^{2}}+b\epsilon\right\rvert<2\left\lvert a\alpha\right\rvert+\left% \lvert a\right\rvert+\left\lvert b\right\rvert$

and thus also

 $\left\lvert C_{n}\right\rvert<2\left\lvert a\alpha\right\rvert+\left\lvert a% \right\rvert+\left\lvert b\right\rvert$

It remains to bound $B_{n}$. But

 $B_{n}^{2}-4A_{n}C_{n}=(2A_{n}t_{n}+B_{n})^{2}$

Substituting the values of $A_{n},B_{n}$ on the right, and using the fact that

 $t_{n}=-\frac{p_{n-2}-xq_{n-2}}{p_{n-1}-xq_{n-1}}$

we get after a computation

 $\displaystyle\sqrt{B_{n}^{2}-4A_{n}C_{n}}$ $\displaystyle=(p_{n-1}q_{n-2}-p_{n-2}q_{n-1})\frac{2axp_{n-1}+bp_{n-1}+bxq_{n-% 1}+2cq_{n-1}}{p_{n-1}-xq_{n-1}}$ $\displaystyle=\pm\frac{(2ax+b)p_{n-1}+(2ax^{2}+2bx+2c)q_{n-1}-(2ax^{2}+bx)q_{n% -1}}{p_{n-1}-xq_{n-1}}$ $\displaystyle=\pm\frac{(p_{n-1}-xq_{n-1})(2ax+b)}{p_{n-1}-xq_{n-1}}=\pm(2ax+b)$

so that

 $B_{n}^{2}-4A_{n}C_{n}=(2ax+b)^{2}=b^{2}-4ac$

Thus

 $B_{n}^{2}\leq 4\left\lvert A_{n}C_{n}\right\rvert+\left\lvert b^{2}-4ac\right% \rvert<4(2\left\lvert a\alpha\right\rvert+\left\lvert a\right\rvert+\left% \lvert b\right\rvert)^{2}+\left\lvert b^{2}-4ac\right\rvert$

and we have thus bounded all of $A_{n},B_{n},C_{n}$ independent of $n$. ∎

## References

• 1 G.H. Hardy & E.M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford Science Publications, 1979.
Title periodic continued fractions represent quadratic irrationals PeriodicContinuedFractionsRepresentQuadraticIrrationals 2013-03-22 18:04:40 2013-03-22 18:04:40 rm50 (10146) rm50 (10146) 9 rm50 (10146) Theorem msc 11Y65 msc 11A55 periodic continued fraction purely periodic