Skip to main content

Section 11.1 Finite Continued Fractions

We return to the example of the last chapter. Note that \(\gcd(21, 13) = 1\) since they are consecutive Fibonacci numbers. We have from the last chapter that

\begin{align*} 21 \amp= 1\cdot 13+8\\ 13 \amp= 1\cdot 8+5\\ 8 \amp= 1\cdot 5+3\\ 5 \amp= 1\cdot 3+2\\ 3 \amp= 1\cdot 2+1\\ 2 \amp= 2\cdot 1. \end{align*}

We can change this to be in terms of fractions. Note that we have

\begin{align*} \frac{21}{13} \amp= 1+\frac{1}{\frac{13}{8}}\\ \frac{13}{8} \amp= 1+\frac{1}{\frac{8}{5}}\\ \frac{8}{5} \amp= 1+\frac{1}{\frac{5}{3}}\\ \frac{5}{3} \amp= 1+\frac{1}{\frac{3}{2}}\\ \frac{3}{2} \amp= 1+\frac{1}{\frac{1}{2}}\\ \frac{2}{1} \amp= 2. \end{align*}

Substituting up we have that

\begin{equation*} \dfrac{21}{13}=1+\dfrac{1} {1+\dfrac{1} {1+\dfrac{1} {1+\dfrac{1} {1+\dfrac{1}{2} }}}} \end{equation*}

The above is called a finite continued fraction.

Definition 11.1.1.

A finite continued fraction is a fraction of the form

\begin{equation*} a_0+\dfrac{1} {a_1+\dfrac{1} {a_2+\dfrac{1} {a_3+\dfrac{1} {a_4+\dfrac{1}{\ddots +\dfrac{1} {a_{n-1}+\dfrac{1}{a_n} }}}}}} \end{equation*}

where \(a_0, a_1,..., a_n\) are real numbers, all of which except possibly \(a_0\) are positive. The numbers \(a_1, a_2,..., a_n\) are the partial quotients of this fraction. Such a fraction is called simple if all the \(a_i\) are integers.

We note that we have

Let \(a/b\) with \(b \neq 0\) be a rational number. Using Euclid's algorithm for finding the greatest common divisor we have a system of equations

\begin{align*} a \amp = ba_0 + r_1 \hspace{20mm} 0 \lt r_1 \lt b\\ b \amp = r_1a_1 + r_2 \hspace{18mm} 0 \lt r_2 \lt r_1\\ r_1 \amp = r_2a_2 + r_3 \hspace{18mm} 0 \lt r_3 \lt r_2\\ \amp \vdots \\ r_{n-2} \amp = r_{n-1}a_{n-1} + r_n \hspace{8.5mm} 0 \lt r_n \lt r_{n-1}\\ r_{n-1} \amp = r_na_n + 0. \end{align*}

where \(r_n = \gcd(a, b).\) Writing the system a little differently we have

\begin{align*} \frac{a}{b} \amp= a_0+\frac{1}{\frac{b}{r_1}}\\ \frac{b}{r_1} \amp= a_1+\frac{1}{\frac{r_1}{r_2}}\\ \frac{r_1}{r_2} \amp= 1+\frac{1}{\frac{r_2}{r_3}}\\ \amp \vdots \\ \frac{r_{n-1}}{r_n} \amp= a_n. \end{align*}

Substituting up (or down if we wish) we have

\begin{equation*} \frac{a}{b}=a_0+\dfrac{1} {a_1+\dfrac{1} {a_2+\dfrac{1} {a_3+\dfrac{1} {a_4+\dfrac{1}{\ddots +\dfrac{1} {a_{n-1}+\dfrac{1}{a_n} }}}}}} \end{equation*}

This proof also gives us a way to find the simple continued fraction for a rational number.

Try \(67/24.\) Just use Euclidean algorithm and the above method.

As you may have noticed, writing out a continued fraction takes a lot of space, so we will opt for a more condensed form; that is, write \([a_0; a_1, a_2,..., a_n]\) for the continued fraction. For example, we have

\begin{equation*} \frac{21}{13}= [1; 1, 1, 1, 1, 2] = [1; 1, 1, 1, 1, 1, 1]. \end{equation*}

As a consequence of the last chapter we have that the ratios of consecutive Fibonacci numbers all have the form

\begin{equation*} \frac{f_{n+1}}{f_n}= [1; 1, 1, . . . , 1, 1] \end{equation*}

where the integer \(1\) appears \(n\) times.