## Number Theory: Lecture 21

In which we study solutions to Pell’s equation, and start thinking about primality tests.

• Lemma 69: If $(x_1,y_1)$ and $(x_2,y_2)$ are solutions to $x^2 - Ny^2 = 1$, then so is $(x_1 x_2 + y_1 y_2 N, x_1 y_2 + x_2 y_1)$.  We proved this with the help of the observation that $(x_1 \pm y_1 \sqrt{N})(x_2 \pm y_2 \sqrt{N}) = (x_1 x_2 + y_1 y_2 N) \pm (x_1 y_2 + x_2 y_1) \sqrt{N}$.
• Definition of what it means for $n$ to be a (Fermat) pseudoprime to the base $b$.
• Lemma 70: If $n$ is pseudoprime to the bases $b_1$ and $b_2$, then $n$ is pseudoprime to the base $b_1 b_2$ and also to the base $b_1 b_2^{-1}$.  This was straightforward from the definition.
• Lemma 71: If there is a base $b$ to which $n$ is not pseudoprime, then at least half of all bases are such that $n$ is not pseudoprime.  We defined an injective function from the set of bases to which $n$ is pseudoprime to the set of bases to which $n$ is not pseudoprime.
• Definition of a Carmichael number.

I gave out the fourth examples sheet.

#### Understanding today’s lecture

You could pick some examples of Pell’s equation and find solutions.

You could look for some composite numbers that are pseudoprime to various bases.  Perhaps you can set yourself particular challenges (“Can I find a number that is pseudoprime to the base 2?”, for example).

You could look for Carmichael numbers (there are questions to help with this on the examples sheet).

Baker (A concise introduction to the theory of numbers) and Davenport (The Higher Arithmetic) both discuss Pell’s equation and the link with continued fractions.  Koblitz (A Course in Number Theory and Cryptography) has a good section on primality testing and pseudoprimes.  I mentioned the paper of Alford, Granville and Pomerance that shows that there are infinitely many Carmichael numbers (it’s worth reading at least the introduction, if not more).  Andrew Granville wrote a really excellent overview of Carmichael numbers and primality testing for a wider mathematical audience; I strongly encourage you to take a look at it.

Incidentally, Andrew Granville wrote the piece on Analytic Number Theory for the Princeton Companion to Mathematics; I recommend both the book and the article very highly (the article discusses many of the topics we’ve seen in this course, and is available online via that link).

#### Preparation for Lecture 22

Where might we go next?  We used Fermat’s Little Theorem as an example of a result of the form “if $p$ is prime, then …”.  Another such result is Euler’s criterion.  Does that give us anything useful for primality testing?  It would be useful if you tested a few numerical examples, to play around a bit.