Every Rational Number is Represented

Proposition 5.1 (Rational continued fractions)   Every nonzero rational number can be represented by a simple continued fraction.

Proof. Without loss of generality we may assume that the rational number is $a/b$ , with $b\geq 1$ and $\gcd(a,b)=1$ . Algorithm 1.1.13 gives:

$$a = b\cdot a_0 + r_1, 0<r_1<b$$

$$b = r_1\cdot a_1 + r_2, 0<r_2<r_1$$

$$\cdots$$

$$r_{n-2} = r_{n-1}\cdot a_{n-1} + r_n, 0<r_n < r_{n-1}$$

$$r_{n-1} = r_n\cdot a_n + 0.$$

Note that $a_i>0$ for $i>0$ (also $r_n=1$ since $\gcd(a,b)=1$ ). Rewrite the equations as follows:

$$a/b = a_0 + r_1/b = a_0 + 1/(b/r_1),$$

$$b/r_1 = a_1 + r_2 / r_1 = a_1 + 1/(r_1/r_2),$$

$$r_1/r_2 = a_2 + r_3 / r_2 = a_2 + 1/(r_2/r_3),$$

$$\cdots$$

$$r_{n-1}/r_n = a_n.$$

It follows that

$$\frac{a}{b} = [a_0,a_1,\ldots, a_n].$$

$\qedsymbol$

The proof of Proposition 5.1.14 leads to an algorithm for computing the continued fraction of a rational number.

A nonzero rational number can be represented in exactly two ways; for example, $2=[1,1] = [2]$ (see Exercise 5.2).