In which we study solutions to Pell’s equation, and start thinking about primality tests.
- Lemma 69: If and are solutions to , then so is . We proved this with the help of the observation that .
- Definition of what it means for to be a (Fermat) pseudoprime to the base .
- Lemma 70: If is pseudoprime to the bases and , then is pseudoprime to the base and also to the base . This was straightforward from the definition.
- Lemma 71: If there is a base to which is not pseudoprime, then at least half of all bases are such that is not pseudoprime. We defined an injective function from the set of bases to which is pseudoprime to the set of bases to which 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 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.