Periodic Continued Fractions

A continued fraction \([a_1;a_2,...]\) is periodic if the sequence eventually repeats, i.e there exists some \(m, n\) with \(a_{m + i} = a_{n+i}\) for all \(i \ge 0\). Our first example of a continued fraction, \([1;2,2,...]\), is periodic and turned out to be \(\sqrt{2}\). In fact:

Theorem: Any periodic continued fraction represents a root of a quadratic equation with integer coefficients.

Proof: Let \(x_k = [a_k; a_{k+1}, ...]\). For some \(m < n\) we have \(x_m = x_n\). Let \(p'_i , q'_i\) be the convergents of \(x_n\). Then

\[ x_m = x_n = \frac{p'_{n-m-1}x_m - p'_{n-m-2}}{q'_{n-m-1} x_m - q'_{n-m-2}} \]

thus \(x_m\) satisfies a quadratic equation with integer coefficients.

As \(x_1 = \frac{p_{m-1}x_m + p_{m-2}}{q_m-1 x_m +q_{m-2}}\) the same is true for \(x_1\).∎

The converse is also true:

Theorem: An irrational root of a \(a x^2 + b x + c = 0\) where \(a,b,c\) are integers has a periodic continued fraction expansion.

Proof: Let \(x\) be an irrational root with continued fraction expansion \([a_1; a_2, ...]\), and define \(x_k = [a_k; a_{k+1}, ...]\). Recall \(x = \frac{x_k p_{k-1} + p_{k-2}}{x_k q_{k-1} + q_{k-2}}\), which we relabel as

\[ x = \frac{r z + s}{t z + u } , \left| r u - t s \right| = 1 \]

From results on the convergents we have

\[ x = \frac{r}{t} + \frac{\epsilon}{t^2} = \frac{s}{u} + \frac{\eta}{u^2} \]

for some reals \(\epsilon , \eta\) of absolute value less than 1.

Substituting \( x = \frac{r z + s}{t z + u } \) into the quadratic gives \(A z^2 + B z + C = 0\) where

\[ \begin{aligned} A &=& a r^2 + b r t + c t^2 \\ B &=& 2 a r s + b(r u + t s) + 2 c t u \\ C &=& a s^2 + b s u + c u^2 \end{aligned} \]

If we show \(A, B, C\) are bounded, that is, their magnitude is less than some positive integer depending only on \(x\), then \(z\) can be a solution of only a finite number of quadratic equations. Then as \(x\) is irrational, the continued fraction expansion is infinite, and since \(z\) can only take finitely many possible values, eventually the fraction repeats itself.

Firstly,

\[ \begin{aligned} \frac{A}{t^2} &=& a\left(\frac{r}{t}\right)^2 + b\left(\frac{r}{t}\right) + c \\ & = & a x^2 + b x + c - \frac{2 a \epsilon x}{t^2} + \frac{a \epsilon^2}{t^4} - \frac{b \epsilon}{t^2} \end{aligned} \]

Using \(a x^2 + b x + c = 0\) and the triangle inequality yields

\[ |A| \le |2 a x| + |a| + |b| \]

showing \(A\) is bounded. Replacing \(r,t\) with \(s, u\) shows \(C\) is bounded.

As for \(B\), we can either show \(4 A C - B^2 = 4 a c - b^2\) by direct computation or that

\[ B = - \left( \frac{\epsilon u}{t} + \frac {\eta t}{u}\right)(2 a x + b ) + \frac{2 a \epsilon\eta}{t u} \]

Since \(r/t, s/u\) are successive convergents, \(\epsilon\) and \(\eta\) are opposite in sign, so:

\[ \left|\frac{\epsilon u}{t} + \frac{\eta t}{u}\right| \le \left|\frac{\epsilon u}{t} - \frac{\eta t}{u}\right| \]

From the definitions of \(\epsilon\) and \(\eta\),

\[ \frac{-r u + s t}{t u} = \frac{\epsilon}{t^2} - \frac{\eta}{u^2} \]

thus \(|\epsilon u/t - \eta t / u| = |r u - s t | = 1\), that is,

\[ |B| \le |2a x + b| + |2 a| ∎ \]

Pure Periodicity

Suppose \(a = [a_1; a_2, ..., a_k, a_1, a_2, ..., a_k,...]\). Then \(a = \frac{p_k a + p_{k-1}}{q_k a + q_{k-1}}\) so \(a\) must be a root of

\[ q_k x^2 + (q_{k-1} - p_k)x - p_{k-1} = 0 \]

The left-hand side takes a negative value when \(x = 0\), and a positive value when \(x = -1\), thus a root lies in the interval \((-1..0)\) and it is the conjugate of \(a\).

A positive root of a quadratic equation with integer coefficients is called a reduced quadratic surd if it is greater than 1 and its conjugate lies in \((-1..0)\).

Theorem: A real \(a\) has a pure periodic fraction expansion if and only if \(a\) is a reduced quadratic surd.

Proof: We have just seen the proof for one direction. As for the other, let let \(f(x)\) be a quadratic equation for which \(a\) is reduced quadratic surd. Let \(a = [a_1; a_2, ...]\). Define \(x_k = [a_k; a_{k+1}, ...]\), Let \(y_1\) be the conjugate of \(a\).

Considering \(f(a_1+\frac{1}{x_2}) = 0\) gives a quadratic equation for \(x_2\). Let \(y_2\) be the other solution, the conjugate of \(x_2\). We have \(f(y_1) = 0\) and \(f(a_1 +\frac{1}{y_2}) = 0\). Since neither root is equal to \(x_1\), and quadratic equations have two roots, we have \(y_1 - \frac{1}{y_2} = a_1\). Since \(a_1 \ge 1\) and \(y_1 > 0\) we see \(-1 < y_2 < 0\), hence \(x_2\) is also a reduced quadratic surd. Inducting shows \(x_k\) is a reduced quadratic surd for all \(k\), and that \(y_k = a_k + \frac{1}{y_{k+1}}\).

Since \(0 < -y_k < 1\), this last equation implies \(a_k = \left\lfloor - \frac{1}{y_{k+1}} \right\rfloor\).

Now suppose the continued fraction expansion for \(a\) repeats at \(a_r = a_{r+k}\) for some \(k\) and \(r > 1\). Then \(x_r = x_{r+k}\) and \(y_r = y_{r+k}\), and hence \(a_{r-1} = a_{r+k-1}\). Repeating the argument gives \(a = [a_1; a_2,..., a_k, a_1, ...] ∎\)

Corollary: The continued fraction expansion of \(\sqrt{D}\) where \(D\) is a nonsquare positive integer has the form \([a_1; a_2, ..., a_k, a_2, ..., a_k, ...]\)

The same can be said for any positive real of the form \(\sqrt{D} + n\) where \(n\) is an integer and \(D\) is a nonsquare positive integer.

Ben Lynn blynn@cs.stanford.edu 💡

Periodic Continued Fractions

Pure Periodicity

Contents