Purely Periodic Continued Fractions

We've seen that quadratic irrationals correspond to periodic continued fractions. A periodic continued fraction may repeat eventually (like $[1, 2, 3, 4, 3, 4, \ldots]$ ) or repeat from the start (like $[3, 4, 3, 4, \ldots]$ ). In this section, I'll consider the second case.

Definition. A continued fraction of the form $[\overline{a_0, a_1, \ldots a_n}]$ is purely periodic.

I'll derive a criterion for a quadratic irrational to have a purely periodic continued fraction. It is a result of Galois from 1829 ([1]). Recall that if $x = \dfrac{a + b \sqrt{d}}{c}$ is a quadratic irrational, its conjugate is

$\overline{x} = \dfrac{a - b \sqrt{d}}{c}.$

Theorem. Let $x = [a_0, a_1, \ldots]$ be a quadratic irrational. The continued fraction for x is purely periodic if and only if and $-1 < \overline{x} < 0$ .

Proof. ( $\leftarrow$ ) Suppose and $-1 < \overline{x} < 0$ . Using the general continued fraction algorithm and properties of conjugates, I have

$\eqalign{ x_{n + 1} & = \dfrac{1}{x_n - a_n} \cr \noalign{\vskip2pt} \dfrac{1}{x_{n + 1}} & = x_n - a_n \cr \noalign{\vskip2pt} \dfrac{1}{\overline{x_{n + 1}}} & = \overline{x_n} - a_n \cr}$

Note that $a_n \ge 1$ for $n \ge 1$ . But , so $a_0 \ge 1$ . Thus, $a_n \ge 1$ for $n \ge 0$ .

Claim: For all $n \ge 0$ ,

$-1 < \overline{x_n} < 0.$

I'll prove the claim using induction. First, $\overline{x} = \overline{x_0}$ , so by assumption $-1 < \overline{x_0} < 0$ .

Assume that $-1 < \overline{x_n} < 0$ . Then $a_n \ge 1$ gives $-a_n \le -1$ , so adding $\overline{x_n} < 0$ gives

$\eqalign{ \overline{x_n} - a_n & < -1 \cr \noalign{\vskip2pt} \dfrac{1}{\overline{x_{n + 1}}} & < -1 \cr \noalign{\vskip2pt} \overline{x_{n + 1}} & > -1 \cr}$

Since the middle inequality shows $\overline{x_{n + 1}} < 0$ , I have

$-1 < \overline{x_{n + 1}} < 0.$

This proves the claim by induction.

Now

$\eqalign{ \overline{x_n} - a_n & = \dfrac{1}{\overline{x_{n + 1}}} \cr \noalign{\vskip2pt} \overline{x_n} & = \dfrac{1}{\overline{x_{n + 1}}} + a_n \cr}$

Using the claim, I have

$\eqalign{ -1 <\ & \dfrac{1}{\overline{x_{n + 1}}} + a_n < 0 \cr \noalign{\vskip2pt} 1 >\ & \left(-\dfrac{1}{\overline{x_{n + 1}}}\right) - a_n > 0 \cr}$

This inequality says that $-\dfrac{1}{\overline{x_{n + 1}}} > a_n$ , and also that is an integer which differs from $-\dfrac{1}{\overline{x_{n + 1}}}$ by less than 1. It follows that

$a_n = \left[-\dfrac{1}{\overline{x_{n + 1}}}\right].$

Since x is a quadratic irrational, its continued fraction is periodic. Thus, there are indices i and j such that

$x_i = x_j \quad\hbox{where}\quad 0 < i < j.$

Hence,

$\eqalign{ \overline{x_i} & = \overline{x_j} \cr \noalign{\vskip2pt} \left[-\dfrac{1}{\overline{x_i}}\right] & = \left[-\dfrac{1}{\overline{x_j}}\right] \cr \noalign{\vskip2pt} a_{i - 1} & = a_{j - 1} \cr \noalign{\vskip2pt} a_{i - 1} + \dfrac{1}{x_i} & = a_{j - 1} + \dfrac{1}{x_j} \cr \noalign{\vskip2pt} x_{i - 1} & = x_{j - 1} \cr}$

Thus, implies $x_{i - 1} = x_{j - 1}$ . Continuing to reduce indices in this way, I eventually obtain

$x_0 = x_{j - i}.$

Therefore,

$x = x_0 = [\overline{a_0, a_1, \ldots, a_{j - i - 1}}].$

Hence, x is purely periodic.

( $\rightarrow$ ) Suppose x is a quadratic irrational that is purely periodic, so $x = [\overline{a_0, \ldots, a_{n - 1}}]$ , where $a_0, \ldots, a_{n - 1} \in \integer^+$ . Note that $x > a_0 \ge 1$ . I have

$x_n = x = [\overline{a_0, \ldots, a_{n - 1}}].$

Hence,

$x = \dfrac{x_n p_{n - 1} + p_{n - 2}}{x_n q_{n - 1} + q_{n - 2}} = \dfrac{x p_{n - 1} + p_{n - 2}}{x q_{n - 1} + q_{n - 2}}.$

$\eqalign{ q_{n - 1} x^2 + q_{n - 2} x & = p_{n - 1} x + p_{n - 2} \cr q_{n - 1} x^2 + (q_{n - 2} - p_{n - 1}) x - p_{n - 2} & = 0 \cr}$

The quadratic function $f(t) = q_{n - 1} t^2 + (q_{n - 2} - p_{n - 1}) t - p_{n - 2}$ has x and $\overline{x}$ as its roots. I already know ; I need to show $-1 < \overline{x} < 0$ . It's enough to show that f has a root between -1 and 0: Since that root can't be x, it must be $\overline{x}$ .

First, $f(0) = -p_{n - 2} < 0$ . Next,

$\eqalign{ f(-1) & = q_{n - 1} + (p_{n - 1} - q_{n - 2}) - p_{n - 2} \cr & = (a_{n - 1} q_{n - 2} + q_{n - 3}) + (a_{n - 1} p_{n - 2} + p_{n - 3}) - p_{n - 2} - q_{n - 2} \cr & = (a_{n - 1} - 1) p_{n - 2} + (a_{n - 1} - 1) q_{n - 2} + p_{n - 3} + q_{n - 3} \cr & = (a_{n - 1} - 1) (p_{n - 2} + q_{n - 2}) + (p_{n - 3} + q_{n - 3}) \cr & > p_{n - 3} + q_{n - 3} \cr & > 0 \cr}$

Then and implies that there's a root between -1 and 0 by the Intermediate Value Theorem. As noted above, that root must be $\overline{x}$ .

Thus, and $-1 < \overline{x} < 0$ .

For example, $\dfrac{1 + \sqrt{3}}{2}$ satisfies $\dfrac{1 + \sqrt{3}}{2} > 1$ and $-1 < \dfrac{1 - \sqrt{3}}{2} < 0$ . Its continued fraction is

$\dfrac{1 + \sqrt{3}}{2} = [\overline{1, 2}].$

On the other hand, $\sqrt{3} > 1$ , but $-\sqrt{3}$ does not lie between -1 and 0. Its continued fraction is

$\sqrt{3} = [1, \overline{1, 2}].$

To motivate the next result, consider the following example.

Example. (a) Compute the numerators and denominators of the convergents for .

(b) Compute the numerators and denominators of the convergents for .

(a)

$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & a & & p & & q & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 2 & & 2 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 1 & & 3 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 3 & & 11 & & 4 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 1 & & 14 & & 5 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 2 & & 39 & & 14 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 4 & & 170 & & 61 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }}\quad\halmos$

(b)

$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & a & & p & & q & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 4 & & 4 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 2 & & 9 & & 2 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 1 & & 13 & & 3 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 3 & & 48 & & 11 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 1 & & 61 & & 14 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & 2 & & 170 & & 39 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }}\quad\halmos$

Look at the numbers in the last two rows of the tables in the last example. They suggest the following result.

Theorem. Consider the continued fractions

$x = [a_0, a_1, \ldots a_{n - 1}, a_n] \quad\hbox{and}\quad y = [a_n, a_{n - 1}, \ldots a_1, a_0].$

Let and denote the numerator and denominator of the $k^{\rm th}$ convergent for x.

Let and denote the numerator and denominator of the $k^{\rm th}$ convergent for y.

Then:

(a)

$\dfrac{p_n}{p_{n - 1}} = \dfrac{p_n'}{q_n'} \quad\hbox{and}\quad \dfrac{q_n}{q_{n - 1}} = \dfrac{p_{n - 1}'}{q_{n - 1}'} \quad\hbox{for}\quad n \ge 1.$

(b)

$p_n = p_n', \quad p_{n - 1} = q_n', \quad q_n = p_{n - 1}', \quad q_{n - 1} = q_{n - 1}'.$

Remark. By reversing the roles of x and y, it also follows that

$\dfrac{p_n'}{p_{n - 1}'} = \dfrac{p_n}{q_n} \quad\hbox{and}\quad \dfrac{q_n'}{q_{n - 1}'} = \dfrac{p_{n - 1}}{q_{n - 1}}.$

Proof. (a) We'll induct on n. For , consider the convergents tables for and :

$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & a & & p & & q & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & $a_0$ & & $a_0$ & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & $a_1$ & & $a_0 a_1 + 1$ & & $a_1$ & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} \hskip0.5in \vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & a & & p & & q & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & $a_1$ & & $a_1$ & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & $a_0$ & & $a_0 a_1 + 1$ & & $a_0$ & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }}$

Then

$\dfrac{p_1}{p_0} = \dfrac{a_0 a_1 + 1}{a_0} = \dfrac{p_1'}{q_1'},$

$\dfrac{q_1}{q_0} = a_1 = \dfrac{p_0'}{q_0'}.$

The result holds for .

Assume that the result holds for n (that is, that it holds for a fraction with terms and its reverse). I need to prove the result for --- that is, for the fractions $[a_0, a_1, \ldots a_n, a_{n + 1}]$ and $[a_{n + 1}, a_n, \ldots a_1, a_0]$ , I have

$\dfrac{p_{n + 1}}{p_n} = \dfrac{p_{n + 1}'}{q_{n + 1}'} \quad\hbox{and}\quad \dfrac{q_{n + 1}}{q_n} = \dfrac{p_n'}{q_n'}.$

Note that the primed p's and q's are for $[a_{n + 1}, a_n, \ldots a_1, a_0]$ , not for $[a_n, \ldots a_1, a_0]$ .

I have

$\dfrac{p_{n + 1}}{p_n} = \dfrac{a_{n + 1} p_n + p_{n - 1}}{p_n} = a_{n + 1} + \dfrac{p_{n - 1}}{p_n} = a_{n + 1} + \dfrac{1}{\left(\dfrac{p_n}{p_{n - 1}}\right)}.$

I'll apply the induction hypothesis to $[a_0, a_1, \ldots a_n]$ and $[a_n, a_{n - 1}, \ldots a_0]$ . Note that $p_{n - 1}$ and are the same for $[a_0, a_1, \ldots a_n]$ and $[a_0, a_1, \ldots a_n, a_{n + 1}]$ . However, the p's and q's for $[a_{n + 1}, a_n, \ldots a_1, a_0]$ and for $[a_n, \ldots a_1, a_0]$ are different, so I'll use double-primed p's and q's for $[a_n, \ldots a_1, a_0]$ . With this understanding, the induction hypothesis gives

$\dfrac{p_n}{p_{n - 1}} = \dfrac{p_n''}{q_n''} = [a_n, \ldots a_1, a_0].$

Then using the last two equations, I have

$\eqalign{ \dfrac{p_{n + 1}}{p_n} & = a_{n + 1} + \dfrac{1}{\left(\dfrac{p_n}{p_{n - 1}}\right)} \cr \noalign{\vskip2pt} & = a_{n + 1} + \dfrac{1}{[a_n, \ldots a_1, a_0]} \cr \noalign{\vskip2pt} & = [a_{n + 1}, a_n, \ldots a_1, a_0] \cr \noalign{\vskip2pt} & = \dfrac{p_{n + 1}'}{q_{n + 1}'} \cr}$

Similarly,

$\dfrac{q_{n + 1}}{q_n} = \dfrac{a_{n + 1} q_n + q_{n - 1}}{q_n} = a_{n + 1} + \dfrac{q_{n - 1}}{q_n} = a_{n + 1} + \dfrac{1}{\left(\dfrac{q_n}{q_{n - 1}}\right)}.$

By induction,

$\dfrac{q_n}{q_{n - 1}} = [a_n, a_{n - 1}, \ldots a_1].$

$\dfrac{q_{n + 1}}{q_n} = a_{n + 1} + \dfrac{1}{[a_n, a_{n - 1}, \ldots a_1]} = [a_{n + 1}, a_n, \ldots a_1] = \dfrac{p_n'}{q_n'}.$

This proves the result for , so the result holds for all $n \ge 1$ by induction.

(b) Recall that

$p_n q_{n - 1} - p_{n - 1} q_n = (-1)^{n - 1}.$

It follows that $\dfrac{p_n}{p_{n - 1}}$ and $\dfrac{q_n}{q_{n - 1}}$ are in lowest terms. But $\dfrac{p_n'}{q_n'}$ and $\dfrac{p_{n - 1}'}{q_{n - 1}'}$ are convergents of a continued fraction, so they're in lowest terms as well.

$\dfrac{p_n}{p_{n - 1}} = \dfrac{p_n'}{q_n'}$ is an equality between fractions in lowest terms, so and $p_{n - 1} = q_n'$ . Likewise, $\dfrac{q_n}{q_{n - 1}} = \dfrac{p_{n - 1}'}{q_{n - 1}'}$ is an equality between fractions in lowest terms, so $q_n = p_{n - 1}'$ and $q_{n - 1} = q_{n - 1}'$ .

This result relates a finite continued fraction $[a_0, a_1, \ldots a_n]$ and its "reverse" $[a_n, a_{n - 1}, \ldots a_0]$ . The next result (also due to Galois) considers the relationship between the purely periodic continued fractions $[\overline{a_0, a_1, \ldots a_n}]$ and $[\overline{a_n, a_{n - 1}, \ldots a_0}]$ .

Theorem. Let $x = [\overline{a_0, a_1, \ldots a_{n - 1}, a_n}]$ be a purely periodic quadratic irrational. Then $-\dfrac{1}{\overline{x}}$ is purely periodic, and

$-\dfrac{1}{\overline{x}} = [\overline{a_n, a_{n - 1}, \ldots a_1, a_0}].$

Proof. The idea is to show that $[\overline{a_0, a_1, \ldots a_{n - 1}, a_n}]$ and $-\dfrac{1}{[\overline{a_n, a_{n - 1}, \ldots a_1, a_0}]}$ are roots of the same quadratic equation. This implies that they are conjugates.

Let $\dfrac{p_k}{q_k}$ be the $k^{\rm th}$ convergent of x. Then

$x = [\overline{a_0, a_1, \ldots a_{n - 1}, a_n}] = [a_0, a_1, \ldots a_{n - 1}, a_n, x].$

The convergents algorithm gives

$\eqalign{ x & = \dfrac{p_n x + p_{n - 1}}{q_n x + q_{n - 1}} \cr \noalign{\vskip2pt} q_n x^2 + q_{n - 1} x & = p_n x + p_{n - 1} \cr q_n x^2 + (q_{n - 1} - p_n) x - p_{n - 1} & = 0 \cr}$

Let

$y = [\overline{a_n, a_{n - 1}, \ldots a_1, a_0}] = [a_n, a_{n - 1}, \ldots a_1, a_0, y].$

Let $\dfrac{p_k'}{q_k'}$ denote the $k^{\rm th}$ convergent of y. The convergents algorithm gives

$y = \dfrac{p_n' y + p_{n - 1}'}{q_n' y + q_{n - 1}'}.$

By the preceding theorem, , $p_{n - 1}' = q_n$ , $q_n' = p_{n - 1}$ , and $q_{n - 1}' = q_{n - 1}$ . So

$\eqalign{ y & = \dfrac{p_n y + q_n}{p_{n - 1} y + q_{n - 1}} \cr \noalign{\vskip2pt} p_{n - 1} y^2 + q_{n - 1} y & = p_n y + q_n \cr p_{n - 1} y^2 + (q_{n - 1} - p_n) y - q_n & = 0 \cr \noalign{\vskip2pt} p_{n - 1} + (q_{n - 1} - p_n) \left(\dfrac{1}{y}\right) - q_n \left(\dfrac{1}{y}\right)^2& = 0 \cr \noalign{\vskip2pt} q_n \left(-\dfrac{1}{y}\right)^2 + (q_{n - 1} - p_n) \left(-\dfrac{1}{y}\right) - p_{n - 1} & = 0 \cr}$

Thus, x and $-\dfrac{1}{y}$ are roots of the quadratic $q_n t^2 + (q_{n - 1} - p_n) t - p_{n - 1} = 0$ , so they must be conjugates:

$\eqalign{ \overline{x} & = -\dfrac{1}{y} \cr \noalign{\vskip2pt} y & = -\dfrac{1}{\overline{x}} \cr \noalign{\vskip2pt} -\dfrac{1}{\overline{x}} & = [\overline{a_n, a_{n - 1}, \ldots a_1, a_0}] \cr} \quad\halmos$

[1] É. Galois, Démonstration d'un théoréme sur les fractions continues périodiques, Annalles de mathématiques 19 (1828), 294--301.

Contact information

Bruce Ikenaga's Home Page