Number Theory: Lecture 19

In which we study convergents, and make sense of infinite continued fractions.

  • Definition of convergents, and of sequences (p_n) and (q_n).
  • Lemma 58: For n \geq 0, we have \frac{p_n}{q_n} = [a_0, a_1, \dotsc, a_n].  We proved this by induction, using the fact that [a_0, a_1, \dotsc, a_n, a_{n+1}] = [a_0, a_1, \dotsc, a_n + \frac{1}{a_{n+1}}].
  • Lemma 59: For n \geq 1, we have p_n q_{n-1} - p_{n-1} q_n = (-1)^{n+1}.  This was an easy induction using Lemma 58.
  • Lemma 60: If a_0, a_1, …, a_n are all integers, then p_n and q_n are coprime integers.  This was a straightforward consequence of Lemma 59.
  • Proposition 61: We have \frac{p_n}{q_n} \to \theta as n \to \infty.  We derived and used the useful formula that \displaystyle \theta = \frac{\alpha_{n+1} p_n + p_{n-1}}{\alpha_{n+1} q_n + q_{n-1}} and noted that q_n \to \infty as n \to \infty.
  • Lemma 62: We have \displaystyle \frac{1}{q_{n+2}} \leq |q_n \theta - p_n| \leq \frac{1}{q_{n+1}} for all n \geq 0, and so we also have |q_n \theta - p_n| \leq |q_{n-1} \theta - p_{n-1}| for n \geq 1.  In the course of proving Proposition 61, we showed that \displaystyle |q_n \theta - p_n| = \frac{1}{\alpha_{n+1} q_n + q_{n-1}}, and then we found upper and lower bounds for \alpha_{n+1} q_n + q_{n-1}.

Understanding today’s lecture

You could pick some irrational numbers and compute their continued fractions.  Try to avoid using a calculator (that is, try to do it exactly) if you possibly can.  What are their convergents?

Further reading

The usual selection.  Hardy and Wright (An Introduction to the Theory of Numbers) and Baker (A concise introduction to the theory of numbers) both discuss Diophantine approximation via continued fractions, and have some nice material going beyond the topics that we’ll see in lectures.

Preparation for Lecture 20

We’ve seen that continued fractions give a sequence of rational numbers that converge to a given real number (namely the convergents).  Next time we’ll consider these as rational approximations of that real number.  I suggest that you compute some convergents (for some examples that we haven’t seen in lectures), to see whether they give good approximations.  How do they compare with the rational approximations arising from truncating decimal expansions?

Next time we’ll see that in some sense the best rational approximations come from continued fractions.  You could usefully think about how we might formulate that result in a precise way (and, of course, how we might prove it).

We are then going to turn our attention to the Diophantine equation x^2 - Ny^2 = 1 (where N is a fixed integer that isn’t a square, and where we are looking for integer solutions x and y).  Can you find some solutions when N = 2 or N = 3, for example?  It would be good to get a feeling for whether there are no solutions, some but only finitely many solutions, or infinitely many solutions, for different values of N.

(And what happens to the equation x^2 - Ny^2 = 1 when N is a square?  Why have I ruled out that case above?)

About these ads

One Response to “Number Theory: Lecture 19”

  1. Number Theory: Lecture 24 | Theorem of the week Says:

    […] Lemma 76: Let be a convergent for .  Then , and moreover we have .  We proved this using the bound from Lemma 62. […]

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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


Follow

Get every new post delivered to your Inbox.

Join 145 other followers

%d bloggers like this: