Home
Search Site
Largest
The 5000
Top 20
Finding
How Many?
Mersenne
Glossary
Prime Curios!
Prime Lists
FAQ
email list
Titans
Submit primes

Let a>1 be an integer. Recall that Fermat's
(little) theorem shows that if p does not divide a,
then a^{p1} = 1 (mod p). m
is a probableprime base a (an aPRP) if a^{m1}
= 1 (mod m). "Most" such numbers m are prime, but
if they are not, they are called pseudoprimes 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 dividea(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)/(a1), so
m is composite. Also this m is different for each choice
of p, so we need only show m is an aPRP to complete
the proof.
Rewrite the expression for m above:
(a^{2}1)(m1) = a(a^{p1}1)(a^{p}+a).
Clearly the rightmost term is even and a^{2}1 divides a^{p1}1
(as p1 is even). Also, Fermat's theorem tells us that a^{p1}1
is divisible by p, so
2p(a^{2}1) divides (a^{2}1)(m1)
or just 2p divides m1. 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^{m1} is also one modulo m, completing
the proof.
