## Number Theory: Lecture 18

In which we meet continued fractions.

• We finished our proof of Bertrand’s postulate from last time.
• Proposition 56 (Dirichlet): Let $\theta$ be a real number and let $N$ be a natural number.  Then there is a rational $\frac{a}{q}$ with $1 \leq q \leq N$ such that $\left|\theta - \frac{a}{q} \right| \leq \frac{1}{qN}$.  We proved this using the pigeonhole principle.
• Definition of a continued fraction and of partial quotients.  Definition of finite and infinite continued fractions.
• Lemma 57: There is a (natural) bijection between finite continued fractions and rational numbers.  It is clear that a finite continued fraction gives a rational number.  In the other direction, we showed that given a rational number we could obtain its continued fraction, and this is both finite and unique.

#### Understanding today’s lecture

Pick a rational number.  Can you find its continued fraction?  How does this process relate to Euclid’s algorithm?

Our next job will be to think about infinite continued fractions.  Can you find a continued fraction for $\sqrt{2}$?  Is it unique?  If you truncate the continued fraction at some point, you get a finite continued fraction and so a rational number.  How does it compare with $\sqrt{2}$?  Investigating these truncated continued fractions before the next lecture would be very helpful.