Number Theory: Lecture 20

In which we find a connection between continued fractions and Pell‘s equation.

  • Theorem 63: Let n be a natural number.  If p and q are integers with 0 < q < q_n, then |q \theta - p| \geq |q_{n-1} \theta - p_{n-1}|.  So in some sense continued fractions give the best rational approximations.  We proved this by writing p = u p_{n-1} + v p_n and q = u q_{n-1} + v q_n for some integers u and v and arguing from there.
  • Corollary 64: If p is an integer and q is a natural number with \left| \theta - \frac{p}{q} \right| < \frac{1}{2q^2}, then \frac{p}{q} is a convergent for \theta.  We picked n such that q_n \leq q < q_{n+1}, used Theorem 63 to show that \left| \frac{p}{q} - \frac{p_n}{q_n} \right| < \frac{1}{q q_n}, and noted that p q_n - p_n q is an integer.
  • Definition of Pell’s equation x^2 - Ny^2 = 1.
  • Corollary 65: Let N be a natural number that is not a square.  If x and y are positive integers satisfying x^2 - Ny^2 = 1, then \frac{x}{y} is a convergent for \sqrt{N}.  This was straightforward with the help of Corollary 64; we showed that 0 < x - y \sqrt{N} < \frac{1}{2y}.
  • Definition of a quadratic irrational.
  • Definition of an eventually periodic continued fraction.
  • Theorem 66 (Lagrange): A real number \theta is a quadratic irrational if and only if its continued fraction is eventually periodic.  We omitted the proof (but saw a sketch of the ideas).
  • Theorem 67: Let N be a natural number that is not a square.  Then the continued fraction of \sqrt{N} is of the form [a_0; \overline{a_1, a_2, \dotsc, a_2, a_1, 2a_0}].  We omitted the proof.
  • Proposition 68: Let N be a natural number that is not a square.  There are integers x and y such that x^2 - Ny^2 = 1.  We looked at the end of a period in the continued fraction for \sqrt{N}, and made the most of the fact that p_n q_{n-1} - p_{n-1} q_n = (-1)^{n+1} (Lemma 59).

Understanding today’s lecture

It would be good to explore the continued fractions of \sqrt{N} for some explicit values of N; there’s a question on Examples Sheet 3 to encourage you to do this.

You could try to find (integer) solutions to the equation x^2 - 14y^2 = 1.  We’ll discuss this example in the next lecture.

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 cover this material on continued fractions and Pell’s equation (including the proofs that we omitted).

There’s also some nice material related to this on NRICH, based on Conway’s tangles.  There’s an article by Mike Pearson, which starts by mentioning two NRICH problems; I encourage you to try those problems before reading Mike’s article.

The MacTutor biography of Pell (link above) gives more information about ‘his’ equation.  MacTutor summarises his biography by “John Pell was an English mathematician best known for Pell’s equation which in fact he had little to do with”.  Brilliant.

Preparation for Lecture 21

Next time we’ll move on to thinking about primality testing.  That is, given a large number we wish to check (rapidly!) whether it is prime.  In this course so far we’ve seen a few results of the form “If p is prime, then …”, for example Fermat’s Little Theorem and Euler’s criterion.  It would be helpful to go back to those two results in particular, to think about whether the result could hold if p is not prime.  Does either result give us a useful primality test?


One Response to “Number Theory: Lecture 20”

  1. theoremoftheweek Says:

    The spammers seem to be working hard. A spam message (advertising some product or other) posted on this blog reads

    “The term CHINESE REMAINDER THEOREM is found in 1929 in Introduction to the theory of numbers by Leonard Eugene Dickson [James A. Landau].”

    That may even be true. Seems like a lot of work to write a spam post that gets picked up by the spam filter nonetheless…

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: