Continued Fractions - Periodic Continued Fractions

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 \geq 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}, ∣ r u - t s ∣ = 1

From results on the convergents we have

x = \frac{r}{t} + \frac{ε}{t^{2}} = \frac{s}{u} + \frac{η}{u^{2}}

for some reals $ε, η$ 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 {(\frac{r}{t})}^{2} + b (\frac{r}{t}) + c \\ = & a x^{2} + b x + c - \frac{2 a ε x}{t^{2}} + \frac{a ε^{2}}{t^{4}} - \frac{b ε}{t^{2}} \end{aligned}

Using $a x^{2} + b x + c = 0$ and the triangle inequality yields

∣ A ∣ \leq ∣ 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 = - (\frac{ε u}{t} + \frac{η t}{u}) (2 a x + b) + \frac{2 a ε η}{t u}

Since $r / t, s / u$ are successive convergents, $ε$ and $η$ are opposite in sign, so:

∣ \frac{ε u}{t} + \frac{η t}{u} ∣ \leq ∣ \frac{ε u}{t} - \frac{η t}{u} ∣

From the definitions of $ε$ and $η$ ,

\frac{- r u + s t}{t u} = \frac{ε}{t^{2}} - \frac{η}{u^{2}}

thus $∣ ε u / t - η t / u ∣ = ∣ r u - s t ∣ = 1$ , that is,

∣ B ∣ \leq ∣ 2 a 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} \geq 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} = ⌊ - \frac{1}{y_{k + 1}} ⌋$ .

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.