Rational Numbers and SFCFs are Equivalent

Theorem

Every simple finite continued fraction‎ has a rational value.

Conversely, every rational number can be expressed as a simple finite continued fraction‎.

Proof

Proof that SFCF has a Rational Value

First we prove that any simple finite continued fraction‎ has a rational value.

This will be proved by induction on the number of partial quotients.

For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition that the continued fraction expansion $\left[{a_1, a_2, a_3, \ldots, a_n}\right]$ has a rational value.

Basis for the Induction

• $P(1)$ is true, as $\left[{a_1}\right]$ is an integer and therefore rational.

This is our basis for the induction.

Induction Hypothesis

• Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.

So this is our induction hypothesis:

The continued fraction expansion $\left[{a_1, a_2, a_3, \ldots, a_k}\right]$ has a rational value.

Then we need to show that the continued fraction expansion $\left[{a_1, a_2, a_3, \ldots, a_k, a_{k+1}}\right]$ also has a rational value.

Induction Step

Consider the continued fraction expansion $\left[{a_1, a_2, a_3, \ldots, a_k, a_{k+1}}\right]$.

By the first continued fraction identity:

$\left[{a_1, a_2, a_3, \ldots, a_k, a_{k+1}}\right] = a_1 + \dfrac 1 {\left[{a_2, a_3, \ldots, a_k, a_{k+1}}\right]}$

$a_1$ is an integer, as we have seen.

By the induction hypothesis, so is $\left[{a_2, a_3, \ldots, a_k, a_{k+1}}\right]$, and so is its reciprocal.

Hence as $a_1 + \dfrac 1 {\left[{a_2, a_3, \ldots, a_k, a_{k+1}}\right]}$ is the sum of two rational numbers, it is itself rational.

So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.

Therefore for all $n \in \N^*$, the continued fraction expansion $\left[{a_1, a_2, a_3, \ldots, a_n}\right]$ has a rational value.

$\blacksquare$

Proof that Every Rational Number can be expressed as a SFCF

Let $\dfrac a b$ be a rational number expressed in canonical form.

That is $b > 0$ and $a \perp b = 1$.

By the Euclidean Algorithm, we have:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a\)	\(=\)	\(\displaystyle q_1 b + r_1,\)	\(\displaystyle \)	\(\displaystyle 0 < r_1 < b\)	\(\displaystyle \)	or $\dfrac a b = q_1 + \dfrac {r_1} b$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle b\)	\(=\)	\(\displaystyle q_2 r_1 + r_2,\)	\(\displaystyle \)	\(\displaystyle 0 < r_2 < r_1\)	\(\displaystyle \)	or $\dfrac b {r_1} = q_2 + \dfrac {r_2} {r_1}$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle r_1\)	\(=\)	\(\displaystyle q_3 r_2 + r_3,\)	\(\displaystyle \)	\(\displaystyle 0 < r_3 < r_2\)	\(\displaystyle \)	or $\dfrac {r_2} {r_1} = q_3 + \dfrac {r_3} {r_2}$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\vdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle r_{n-3}\)	\(=\)	\(\displaystyle q_{n-1} r_{n-2} + r_{n-1},\)	\(\displaystyle \)	\(\displaystyle 0 < r_{n-1} < r_{n-2}\)	\(\displaystyle \)	or $\dfrac {r_{n-3} } {r_{n-2} } = q_{n-1} + \dfrac {r_{n-1} } {r_{n-2} }$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle r_{n-2}\)	\(=\)	\(\displaystyle q_n r_{n-1} + 0,\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	or $\dfrac {r_{n-2} } {r_{n-1} } = q_n$

Thus from the system of eqns at the right hand side, we get:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \frac a b\)	\(=\)	\(\displaystyle q_1 + \cfrac 1 {\frac b {r_1} }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle q_1 + \cfrac 1 {q_2 + \cfrac 1 {\frac {r_1} {r_2} } }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle q_1 + \cfrac 1 {q_2 + \cfrac 1 {q_3 + \cfrac 1 {\frac {r_2} {r_3} } } }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle q_1 + \cfrac 1 {q_2 + \cfrac 1 {q_3 + \cfrac 1 {\ddots \cfrac {} {q_{n-1} + \cfrac 1 {q_n} } } } }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

This shows that $\dfrac a b$ has the SFCF $\left[{q_1, q_2, q_3, \ldots, q_n}\right]$.

$\blacksquare$

Note

It can be seen from this proof that there is a close connection between continued fractions and the Euclidean Algorithm.