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

- Lemma 69:
*If and are solutions to , then so is .*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 .* - Lemma 70: If is pseudoprime to the bases and , then is pseudoprime to the base and also to the base . This was easy to check.
- Proposition 71:
*If is not pseudoprime to some base , then at least half of all bases are such that is not pseudoprime to those bases.*We showed that there is an injection from {bases to which is pseudoprime} to {bases to which is not pseudoprime}. - Definition of a
*Carmichael number*. - Definition of an
*Euler pseudoprime to the base .*

#### Further reading

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 is a Carmichael number, what can you say about and its prime factors?

November 25, 2011 at 12:27 pm

[…] Theorem of the week Expositions of interesting mathematical results « Number Theory: Lecture 21 […]