Let a>1 be an integer. Recall that Fermat's
(little) theorem shows that if p does not divide a,
then ap-1 = 1 (mod p). m
is a probable-prime base a (an a-PRP) if am-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.
Choose any prime p which does not dividea(a2-1)
(this condition can be weakened to p which does not divide a2-1,
see [CP2001
thm 3.3.4]) and then define
m = (a2p-1)/(a2-1).
m is divisible by (ap-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:
(a2-1)(m-1) = a(ap-1-1)(ap+a).
Clearly the rightmost term is even and a2-1 divides ap-1-1
(as p-1 is even). Also, Fermat's theorem tells us that ap-1-1
is divisible by p, so
2p(a2-1) divides (a2-1)(m-1)
or just 2p divides m-1. Finally, by the definition of
m we have a2p = 1 + m(a2-1)
or just a2p = 1 (mod m). It follows
that am-1 is also one modulo m, completing
the proof.
