1.
On the asymptotic density of fermat pseudoprimes to a fixed baseSlobodan Filipovski, 2026, original scientific article
Abstract: 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}\equiv 1 \pmod n. \] 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\H{o}s shows that, for each fixed base $a\geq 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\H{o}s and Niven.
Keywords: Fermat pseudoprimes, asymptotic density, primality testing
Published in RUP: 21.09.2026; Views: 287; Downloads: 13
Full text (530,46 KB)
This document has more files! More...
