Fermat pseudoprime
A Fermat pseudoprime to base a is a composite positive integer n such that a^{n-1} \equiv 1 \pmod{n}, where a and n are coprime, thereby satisfying the conclusion of Fermat's Little Theorem despite n not being prime.[1] This property makes such numbers significant in probabilistic primality testing, as they can pass the Fermat test—a simple yet unreliable method for identifying primes—leading to false positives when distinguishing primes from composites.[2] The concept originates from Fermat's Little Theorem, which states that if p is prime and \gcd(a, p) = 1, then a^{p-1} \equiv 1 \pmod{p}; pseudoprimes exploit this by behaving like primes for specific bases.[1] Historically, pseudoprimes to base 2 were first studied by Pierre Frédéric Sarrus in 1819 (termed "Sarrus numbers") and later named "Poulet numbers" by Paul Poulet in 1926 after he compiled extensive lists of them.[3] There are infinitely many Fermat pseudoprimes to any fixed base a \geq 2, and their density is low, with estimates showing fewer than x^{1 - c \frac{\log \log \log x}{\log \log x}} such numbers up to x for some constant c > 0.[2] A special subclass consists of Carmichael numbers, which are absolute Fermat pseudoprimes: composite n satisfying b^{n-1} \equiv 1 \pmod{n} for every base b coprime to n.[4] The smallest Fermat pseudoprime to base 2 is 341 ($11 \times 31), while the smallest Carmichael number is 561 ($3 \times 11 \times 17).[1] To mitigate the risk of pseudoprimes in testing, multiple bases are often used; for example, testing bases 2, 3, 5, and 7 leaves 1770 composites below $25 \times 10^9 that pass all four tests.[1] These numbers also appear in cryptographic applications, where reliable primality tests are essential for security.[5]Background
Fermat's Little Theorem
Fermat's Little Theorem states that if p is a prime number and a is an integer not divisible by p, then a^{p-1} \equiv 1 \pmod{p}.[6] An equivalent formulation is a^p \equiv a \pmod{p} for any integer a.[6] Pierre de Fermat first stated the theorem in a letter dated October 18, 1640, to Bernard Frénicle de Bessy, amid a discussion on perfect numbers prompted by Frénicle's inquiry about whether a 20-digit perfect number existed.[7] Fermat did not include a proof in the letter, and the first rigorous proof was provided by Leonhard Euler in 1736.[7] A proof of the equivalent form a^p \equiv a \pmod{p} can be obtained using the binomial theorem. For a \geq 1, expand (a + 1)^p = \sum_{k=0}^p \binom{p}{k} a^{p-k}, which simplifies to (a + 1)^p \equiv a^p + 1 \pmod{p} because p divides \binom{p}{k} for $1 \leq k \leq p-1.[6] Rearranging gives (a + 1)^p - (a + 1) \equiv a^p - a \pmod{p}, and by induction on a, the result holds for all positive integers a; it extends to a = 0 and negative a trivially.[6] Alternatively, a group-theoretic proof relies on the multiplicative group of integers modulo p, denoted (\mathbb{Z}/p\mathbb{Z})^*, which has order p-1.[6] By Lagrange's theorem, for any a not divisible by p, the order of a modulo p divides p-1, so a^{p-1} \equiv 1 \pmod{p}.[6] Euler's theorem generalizes Fermat's Little Theorem to composite moduli: if n \geq 2 is a positive integer and \gcd(a, n) = 1, then a^{\phi(n)} \equiv 1 \pmod{n}, where \phi is Euler's totient function counting the integers up to n that are relatively prime to n.[8] For prime p, \phi(p) = p-1, so Euler's theorem reduces to Fermat's Little Theorem.[8] For example, with p = 5 and a = 2, compute $2^{5-1} = 16 \equiv 1 \pmod{5}.[6]Fermat Primality Test
The Fermat primality test is a probabilistic algorithm for determining whether an odd integer n > 2 is likely to be prime, based on Fermat's Little Theorem, which states that if p is prime and \gcd(a, p) = 1, then a^{p-1} \equiv 1 \pmod{p}.[6] The test leverages the contrapositive: if a^{n-1} \not\equiv 1 \pmod{n} for some base a with $1 < a < n and \gcd(a, n) = 1, then n is definitively composite.[9] In the procedure, select a random base a satisfying the conditions, compute a^{n-1} \mod n using fast modular exponentiation, and check if the result equals 1; if it does, n passes the test and is deemed a probable prime, while failure proves compositeness.[9] This process is repeated with multiple independent bases to enhance reliability, as a single base may yield inconclusive results for certain composites.[10] The test's probabilistic nature arises because some composite numbers can pass for specific bases, but the probability of error decreases exponentially with the number of bases tested, often making it sufficiently accurate for practical purposes like cryptography.[10] The algorithm's efficiency stems from fast exponentiation via repeated squaring, which requires only O(\log n) modular multiplications, each taking O(\log^2 n) time for large n, resulting in overall polylogarithmic runtime suitable for numbers with hundreds of digits.[9] Historically, the test traces to Fermat's 1640 correspondence, but it gained prominence in the 1970s as computing demands for large-prime generation in cryptography, such as RSA, necessitated fast, heuristic methods over exhaustive trial division.[10] For example, testing n = 341 with base a = 2 yields $2^{340} \equiv 1 \pmod{341}, suggesting primality, yet $341 = 11 \times 31 is composite, illustrating the test's potential for false positives.[9]Definition and Examples
Formal Definition
A composite integer n > 1 is called a Fermat pseudoprime to base b, where $2 \leq b \leq n-1 and \gcd(b, n) = 1, if it satisfies the congruence b^{n-1} \equiv 1 \pmod{n}.[1] This condition mimics the conclusion of Fermat's Little Theorem for primes but applies to composites, hence the term "pseudoprime."[11] Typically, Fermat pseudoprimes are defined for odd composite n, since even composites greater than 2 fail the test for base 2 and are not usually considered.[12] The notation FSP_b(n) or psp_b(n) is commonly used to denote that n is a Fermat pseudoprime to base b.[1] The condition b^{n-1} \equiv 1 \pmod{n} implies that the multiplicative order of b modulo n, denoted \operatorname{ord}_n(b), divides n-1. By Euler's theorem, \operatorname{ord}_n(b) always divides \phi(n), where \phi is Euler's totient function, but for composite n, \phi(n) < n-1, so the order divides \gcd(n-1, \phi(n)).[13] The number 1 is not considered, as it is neither prime nor composite, and powers of 2 are excluded, being either prime (for 2) or even composites that do not satisfy the condition for the relevant bases.[11]Initial Examples
The smallest Fermat pseudoprime to base 2 is 341, a composite number factoring as $11 \times 31. It satisfies the condition $2^{340} \equiv 1 \pmod{341}, passing the Fermat primality test despite its compositeness.[1][12] To verify this, compute $2^{340} modulo 341 using the Chinese Remainder Theorem, as $341 = 11 \times 31. Modulo 11, Fermat's Little Theorem gives $2^{10} \equiv 1 \pmod{11}, so $2^{340} = (2^{10})^{34} \equiv 1^{34} \equiv 1 \pmod{11}. Modulo 31, $2^{30} \equiv 1 \pmod{31} and $340 = 11 \times 30 + 10, so $2^{340} \equiv (2^{30})^{11} \times 2^{10} \equiv 1 \times 2^{10} \pmod{31}. Now, $2^{10} = 1024 and $1024 \div 31 = 33 remainder 1 (since $31 \times 33 = 1023), so $2^{340} \equiv 1 \pmod{31}. Thus, $2^{340} \equiv 1 \pmod{341}.[14][15] Another early example is 561, factoring as $3 \times 11 \times 17, which is a Fermat pseudoprime to base 2 since $2^{560} \equiv 1 \pmod{561}. This number is notable as the smallest Carmichael number, meaning it behaves as a pseudoprime for every base coprime to 561.[12][16] Fermat pseudoprimes can be base-specific. For instance, 91 = $7 \times 13 is a Fermat pseudoprime to base 3, satisfying $3^{90} \equiv 1 \pmod{91}, but fails for base 2 since $2^{90} \equiv 64 \pmod{91} \not\equiv 1.[17][18] The first few Fermat pseudoprimes to base 2 are listed below, along with their factorizations:| n | Prime factorization |
|---|---|
| 341 | $11 \times 31 |
| 561 | $3 \times 11 \times 17 |
| 645 | $3 \times 5 \times 43 |
| 1105 | $5 \times 13 \times 17 |
Properties
Algebraic Properties
A fundamental algebraic property of a Fermat pseudoprime n to base b (with \gcd(b, n) = 1 and n composite) is that n divides b^{n-1} - 1, or equivalently, b^{n-1} \equiv 1 \pmod{n}.[16] This condition mimics Fermat's Little Theorem for primes but holds for certain composites, highlighting the failure of the converse. The property implies that the Fermat quotient q_b(n) = \frac{b^{n-1} - 1}{n} is an integer.[19] For primes p, the Fermat quotient q_b(p) is always an integer by Fermat's Little Theorem, and the extension to pseudoprimes underscores their deceptive behavior in primality testing. Properties of Fermat quotients, such as congruences modulo primes, have been studied for cryptographic applications, where pseudoprimes can introduce vulnerabilities.[20] Consider the case where n = pq with distinct primes p and q. Then n is a Fermat pseudoprime to base b (with \gcd(b, n) = 1) if and only if b^{p-1} \equiv 1 \pmod{q} and b^{q-1} \equiv 1 \pmod{p}.[12] This condition arises because b^{n-1} \equiv 1 \pmod{p} reduces to b^{q-1} \equiv 1 \pmod{p} (using Fermat's Little Theorem modulo p), and similarly modulo q. Thus, the product of two primes that are themselves Fermat pseudoprimes to base b (trivially true by Fermat's Little Theorem) yields a composite Fermat pseudoprime to b precisely when these modular exponentiation conditions hold, reflecting shared order properties of b modulo p and q. Fermat pseudoprimes exhibit non-uniqueness in bases: a fixed composite n can satisfy the condition for multiple bases b coprime to n. The number of such bases b (with $1 < b < n) is given by \prod_{p \mid n} \gcd(n-1, p-1), where the product is over distinct prime divisors p of n.[12] For n = pq, this simplifies to \gcd(pq-1, p-1) \cdot \gcd(pq-1, q-1), and the two gcd terms are equal, yielding a perfect square that is typically greater than 1, ensuring multiple bases exist.Distribution and Density
The distribution of Fermat pseudoprimes to a fixed base b \geq 2 is asymptotically much sparser than that of prime numbers. Let \pi_b(x) denote the number of such pseudoprimes up to x. An upper bound of \pi_b(x) \ll x^{1 - \frac{1}{2} \frac{\log \log \log x}{\log \log x}} holds for sufficiently large x, indicating a subpolynomial growth rate.[2] There are infinitely many Fermat pseudoprimes to any fixed base b > 1. This follows from an explicit construction: for primes p not dividing b(b^2 - 1), the number m = (b^{2p} - 1)/(b^2 - 1) is composite and satisfies b^{m-1} \equiv 1 \pmod{m}, and distinct primes p yield distinct m.[21] A quantitative lower bound for base 2 arises from the existence of Carmichael numbers, which are Fermat pseudoprimes to every coprime base, including 2. Alford, Granville, and Pomerance proved there are at least x^{0.332} Carmichael numbers up to x for sufficiently large x, hence at least as many base-2 Fermat pseudoprimes.[22] Explicit computations confirm the low density. There are 245 base-2 Fermat pseudoprimes below $10^6, 38,975 below $10^{11}, 101,629 below $10^{12}, and 264,239 below $10^{13}. These figures show steady but slow growth, with the proportion among odd composites decreasing: for example, roughly 0.058% of odd composites up to $10^6 (computed as 245 divided by approximately 421,502 such numbers) are base-2 Fermat pseudoprimes.[23] For composite bases b, the asymptotic density remains similarly sparse under fixed b, though the precise count can vary due to differing order conditions in the multiplicative group modulo n. The uniform upper bound applies regardless of whether b is prime or composite.[2]Constructions and Factorizations
Poulet numbers are composite odd integers that are Fermat pseudoprimes to base 2, meaning they satisfy $2^{n-1} \equiv 1 \pmod{n} despite being composite.[24] Named after the mathematician Paul Poulet, who first systematically tabulated them up to 100 million in 1938, these numbers are products of distinct odd primes and represent the simplest non-trivial constructions of base-2 Fermat pseudoprimes. A classic example is the smallest Poulet number, $341 = 11 \times 31, which satisfies the congruence despite its composite nature.[25] To construct square-free Fermat pseudoprimes to base 2 as products of distinct primes p_1, p_2, \dots, p_k, select primes such that for all i \neq j, $2^{p_i - 1} \equiv 1 \pmod{p_j}. This condition ensures that the multiplicative order of 2 modulo each p_j divides p_i - 1 for i \neq j, implying by the Chinese Remainder Theorem that $2^{n-1} \equiv 1 \pmod{p_j} for every j, where n = p_1 p_2 \cdots p_k.[24] An iterative method, building on smaller pseudoprimes, involves taking a known square-free pseudoprime n_i with exactly k-1 prime factors and multiplying it by a primitive prime factor p_i of $2^{n_i} - 1 such that p_i \nmid n_i; the result n_{i+1} = p_i n_i is then a square-free pseudoprime to base 2 with exactly k prime factors.[25] This approach yields infinitely many such numbers for any fixed number of prime factors k \geq 2.[25] For Fermat pseudoprimes that are not square-free, such as those of the form n = p^k m with k \geq 2 and \gcd(p, m) = 1, additional conditions on the exponents are required. Specifically, since n-1 is coprime to p, the base must satisfy a^{p-1} \equiv 1 \pmod{p^k}, meaning p is a base-a Wieferich prime (a rare property), and the order must lift appropriately via properties of the p-adic valuation or binomial theorem expansions.[24] Furthermore, n must satisfy the Fermat condition modulo m. These constraints make non-square-free examples scarce compared to their square-free counterparts.[24] Carmichael numbers provide a special class of square-free Fermat pseudoprimes, as they pass the Fermat test to every base b coprime to n.[26] By Korselt's criterion, a square-free composite n = p_1 p_2 \cdots p_k is Carmichael if and only if p_i - 1 divides n - 1 for each i.[26] Consequently, the Carmichael function \lambda(n) = \operatorname{lcm}(p_1 - 1, \dots, p_k - 1) divides n - 1, ensuring the pseudoprimality condition holds for all suitable bases, including 2 (since Carmichael numbers are odd). A foundational example is the smallest Carmichael number, $561 = 3 \times 11 \times 17, where \lambda(561) = \operatorname{lcm}(2, 10, 16) = 80 divides $560, and each prime factor p satisfies p divides $2^{\lambda(561)} - 1 = 2^{80} - 1 because the order of 2 modulo p divides p-1, which divides \lambda(561).[26]Specific Instances
Smallest Fermat Pseudoprimes
The smallest Fermat pseudoprime to base 2 is 341 = 11 × 31, discovered in 1819 by Pierre Frédéric Sarrus as a counterexample to a naive converse of Fermat's Little Theorem.[27] This number satisfies $2^{340} \equiv 1 \pmod{341}, despite being composite, and it marked an early recognition of the limitations in using Fermat's test for primality.[3] Subsequent small Fermat pseudoprimes to base 2 include 561 = 3 × 11 × 17 (the smallest Carmichael number, also a pseudoprime to all bases coprime to it), 645 = 3 × 5 × 43, and 1105 = 5 × 13 × 17.[28] In 1938, Paul Poulet systematically enumerated all odd Fermat pseudoprimes to base 2 up to 100 million, expanding the known list significantly and highlighting their rarity relative to primes.[29] For base 3, the smallest Fermat pseudoprime is 91 = 7 × 13, which satisfies $3^{90} \equiv 1 \pmod{91}.[30] Additional small examples to base 3 include 119 = 7 × 17 and 247 = 13 × 19. The following table lists the first 10 Fermat pseudoprimes to each base b from 2 to 10, including their prime factorizations where available. These sequences are drawn from established enumerations and illustrate the variation in the smallest such composites across bases.[31]| Base b | First 10 Fermat Pseudoprimes (with prime factors) |
|---|---|
| 2 | 341 (11×31), 561 (3×11×17), 645 (3×5×43), 1105 (5×13×17), 1387 (19×73), 1729 (7×13×19), 1905 (3×5×127), 2047 (23×89), 2465 (5×17×29), 2701 (37×73) |
| 3 | 91 (7×13), 121 (11²), 286 (2×11×13), 671 (11×61), 703 (19×37), 949 (13×73), 1105 (5×13×17), 1541 (23×67), 1729 (7×13×19), 1891 (31×61) |
| 4 | 15 (3×5), 85 (5×17), 91 (7×13), 341 (11×31), 435 (3×5×29), 451 (11×41), 561 (3×11×17), 645 (3×5×43), 703 (19×37), 1105 (5×13×17) |
| 5 | 4 (2²), 124 (2²×31), 217 (7×31), 561 (3×11×17), 781 (11×71), 1541 (23×67), 1729 (7×13×19), 1891 (31×61), 2821 (7×13×31), 4123 (7×19×31) |
| 6 | 35 (5×7), 185 (5×37), 217 (7×31), 301 (7×43), 481 (13×37), 1105 (5×13×17), 1111 (11×101), 1261 (13×97), 1333 (31×43), 1729 (7×13×19) |
| 7 | 6 (2×3), 25 (5²), 325 (5²×13), 561 (3×11×17), 703 (19×37), 817 (19×43), 1105 (5×13×17), 1825 (5²×73), 2101 (11×191), 2353 (13×181) |
| 8 | 9 (3²), 21 (3×7), 45 (3²×5), 63 (3²×7), 65 (5×13), 105 (3×5×7), 117 (3²×13), 133 (7×19), 153 (3²×17), 231 (3×7×11) |
| 9 | 4 (2²), 8 (2³), 28 (2²×7), 52 (2²×13), 91 (7×13), 121 (11²), 205 (5×41), 286 (2×11×13), 364 (2²×7×13), 511 (7×73) |
| 10 | 9 (3²), 33 (3×11), 91 (7×13), 99 (3²×11), 259 (7×37), 451 (11×41), 481 (13×37), 561 (3×11×17), 657 (3×3×73), 703 (19×37) |