Periodic Continued Fractions


Definition. A quadratic irrational is an irrational number which is a root of a quadratic equation

$$ax^2 + bx + c = 0, \quad a, b, c \in \integer, \quad a \ne 0.$$

Lemma. A number is a quadratic irrational if and only if it can be written in the form $\dfrac{p +
   \sqrt{q}}{r}$ , where $p, q, r \in \integer$ , $r \ne 0$ , and q is positive and not a perfect square.

Proof. Suppose x is a quadratic irrational. Then x is a root of

$$ax^2 + bx + c = 0, \quad a, b, c \in \integer, a \ne 0.$$

By the quadratic formula,

$$x = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}.$$

$-b$ , $b^2 - 4ac$ , and $2a$ are integers, and $2a \ne 0$ , since $a \ne 0$ .

If $b^2 - 4ac =
   0$ , then $x = -\dfrac{b}{2a}$ , which is a rational number, contrary to assumption.

If $b^2 - 4ac <
   0$ , then x is complex, again contrary to assumption.

Hence, $b^2 - 4ac
   > 0$ .

Finally, if $b^2 -
   4ac$ is a perfect square, then $x = \dfrac{-b \pm
   \sqrt{b^2 - 4ac}}{2a}$ is rational. Hence, $b^2 - 4ac$ is not a perfect square.

For the converse, suppose $x = \dfrac{p +
   \sqrt{q}}{r}$ , where $p, q, r \in \integer$ , $r \ne 0$ , and q is positive and not a perfect square. Then

$$rx - p = \sqrt{q}, \quad (rx - p)^2 = q, \quad r^2x^2 - 2rpx + (p^2 - q) = 0.$$

This is a quadratic equation with integer coefficients, and $r^2 \ne 0$ since $r \ne 0$ . Therefore, x is a quadratic irrational.

Theorem. (Lagrange) The quadratic irrationals are exactly the real numbers which can be represented by infinite periodic continued fractions.

I'm going to prove one direction --- that periodic continued fractions are quadratic irrationals. I need a series of lemmas; the lemmas are motivated by the informal procedure of the following example.


Example. Consider $x = [5; 2, 1, 2, 2, 1,
   2, 2, \ldots] = [5; 2, \overline{1, 2, 2}]$ .

I'll write x in closed form. Let $y = [\overline{1, 2,
   2}]$ . Then

$$x = 5 + \dfrac{1}{2 + \dfrac{1}{y}}.$$

On the other hand,

$$y = 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{y}}}.$$

After some simplification, I get

$$5y^2 - 5y - 3 = 0, \quad y = \dfrac{5 \pm \sqrt{37}}{10}.$$

y must be positive, so $y = \dfrac{5 + \sqrt{37}}{10}$ . Therefore,

$$x = 5 + \dfrac{1}{2 + \dfrac{1}{\dfrac{5 + \sqrt{37}}{10}}} = \dfrac{643 + 5\sqrt{37}}{126}.\quad\halmos$$


The idea of the lemmas is simply to emulate the algebra I just did.

Lemma 1. If x is a quadratic irrational and $a_0$ is an integer, then $a_0 + \dfrac{1}{x}$ is a quadratic irrational.

Proof. Write $x = \dfrac{a +
   \sqrt{b}}{c}$ , where $a, b, c \in \integer$ , $c \ne 0$ , and b is positive and not a perfect square. Then

$$a_0 + \dfrac{1}{x} = a_0 + \dfrac{1}{\dfrac{a + \sqrt{b}}{c}} = a_0 + \dfrac{c}{a + \sqrt{b}} = \dfrac{(a_0a^2 + ac - a_0b) - c\sqrt{b}}{a^2 - b}.$$

(I've suppressed the ugly algebra involved in combining the fractions and rationalizing the denominator.) The last expression is a quadratic irrational; note that $a^2 - b \ne 0$ , because b is not a perfect square.

Lemma 2. If x is a quadratic irrational and $a_0, a_1, \ldots,
   a_n$ are integers, then

$$\matrix{a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \vphantom{\dfrac{1}{a_3}}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_n + \dfrac{1}{x}} \cr}$$

is a quadratic irrational.

Proof. I'll use induction. The case $n = 0$ was done in Lemma 1.

Suppose $n > 0$ , and suppose the result is true for $n - 1$ . Then in

$$\matrix{a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \vphantom{\dfrac{1}{a_3}}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_n + \dfrac{1}{x}} \cr}, \quad\hbox{the subfraction}\quad \matrix{a_1 + \dfrac{1}{a_2 + \vphantom{\dfrac{1}{a_3}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_n + \dfrac{1}{x}} \cr}$$

is a quadratic irrational by the induction hypothesis.

But the original fraction is just $a_0 +
   \dfrac{1}{(\hbox{the subfraction})}$ , so it's a quadratic irrational by Lemma 1. This completes the induction step, so the result is true for all $n \ge 0$ .

Lemma 3. Let $a_0, a_1, \ldots, a_n
   \in \integer$ . Then

$$\matrix{a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \vphantom{\dfrac{1}{a_3}}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_n + \dfrac{1}{x}} \cr}, \quad\hbox{can be written as}\quad \dfrac{ax + b}{cx + d},$$

where $a, b, c, d
   \in \integer$ .

Proof. Your experience with algebra should tell you this is obvious, but I'll give the proof by induction anyway.

For $n = 0$ , I have

$$a_0 + \dfrac{1}{x} = \dfrac{a_0x + 1}{x}.$$

This has the right form.

Take $n > 0$ , and assume the result is true for $n - 1$ . Then in

$$\matrix{a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \vphantom{\dfrac{1}{a_3}}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_n + \dfrac{1}{x}} \cr}, \quad\hbox{the subfraction}\quad \matrix{a_1 + \dfrac{1}{a_2 + \vphantom{\dfrac{1}{a_3}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_n + \dfrac{1}{x}} \cr}$$

can be written as $\dfrac{ax + b}{cx + d}$ , $a, b, c, d \in
   \integer$ , by induction.

The original fraction is therefore

$$a_0 + \dfrac{1}{\dfrac{ax + b}{cx + d}} = \dfrac{(a_0a + c)x + (a_0b + d)}{ax + b}.$$

(I've suppressed some easy but ugly algebra again.) The last fraction is in the right form, so this completes the induction step. The result is therefore true for all $n \ge 0$ .

I'm ready to prove that periodic continued fractions are quadratic irrationals. First, I'll consider those that start repeating immediately.

Lemma 4. If $a_0, a_1, \ldots, a_n
   \in \integer$ , then

$$x = [\overline{a_0; a_1, \ldots, a_n}]$$

is a quadratic irrational.

Proof. First, x is irrational, because it is an {\it infinite} continued fraction.

By Lemma 3,

$$x = [\overline{a_0; a_1, \ldots, a_n}] = [a_0; a_1, \ldots, a_n, x] = \dfrac{ax + b}{cx + d},$$

where $a, b, c, d
   \in \integer$ .

Hence,

$$cx^2 + dx = ax + b, \quad cx^2 + (d - a)x - b = 0.$$

Therefore, x is a quadratic irrational.

In the general case, the fraction does not start repeating immediately.

Proposition. If $b_0, b_1, \ldots, b_m,
   a_0, a_1, \ldots, a_n \in \integer$ , then

$$x = [b_0; b_1, \ldots, b_m, \overline{a_0, a_1, \ldots, a_n}]$$

is a quadratic irrational.

Proof. $[\overline{a_0, a_1,
   \ldots, a_n}]$ is a quadratic irrational by Lemma 4. Therefore,

$$x = [b_0; b_1, \ldots, b_m, x]$$

is a quadratic irrational by Lemma 2.

The converse states the quadratic irrationals give rise to periodic continued fractions. I won't give the proof; however, here's an example which shows how you can go from a quadratic equation to a periodic continued fraction (at least in this case).


Example. Suppose x is a quadratic irrational satisfying $x^2 +
   x - 1 = 0$ . Rewrite the equation as

$$x(x + 1) - 1 = 0, \quad\hbox{and then}\quad x = \dfrac{1}{1 + x}.$$

Now substitute $x
   = \dfrac{1}{1 + x}$ for x in the right side:

$$x = \dfrac{1}{1 + \dfrac{1}{1 + x}}.$$

Do it again:

$$x = \dfrac{1}{1 + \dfrac{1}{1 + \dfrac{1}{1 + x}}}.$$

It's clear that you can keep going, and so $x = [0;
   \overline{1}]$ .


Contact information

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga