# Infinitely many pseudoprimes

Let *a* > 1 be an integer. Recall that Fermat's
(little) theorem shows that if *p* does not divide *a*,
then *a*^{p-1} ≡ 1 (mod *p*). *m* is a **probable-prime base a** (an

**) if**

*a*-PRP*a*

^{m-1}≡ 1 (mod

*m*). "Most" such numbers

*m*are prime, but if they are not, they are called

**pseudo-primes base**. The purpose of this note is to prove the following:

*a***Theorem:**- Let
*a*be any integer greater than one. There is an infinite number of pseudoprimes with respect to the base*a*. **Proof:**We will follow Ribenboim [HW79 p72].-
Choose any prime

*p*which does not divide*a*(*a*^{2}-1) (this condition can be weakened to*p*which does not divide*a*^{2}-1, see [CP2001 thm 3.3.4]) and then define*m*= (*a*^{2p}-1)/(*a*^{2}-1).*m*is divisible by (*a*^{p}-1)/(*a*-1), so*m*is composite. Also this*m*is different for each choice of*p*, so we need only show*m*is an*a*-PRP to complete the proof.Rewrite the expression for

*m*above:(

*a*^{2}-1)(*m*-1) =*a*(*a*^{p-1}-1)(*a*^{p}+*a*).Clearly the rightmost term is even and

*a*^{2}-1 divides*a*^{p-1}-1 (as*p*-1 is even). Also, Fermat's theorem tells us that*a*^{p-1}-1 is divisible by*p*, so2

*p*(*a*^{2}-1) divides (*a*^{2}-1)(*m*-1)or just 2

*p*divides*m*-1. Finally, by the definition of*m*we have*a*^{2p}= 1 +*m*(*a*^{2}-1) or just*a*^{2p}≡ 1 (mod*m*). It follows that*a*^{m-1}is also one modulo*m*, completing the proof. ∎