Number Theory: Lecture 20

In which we find a link between continued fractions and Pell’s equation.

Theorem 63: Let $n$ be a natural number, and let $\theta$ have convergents $\frac{p_k}{q_k}$ . If $p$ and $q$ are integers with $0 < q < q_n$ , then $|q \theta - p| \geq |q_{n-1} \theta - p_{n-1}|$ . (So $|q\theta - p| \geq | q_n \theta - p_n|$ .) The key idea of the proof was to find a way to link $p$ and $q$ (about which we know very little) with $p_{n-1}$ , $q_{n-1}$ , $p_n$ and $q_n$ (about which we know quite a lot). We were able to do this by finding integers $u$ and $v$ such that $p = u p_{n-1} + v p_n$ and $q = u q_{n-1} + v q_n$ . By thinking about the signs of $u$ and $v$ (which must be different), we were able to obtain a lower bound for $|q \theta - p|$ .
Corollary 64: If $p$ is an integer and $q$ is a natural number with $|\theta - \frac{p}{q}| < \frac{1}{2q^2}$ , then $\frac{p}{q}$ is a convergent for $\theta$ . This is one of those proofs that becomes easier if you try to prove something slightly stronger. We showed that if $q_n \leq q < q_{n+1}$ and $| \theta - \frac{p}{q}| < \frac{1}{2q^2}$ , then $| \frac{p}{q} - \frac{p_n}{q_n}| < \frac{1}{q q_n}$ , and so $\frac{p}{q} = \frac{p_n}{q_n}$ .
Definition of Pell’s equation $x^2 - Ny^2 = 1$ (where $N$ is a fixed natural number that is not a square, and we are interested in integer solutions for $x$ and $y$ ).
Corollary 65: Let $N$ be a natural number that is not a square. If $x$ and $y$ are positive integers satisfying Pell’s equation $x^2 - Ny^2 = 1$ , then $\frac{x}{y}$ is a convergent for $\sqrt{N}$ . This follows nicely from the previous result.
Theorem 66 (Lagrange): The continued fraction of $\theta$ is eventually periodic if and only if $\theta$ 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 $N$ be a natural number that is not a square. Then $\sqrt{N}$ has a continued fraction of the form $[a_0; \overline{a_1, a_2, \dotsc, a_2, a_1, 2a_0}]$ . We did not prove this either.
Proposition 68: Let $N$ be a natural number that is not a square. Then there are integers $x$ and $y$ such that $x^2 - Ny^2 = 1$ . We showed that there is a convergent $\frac{p_n}{q_n}$ for $\sqrt{N}$ such that $p_n^2 - N q_n^2 = 1$ , namely the convergent at the end of either the first or second period.

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 $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?

Like this:

Be the first to like this post.

This entry was posted on November 21, 2011 at 12:10 pm and is filed under Cambridge Maths Tripos, II Number Theory, Lecture. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Number Theory: Lecture 20”

Joseph McCullough Says:
November 22, 2011 at 10:01 pm
I’m really looking forward to the primality testing. I haven’t read up on that in a long time, and it’ll be nice to see a fresh perspective on it.

Theorem of the week