On the Asymptotic Density of Fermat Pseudoprimes to a Fixed Base

Fermat’s little theorem provides a classical and widely used test for primality: if n is prime and gcd(a,n)=1, then a n−1≡1 (modn). Composite integers satisfying this congruence are called Fermat pseudoprimes to base a, and they represent a fundamental obstruction to Fermat-type primality tests. A classical result of Erdős shows that, for each fixed base a≥2, the set of such numbers has asymptotic density zero. In this note we give a short and elementary proof of this density-zero property for Fermat pseudoprimes, based on ideas of Erdős and Niven.