In which we find a link between continued fractions and Pell’s equation.
- Theorem 63: Let be a natural number, and let have convergents . If and are integers with , then . (So .) The key idea of the proof was to find a way to link and (about which we know very little) with , , and (about which we know quite a lot). We were able to do this by finding integers and such that and . By thinking about the signs of and (which must be different), we were able to obtain a lower bound for .
- Corollary 64: If is an integer and is a natural number with , then is a convergent for . This is one of those proofs that becomes easier if you try to prove something slightly stronger. We showed that if and , then , and so .
- Definition of Pell’s equation (where is a fixed natural number that is not a square, and we are interested in integer solutions for and ).
- Corollary 65: Let be a natural number that is not a square. If and are positive integers satisfying Pell’s equation , then is a convergent for . This follows nicely from the previous result.
- Theorem 66 (Lagrange): The continued fraction of is eventually periodic if and only if is a quadratic irrational. We did not prove this in the lecture, but saw an outline of some of the ideas of the proof.
- Theorem 67: Let be a natural number that is not a square. Then has a continued fraction of the form . We did not prove this either.
- Proposition 68: Let be a natural number that is not a square. Then there are integers and such that . We showed that there is a convergent for such that , namely the convergent at the end of either the first or second period.
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.
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.
Preparation for Lecture 21
Next time we’ll be 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 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 is not prime. Does either result give us a useful primality test?