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?

Further reading

Davenport (The Higher Arithmetic), Baker (A concise introduction to the theory of numbers), and Hardy and Wright (An Introduction to the Theory of Numbers) all have good sections on continued fractions, including material beyond what we’ll cover in lectures.  There are various books on Diophantine approximation (going well beyond this course).  I’ve just read that biography of Wright for the first time — his childhood and early education are well worth reading about.

Preparation for Lecture 19

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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: