next up previous contents
Next: Continued fractions for irrationals Up: Rational numbers Previous: Rational numbers   Contents

Continued Fractions

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

$\displaystyle \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  

$\displaystyle \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

$\displaystyle \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

$\displaystyle \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

$\displaystyle \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

$\displaystyle \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}}$.
next up previous contents
Next: Continued fractions for irrationals Up: Rational numbers Previous: Rational numbers   Contents
root 2002-06-10