## Number Theory: Lecture 21

In which we learn a little more about solutions to Pell’s equation, and start thinking about primality testing.

• 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)$.  This was a straightforward check (and we managed to avoid doing lots of algebra).  So there are infinitely many solutions to Pell’s equation (since we already know that there is one).
• Definition of a 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 easy to check.
• Proposition 71: If $n$ is not pseudoprime to some base $b$, then at least half of all bases are such that $n$ is not pseudoprime to those bases.  We showed that there is an injection from {bases to which $n$ is pseudoprime} to {bases to which $n$ is not pseudoprime}.
• Definition of a Carmichael number.
• Definition of an Euler pseudoprime to the base $b$.

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.

#### Preparation for Lecture 22

We finished with the definition of Euler pseudoprimes.  It would be helpful to look back over our work today on Fermat pseudoprimes, to see whether you can adapt it to Euler pseudoprimes.  I suggest that you start with some examples.  Are there analogues of Proposition 71 and of Carmichael numbers for Euler pseudoprimes?  You could also think about Carmichael numbers: can you find any?  If $n$ is a Carmichael number, what can you say about $n$ and its prime factors?