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

Ben Lynn blynn@cs.stanford.edu 💡