periodic continued fractions represent quadratic irrationals

This article shows that infinite simple continued fractions that are eventually periodic correspond precisely to quadratic irrationals.

Throughout, we will freely use results on convergents to a continued fraction; see that article for details.

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.

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

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

and with continued fraction representation

\\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}\eq 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.