Continued Fractions

We return to $525$ and $231$. Note that

$$\frac{535}{231} = 2 + \frac{63}{231} = 2 + \frac{1}{\frac{231}{63... ...+ \frac{1}{3 + \frac{42}{63}} = 2 + \frac{1}{3 + \frac{1}{1 + \frac{1}{2}}}.$$

Notation 4  

$$\frac{535}{231} = 2 + \frac{1}{3+} \frac{1}{1+} \frac{1}{2} = \left[2,3,1,2\right] = 2;3,1,2.$$

Note that $2$, $3$, $1$ and $2$ are just the $q_i$'s in the Euclidean algorithm. The rational $\frac{a}{b} > 0$ is written as a continued fraction

$$\frac{a}{b} = q_1 + \frac{1}{q_2 +} \frac{1}{q_3 +} \dots \frac{1}{q_n},$$

with all the $q_i \in \mathbb{N}_0$, $q_i \ge 1$ for $1 < i < n$ and $q_n \ge 2$.

Lemma 6.4.1   Every rational $\frac{a}{b}$ with $a$ and $b \in \mathbb{N}$ has exactly one expression in this form.

Proof. Existance follows immediately from the Euclidean algorithm. As for uniqueness, suppose that

$$\frac{a}{b} = p_1 + \frac{1}{p_2 +} \frac{1}{p_3 +} \dots \frac{1}{p_m}$$

with the $p_i$'s as before. Firstly $p_1 = q_1$ as both are equal to $\lfloor \frac{a}{b} \rfloor$. Since $\frac{1}{p_2 + \frac{1}{\dots}} < 1$ then

$$\left( \frac{a}{b} - p_1 \right)^{-1} = p_2 + \frac{1}{p_3 + \... ...t( \frac{a}{b} - q_1 \right)^{-1} = q_2 + \frac{1}{q_3 + \frac{1}{\dots}}.$$

Thus $p_2 = q_2$ and so on. $\qedsymbol$

Now, suppose that given $[q_1, q_2, \dots, q_n]$ we wish to find $\frac{a}{b}$ equal to it. Then we work out the numbers $A_i$ and $B_i$ as in the Euclidean algorithm. Then $\frac{a}{b} = \frac{A_n}{B_n}$ by lemma (2.22). If we stop doing this after $i$ steps we get $\frac{A_i}{B_i} = [q_1, q_2, \dots, q_i]$. The numbers $\frac{A_i}{B_i}$ are called the ``convergents'' to $\frac{a}{b}$. Using lemma (2.23), we get that $\frac{A_i}{B_i} - \frac{A_{i-1}}{B_{i-1}} = \frac{(-1)^i}{B_{i-1} B_i}$. Now the $B_i$ are strictly increasing, so the gaps are getting smaller and the signs alternate. We get

$$\frac{A_1}{B_1} < \frac{A_3}{B_3} < \dots < \frac{a}{b} < \dots < \frac{A_4}{B_4} < \frac{A_2}{B_2}.$$

The approximations are getting better and better; in fact $\lvert\frac{A_i}{B_i} - \frac{a}{b}\rvert \le \frac{1}{B_i B_{i+1}}$.