Infinitely many pseudoprimes

By Chris Caldwell

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 a-PRP) if a^m-1 ≡ 1 (mod m).  "Most" such numbers m are prime, but if they are not, they are called pseudo-primes base a.  The purpose of this note is to prove the following:

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²-1) (this condition can be weakened to p which does not divide a²-1, see [CP2001 thm 3.3.4]) and then define

m = (a^2p-1)/(a²-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²-1)(m-1) = a(a^p-1-1)(a^p+a).

Clearly the rightmost term is even and a²-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, so

2p(a²-1) divides (a²-1)(m-1)

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