Finite Continued Fractions and Rational Numbers

# Finite Continued Fractions and Rational Numbers

Consider the pair of numbers $54$ and $12$. We can use the Euclidean algorithm to find $(54, 10)$. We have that:

(1)
\begin{align} \quad 54 &= 5(10) + 4 \\ 10 &= 4(2) +2 \\ 4 &= 2(2) + 0 \end{align}

From the first equation we get that:

(2)
\begin{align} \quad \frac{54}{10} &= 5 + \frac{4}{10} \\ &= 5 + \frac{1}{\frac{10}{4}} \end{align}

From the second equation we have that $\frac{10}{4} = 2 + \frac{2}{4}$. Plugging this into the equation above gives us:

(3)
\begin{align} \quad \frac{54}{10} &= 5 + \frac{1}{2 + \frac{2}{4}} \\ &= 5 + \frac{1}{2 + \frac{1}{\frac{4}{2}}} \end{align}

From the third equation we have that $\frac{4}{2} = 2$. Plugging this into the equation above gives us:

(4)
\begin{align} \quad \frac{54}{10} = 5 + \frac{1}{2 + \frac{1}{2}} \end{align}

From this, we see that the rational number $\frac{54}{10}$ can be represented by the simple continued fraction $\langle 5; 2, 2 \rangle$. For any rational number $\frac{a}{b}$ we can use the Euclidean algorithm to find $(a, b)$ and then obtain a continued fraction for $\frac{a}{b}$. On the other hand, given any finite simple continued fraction $\langle x_0; x_1, ..., x_n \rangle$ it is clear that it represents a rational number by simplification. We summarize these results in the following proposition.

 Proposition 1: Every rational number $\frac{a}{b} \in \mathbb{Q}$ can be represented by a finite simple continued fraction. Moreover, every finite simple continued fraction $\langle x_0; x_1, ..., x_n \rangle$ represents a rational number.

Now also observe that from the equation above, we can go one step further and have that:

(5)
\begin{align} \quad \frac{54}{10} = 5 + \frac{1}{2 + \frac{1}{1 + \frac{1}{1}}} \end{align}

And so $\frac{54}{10}$ can also be represented by the simple continued fraction $\langle 5; 2, 1, 1 \rangle$.

In general, if $\langle x_0; x_1, ..., x_n \rangle$ is a continued fraction for $\frac{a}{b}$ then so is $\langle x_0; x_1, ..., x_n - 1, 1 \rangle$.