A Carmichael number is a composite positive integer n > 1 that satisfies the congruence a^{n-1} \equiv 1 \pmod{n} for every integer a coprime to n, making it a pseudoprime to every such base and thus indistinguishable from a prime number under Fermat's Little Theorem test.[1][2]These numbers were first studied in the late 19th century, with Czechmathematician Václav Šimerka identifying the smallest example, 561, in 1885, though without recognizing its broader significance.[2] The concept was formalized by American mathematician Robert D. Carmichael, who described their pseudoprime properties in a 1910 paper in the Bulletin of the American Mathematical Society and a 1912 paper in the American Mathematical Monthly.[2] The term "Carmichael number" was coined later by N. G. W. H. Beeger in 1950 to honor Carmichael's contributions.[2]Carmichael numbers must be odd, square-free, and divisible by at least three distinct prime factors.[1][2] They satisfy Korselt's criterion, formulated by Axel E. Korselt in 1899: a composite n is Carmichael if and only if it is square-free and for every prime p dividing n, p-1 divides n-1.[2] This criterion provides a constructive way to identify them, such as through Chernick's method, where the product of three primes of the forms $6k+1, $12k+1, and $18k+1 yields a Carmichael number for suitable k.[2]The smallest Carmichael number is 561 = 3 × 11 × 17.[1][2] Other early examples include 1105 = 5 × 13 × 17, 1729 = 7 × 13 × 19, and 2465 = 5 × 17 × 29.[1][2] Their existence posed a challenge in number theory, with Paul Erdős conjecturing in the 1950s that infinitely many exist; this was proven in 1994 by W. R. Alford, Andrew Granville, and Carl Pomerance, who showed there are more than x^{2/7} such numbers up to x for sufficiently large x.[3]
Definition and Criteria
Korselt's Criterion
A positive composite integer n is a Carmichael number if and only if it is square-free and, for every prime p dividing n, p - 1 divides n - 1.[1][4]Square-freeness means that n has no squared prime factors in its prime factorization, i.e., n = p_1 p_2 \cdots p_k where the p_i are distinct primes and k \geq 2. This condition ensures that the integers modulo n form a direct product of fields via the Chinese Remainder Theorem, which is essential for the pseudoprimality property to hold uniformly across components.[1][5]An equivalent formulation of Korselt's criterion uses the Carmichael function \lambda(n), defined as the least common multiple of p_i - 1 for the distinct primes p_i dividing n; thus, n is a Carmichael number if \lambda(n) divides n - 1.[1][4]To see why this criterion implies compositeness and the defining pseudoprimality condition, note that square-freeness with k \geq 2 guarantees n is composite. For the pseudoprimality, n must satisfy a^{n-1} \equiv 1 \pmod{n} for all a coprime to n, a property rooted in Fermat's Little Theorem. By the Chinese Remainder Theorem, it suffices to show a^{n-1} \equiv 1 \pmod{p_i} for each prime p_i dividing n. Fermat's Little Theorem gives a^{p_i - 1} \equiv 1 \pmod{p_i} if p_i \nmid a, so the multiplicative order of a modulo p_i divides p_i - 1. Since p_i - 1 divides n - 1, the order also divides n - 1, yielding a^{n-1} \equiv 1 \pmod{p_i}. Thus, the condition holds modulo n. Conversely, if n is a Carmichael number, it must be square-free (as squared factors would violate pseudoprimality for certain bases) and satisfy the divisibility for each p_i.[1][4]For verification, consider n = 561 = 3 \times 11 \times 17. Here, n - 1 = 560, and the primes yield $3 - 1 = 2 (divides 560 since $560 / 2 = 280), $11 - 1 = 10 (divides 560 since $560 / 10 = 56), and $17 - 1 = 16 (divides 560 since $560 / 16 = 35). Thus, 561 satisfies Korselt's criterion.[1]
Equivalent Formulations
A Carmichael number can be defined as a composite positive integer n > 1 such that a^{n-1} \equiv 1 \pmod{n} for every integer a coprime to n.[2] This property establishes n as a universal Fermat pseudoprime, meaning it satisfies the conclusion of Fermat's Little Theorem for all suitable bases a, despite being composite.[2]An equivalent characterization involves the Carmichael function \lambda(n), which denotes the exponent of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^\times, or the least common multiple of the exponents of the component groups for the prime power factorization of n.[6] Specifically, a positive integer n is a Carmichael number if and only if it is composite and square-free with \lambda(n) dividing n-1.[6] For square-free n, \lambda(n) simplifies to the least common multiple of p-1 over all distinct primes p dividing n.[6]This pseudoprime condition is equivalent to Korselt's criterion, which requires n to be square-free and composite with p-1 dividing n-1 for every prime p dividing n.[2] To see the equivalence, assume n is square-free, so \mathbb{Z}/n\mathbb{Z}^\times \cong \prod_{p \mid n} \mathbb{Z}/p\mathbb{Z}^\times by the Chinese Remainder Theorem.[2] For a coprime to n, Euler's theorem implies a^{\phi(p)} \equiv 1 \pmod{p} for each p \mid n, where \phi(p) = p-1; thus, if p-1 \mid n-1 for all such p, then a^{n-1} \equiv 1 \pmod{p} for each p, and hence modulo n.[2] Conversely, if a^{n-1} \equiv 1 \pmod{n} for all a coprime to n, then by considering generators modulo each p, the order divides n-1, so p-1 \mid n-1.[2] The square-free requirement follows from a contradiction: if p^2 \mid n, there exists a with a^{n-1} \not\equiv 1 \pmod{p^2}.[6]The pseudoprime condition also implies that the multiplicative order \ord_n(a) divides n-1 for every a coprime to n, since a^{n-1} \equiv 1 \pmod{n} means the order divides n-1.[2] This is distinct from base-specific Fermat pseudoprimes, which hold only for particular bases, or strong pseudoprimes, which satisfy a stricter condition related to the Miller-Rabin primality test involving witnesses across prime factors.[2]
History
Early Observations
The foundations of recognizing numbers that mimic prime behavior under modular exponentiation were laid in the 17th century by Pierre de Fermat, who in a 1640 letter to Frenicle de Bessy stated what is now known as Fermat's Little Theorem: for a prime p and integer a not divisible by p, a^{p-1} ≡ 1 mod p. This congruence provides a primality test, but Fermat's work indirectly hinted at the possibility of composites passing it for certain bases, though no explicit examples of such pseudoprimes were given.In the 19th century, investigations into the reliability of Fermat's congruence revealed the existence of composite numbers that satisfy it for specific bases, fostering suspicion of broader classes of such "anomalous" composites. A pivotal early example was identified in 1820 by Pierre Frédéric Sarrus, who found that 341 = 11 × 31 is a Fermat pseudoprime to base 2, as 2^{340} ≡ 1 mod 341 despite 341 being composite; this was the first such instance documented. Concurrently, studies of Fermat quotients—quantities of the form q_p(a) = (a^{p-1} - 1)/p, first systematically explored by C. G. J. Jacobi and later by G. Eisenstein in the mid-19th century—uncovered irregular patterns and anomalous residues for composite moduli, suggesting the potential for composites to behave like primes across multiple bases.In 1885, Czech mathematician Václav Šimerka enumerated the first seven Carmichael numbers—561, 1105, 1729, 2465, 2821, 6601, and 8911—in his paper "Zbytky z arithmetické posloupnosti" published in Časopis pro pěstování matematiky a fysiky, while studying remainders in arithmetic progressions. Although he identified these composite numbers, Šimerka did not recognize their property of satisfying Fermat's congruence for all coprime bases.[7]The most direct pre-20th-century insight into what would later be termed Carmichael numbers came from Alwin Korselt in 1899. In a response titled "Problème chinois" published in L'Intermédiaire des mathématiciens, Korselt articulated a necessary criterion (now known as Korselt's criterion) for a composite number n to satisfy a^{n-1} ≡ 1 mod n for all integers a coprime to n: n must be square-free, and for every prime p dividing n, p-1 must divide n-1. He observed that the composite number 561 = 3 × 11 × 17 satisfies this criterion but, after exhaustively checking all odd composite numbers up to 1000 and finding none that do, erroneously concluded that no such composites exist, thereby conjecturing the non-existence of absolute pseudoprimes.[8]
Carmichael's Contributions
In 1912, Robert D. Carmichael published a seminal paper in the American Mathematical Monthly where he systematically identified the smallest known composite numbers that satisfy Fermat's congruence a^{n-1} \equiv 1 \pmod{n} for every integer a coprime to n.[9] These numbers, now known as Carmichael numbers, include 561, 1105, and 1729 as the initial examples he discovered.[9] Building on earlier theoretical work, Carmichael's investigation highlighted the limitations of Fermat's little theorem as a primality test, demonstrating that such composites could masquerade as primes under this criterion.[10]Carmichael's search method involved examining square-free composite numbers with small distinct prime factors, specifically those where, for each prime factor p dividing n, the condition p-1 divides n-1 holds—a formulation equivalent to Korselt's criterion from 1899.[9] He applied this approach to products of three small primes, verifying the examples empirically. For instance, 561 = 3 × 11 × 17, where n-1 = 560 is divisible by 2, 10, and 16; similarly, 1105 = 5 × 13 × 17 with divisors 4, 12, and 16 of 1104; and 1729 = 7 × 13 × 19 with divisors 6, 12, and 18 of 1728.[9] This methodical enumeration was groundbreaking, as it provided concrete counterexamples to the converse of Fermat's theorem.Earlier, in 1910, Carmichael had laid foundational groundwork by defining the universal exponent function \lambda(n), the smallest exponent such that a^{\lambda(n)} \equiv 1 \pmod{n} for all a coprime to n, and noting that 561 satisfies \lambda(561) \mid 560. His 1912 work expanded this to additional cases, emphasizing numbers where \lambda(n) \mid n-1. These contributions significantly influenced early 20th-century number theory by underscoring the need for stronger primality tests beyond Fermat's method, spurring further research into pseudoprimes.[9] The term "Carmichael numbers" was later adopted in 1950 by Nicolaas G. W. H. Beeger to honor his discoveries.
Fundamental Properties
Structural Characteristics
Carmichael numbers, as defined by Korselt's criterion, exhibit several inherent algebraic properties that stem directly from the requirement that a composite, square-free integer n = p_1 p_2 \cdots p_k (with distinct primes p_i) satisfies p_i - 1 \mid n - 1 for each i.[2]A fundamental structural trait is that all Carmichael numbers are odd. Suppose n > 2 is even. Then n-1 is odd, so for any odd prime p dividing n, p-1 is even but cannot divide the odd n-1 (since an even integer greater than 1 does not divide an odd integer). Thus, Korselt's criterion fails. Equivalently, the pseudoprime condition fails for base a \equiv -1 \pmod{n} (e.g., a = n-1), as a^{n-1} \equiv (-1)^{n-1} = -1 \not\equiv 1 \pmod{n} since n \nmid 2. This oddness places Carmichael numbers in the residue class 1 modulo 2.[2]Carmichael numbers must also have at least three distinct prime factors. Products of two distinct primes pq cannot satisfy Korselt's criterion, as the conditions p-1 \mid pq-1 and q-1 \mid pq-1 lead to inconsistencies unless p or q is 2, which contradicts oddness; thus, k \geq 3.[11] This minimal factorization structure underscores their composite nature without being prime powers, as any prime power p^k (for k \geq 2) is not square-free, directly excluding it from the definition.[12]An equivalent characterization arises from the Carmichael function \lambda(n), the exponent of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^\times. A number n is Carmichael if and only if \lambda(n) \mid n-1, or equivalently, n \equiv 1 \pmod{\lambda(n)}. This congruence captures the universal order divisibility required for the pseudoprimality condition across all bases coprime to n.[13]Consequently, Carmichael numbers are absolute pseudoprimes, meaning they pass the Fermat primality test a^{n-1} \equiv 1 \pmod{n} for every integer a coprime to n. This property follows immediately from the \lambda(n) \mid n-1 condition, as the order of any such a divides \lambda(n), hence divides n-1.[14]
Relation to Pseudoprimality
A Fermat pseudoprime to base b is a composite positive integer n such that b^{n-1} \equiv 1 \pmod{n}, mimicking the conclusion of Fermat's Little Theorem despite n not being prime.[15] This property holds provided \gcd(b, n) = 1, and such numbers can deceive primality tests based solely on that base.[15]Carmichael numbers represent the most robust form of Fermat pseudoprimes, satisfying b^{n-1} \equiv 1 \pmod{n} for every base b coprime to n, rendering them absolute or universal pseudoprimes.[1] This universal behavior makes them particularly insidious, as they pass Fermat-based tests regardless of the chosen base, unlike ordinary pseudoprimes that may fail for specific bases.[1]In probabilistic primality testing, such as the Fermat test, Carmichael numbers lead to false positives with certainty when the base is coprime to n, undermining the reliability of these methods for composite detection.[8] Consequently, more advanced tests like the Miller-Rabin algorithm are employed, which detect Carmichael numbers as composite with high probability by using multiple bases, though they still pose challenges in naive implementations.[8]Historically, Carmichael numbers have played a role in cryptography, notably in RSA factoring challenges, where their pseudoprime properties and resistance to certain tests highlighted vulnerabilities in key generation if a Carmichael number is mistakenly used as a prime factor in the modulus, potentially enabling attacks on the system.[16]There are exactly 8,238 Carmichael numbers below $10^{12}, indicating their relative rarity among composites—approximately one per $10^8 numbers in this range—yet they tend to cluster around certain sizes, increasing their practical impact in targeted searches or tests.[17]
Constructions and Examples
Explicit Factorizations
The smallest Carmichael number is 561, which has the prime factorization $561 = 3 \times 11 \times 17.[7] This number satisfies Korselt's criterion, as each p-1 divides $560: specifically, $2 \mid 560, $10 \mid 560, and $16 \mid 560.[2]Subsequent small Carmichael numbers exhibit similar square-free structures with three distinct odd prime factors. For instance, 1105 factors as $5 \times 13 \times 17, 1729 as $7 \times 13 \times 19, and 2465 as $5 \times 17 \times 29.[18] A larger example is 2821, with factorization $7 \times 13 \times 31, verified by Korselt's criterion since $6 \mid 2820, $12 \mid 2820, and $30 \mid 2820.[1]In these explicit factorizations of small Carmichael numbers, the prime factors often appear congruent to 3 modulo 4 (e.g., 3, 7, 11, 19, 23, 31) or feature p-1 values with small prime divisors (e.g., 2, 4, 6, 10, 12), which supports the divisibility requirements of Korselt's criterion.[18]The following table lists the first 10 Carmichael numbers, their full prime factorizations, and the corresponding p-1 values that divide n-1:
Carmichael Number n
Prime Factorization
p-1 Values (each divides n-1)
561
[3](/page/3) \times 11 \times 17
2, 10, 16
1105
$5 \times 13 \times 17
4, 12, 16
1729
[7](/page/+7) \times 13 \times 19
6, 12, 18
2465
$5 \times 17 \times 29
4, 16, 28
2821
[7](/page/+7) \times 13 \times 31
6, 12, 30
6601
[7](/page/+7) \times 23 \times 41
6, 22, 40
8911
[7](/page/+7) \times 19 \times 67
6, 18, 66
10585
$5 \times 29 \times 73
4, 28, 72
15841
[7](/page/+7) \times 31 \times 73
6, 30, 72
29341
$13 \times 37 \times 61
12, 36, 60
[7][18]
Methods of Generation
One prominent method for generating Carmichael numbers, introduced by Paul Erdős in 1956, relies on a probabilistic construction. To build such a number, select a fixed positive integer L and identify a large set of distinct primes p_i such that p_i - 1 divides L for each i. Then, a suitable subset of these primes whose product n satisfies n \equiv 1 \pmod{L} will ensure that L divides n-1. Since each p_i -1 divides L, it follows that each p_i -1 divides n-1, satisfying Korselt's criterion provided the subset has at least three primes (ensuring compositeness and square-freeness). Erdős used probabilistic arguments to show that such sets of primes exist in abundance for large L, enabling the construction of Carmichael numbers with arbitrarily many prime factors.[14]A landmark theoretical construction proving the infinitude of Carmichael numbers was developed by William R. Alford, Andrew Granville, and Carl Pomerance in 1994. Their approach employs covering systems—collections of congruences that cover all integers modulo a given modulus—to select primes p_i such that the Carmichael function \lambda(n) divides n-1. Specifically, they construct n as a product of primes from residue classes designed so that the least common multiple of the p_i - 1 is forced to divide n-1 via the covering, yielding infinitely many such composite n. This method not only establishes existence but also provides a framework for generating Carmichael numbers with controlled prime factor counts.[3]Modern computational methods for generating Carmichael numbers often involve sieving techniques over lists of primes, checking divisor conditions from Korselt's criterion up to large bounds. These algorithms, building on earlier work by Richard Pinch, use optimized sieves to enumerate products of primes satisfying the necessary congruences, with computations extending to limits around $10^{20} and beyond through parallel processing and modular arithmetic optimizations. For instance, recent advances have tabulated all Carmichael numbers up to $10^{22}, revealing 49,679,870 such numbers via bifurcated sieving algorithms that separate cases based on the size of the largest prime factor.[19]
Density and Distribution
Asymptotic Counts
In 1994, Alford, Granville, and Pomerance proved that there are infinitely many Carmichael numbers by establishing a lower bound on their counting function C(x), the number of Carmichael numbers up to x, showing that C(x) > x^{2/7} for sufficiently large x.[3] This result resolved a long-standing conjecture and demonstrated that Carmichael numbers grow at least polynomially, albeit sublinearly, with x.Subsequent improvements refined this lower bound. In 2005, Harman strengthened it to C(x) > x^{0.332} for large x, using advanced sieve methods to construct more Carmichael numbers via better coverings of integers by arithmetic progressions.[20] The current best lower bound remains x^{0.332}, though the exact asymptotic growth is an active area of research.For upper bounds, Pomerance established that C(x) < x^{1 - c / \log \log \log x} for some constant c > 0 and sufficiently large x, providing evidence that Carmichael numbers are relatively sparse despite their infinitude.[21] This bound, derived from analytic number theory estimates on prime distributions, shows that the growth is slower than any fixed power greater than 1 but faster than exponential decay.Heuristically, Erdős and Pomerance argued that the expected count is on the order of x^{1/2} / \log x, based on probabilistic models of prime factorizations satisfying Korselt's criterion; however, explicit constructions reveal that the actual growth exceeds this naive expectation.[11]Computationally, exhaustive searches have identified exactly 20,138,200 Carmichael numbers up to $10^{21} (as computed in 2007), confirming the theoretical lower bounds and highlighting the feasibility of generating large instances through systematic sieving.
Arithmetic Progressions
The distribution of Carmichael numbers within arithmetic progressions has been a subject of significant interest, building on adaptations of Dirichlet's theorem on primes in arithmetic progressions. Early unconditional results established the existence of infinitely many Carmichael numbers in specific progressions, such as those congruent to 1 modulo fixed values like 3 or 5, by constructing suitable products of primes whose p-1 divide a common λ-value while ensuring the product falls into the desired residue class.[3]In 2013, Thomas Wright proved unconditionally that for any integers a and M with gcd(a, M) = 1, there are infinitely many Carmichael numbers congruent to a modulo M.[22] This result relies on advanced sieve methods to produce the required primes in appropriate residue classes.A 2025 result by Daniel Larsen provides a complete dichotomy: every arithmetic progression contains either infinitely many Carmichael numbers or none at all, with the outcome determined by a simple criterion involving the existence of suitable primes that can form the factors while satisfying the progression condition and Korselt's criterion.[23] Specifically, for progressions a mod d with gcd(a, d) = 1, the progression always contains infinitely many, confirming and extending prior work; none occur only when structural obstructions prevent the construction, such as when the progression forces even numbers or squares. This resolves a long-standing conjecture by showing no coprime progression is completely avoided.[23][22]For example, the arithmetic progression 1 mod 561 contains infinitely many Carmichael numbers, as 561 is itself the smallest such number and gcd(1, 561) = 1.[22]Constructions of Carmichael numbers often employ covering systems to force the prime factors into residue classes modulo a fixed λ, ensuring p ≡ 1 mod divisors of λ so that p-1 divides λ, which in turn allows the product to satisfy n ≡ 1 mod λ and thus lie in desired progressions.[3]
Variants
Lucas-Carmichael Numbers
Lucas-Carmichael numbers are square-free composite integers that serve as analogues to Carmichael numbers for the Lucas primality test, passing the test with respect to Lucas sequences defined by parameters P and Q. Specifically, an odd composite square-free n is a Lucas-Carmichael number if, for all integers P, Q with \gcd(P, Q) = 1 and \gcd(n, Q(P^2 - 4Q)) = 1, the Lucas sequence satisfies U_{n+1}(P, Q) \equiv 0 \pmod{n} and V_n(P, Q) \equiv P \pmod{n}.An equivalent criterion is that for each prime p dividing n, the rank of apparition of p in the Lucas sequence divides n + 1 (or a similar adjusted index based on the Jacobi symbol).An equivalent, simpler criterion, analogous to Korselt's criterion, is that n is square-free, odd, composite, and p + 1 divides n + 1 for every prime p dividing n.[24]The smallest example is 399 = 3 × 7 × 19.[25]Lucas-Carmichael numbers are always odd and possess at least three distinct prime factors; they are rarer than standard Carmichael numbers.[26]These numbers can deceive Lucas-Lehmer-like primality tests employed in cryptographic protocols, potentially compromising the security of systems relying on such tests for key generation.[27]
Quasi-Carmichael Numbers
Quasi-Carmichael numbers represent a generalization of Carmichael numbers in which the condition for pseudoprimality is relaxed to hold for all but finitely many bases coprime to the number. This concept was introduced by Paul Erdős in 1956, who referred to them as "almost" Carmichael numbers in the context of studying the distribution of pseudoprimes.[14]A quasi-Carmichael number is a composite integer n such that a^{n-1} \equiv 1 \pmod{n} for all but finitely many integers a with \gcd(a, n) = 1.[14] An equivalent criterion involves the Carmichael function \lambda(n), where \lambda(n) divides n-1 except for small exceptions in the divisibility condition.[14]A representative example is 91 = 7 × 13, which fails the condition for bases a = 3 and a = 10 but satisfies it for the others coprime to 91.[28] Quasi-Carmichael numbers can have as few as two prime factors and play a role in investigations of the density of pseudoprimes among composite numbers.[14]
Knödel numbers constitute a generalization of Carmichael numbers, defined as a family of composite integers satisfying a relaxed form of the universal Fermat pseudoprimality condition. Specifically, for a fixed positive integer k, a composite number n > k is a k-Knödel number if a^{n-k} \equiv 1 \pmod{n} for every integer a with $1 < a < n and \gcd(a, n) = 1. This condition implies that the exponent of the multiplicative group modulo n, denoted \lambda(n), divides n - k. The sets of such numbers, denoted C_k, were first considered in the context of Carmichael-like composites by Walter Knödel in his 1953 paper on Carmichael numbers.[29]The case k = 1 precisely recovers the Carmichael numbers, as the condition reduces to a^{n-1} \equiv 1 \pmod{n} for all a coprime to n, establishing C_1 as the set of all Carmichael numbers. For k \geq 2, the sets C_k are larger, encompassing composites that pass the Fermat test with a reduced exponent n - k. In 1963, A. Makowski proved that each C_k for k \geq 2 is infinite, extending earlier results on the abundance of such pseudoprimes. Every composite n belongs to some C_k, specifically for k \equiv n \pmod{\lambda(n)} with $0 < k < n, highlighting their ubiquity among composites.[6]Notable examples include the smallest Carmichael number 561, which is a 1-Knödel number satisfying the condition for all 560 bases coprime to it between 1 and 560. Smaller composites like 341 ($11 \times 31) qualify as higher-order Knödel numbers; with \lambda(341) = 30, it is an 11-Knödel number since 30 divides $341 - 11 = 330, ensuring the congruence holds for all relevant bases. These numbers are studied for their role in probing the distribution and construction of pseudoprimes, particularly in sequences where the pseudoprimality holds across bases coprime to n, aiding analyses of primality testing robustness.[30]
Higher-Order Carmichael Numbers
A Carmichael number of order k is a positive composite integer n such that the map x \mapsto x^n defines an endomorphism of every \mathbb{Z}/n\mathbb{Z}-algebra generated as a \mathbb{Z}/n\mathbb{Z}-module by k elements. This algebraic condition generalizes the standardnotion of a Carmichael number, which corresponds precisely to the case k=1.An equivalent number-theoretic criterion states that n must be squarefree, and for every prime divisor p of n and every integer r with $1 \leq r \leq k, there exists a nonnegative integer i such that n \equiv p^i \pmod{p^r - 1}. For k=1, this reduces to the classical Korselt's criterion, requiring n \equiv 1 \pmod{p-1} for each prime p dividing n. Higher values of k impose stricter conditions on the prime factors, ensuring n satisfies enhanced pseudoprimality properties across multiple levels of algebraic structure.The concept was introduced by Everett W. Howe in 1998 to explore stronger forms of pseudoprimality beyond the standard Fermat test.[31] For k=2, no such numbers are known below $10^{12}, and the smallest examples are vastly larger, each being the product of 15 distinct primes with approximate magnitude $10^{31}. One representative example factors as $31 \times 37 \times 101 \times 103 \times 109 \times 199 \times 419 \times 449 \times 521 \times 571 \times 911 \times 2089 \times 2551 \times 5851 \times 11969.Howe provides a heuristic argument, adapting Erdős's probabilistic method from the standard case, indicating that infinitely many Carmichael numbers exist for every fixed order k \geq 1.