Periodic Continued Fractions

A periodic 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 \lt 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 there is root in $(-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 \gt 0$ we see $-1 \lt y_2 \lt 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 \lt -y_k \lt 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 \gt 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.