Carmichael number

⁠ which in modular arithmetic satisfies the congruence relation: for all integers ⁠

[3] They constitute the comparatively rare instances where the strict converse of Fermat's Little Theorem does not hold.

This fact precludes the use of that theorem as an absolute test of primality.

A Carmichael number will pass a Fermat primality test to every base

However, no Carmichael number is either an Euler–Jacobi pseudoprime or a strong pseudoprime to every base relatively prime to it[6] so, in theory, either an Euler or a strong probable prime test could prove that a Carmichael number is, in fact, composite.

⁠, so this Carmichael number is also a (not necessarily strong) pseudoprime to all bases less than ⁠

[8] An alternative and equivalent definition of Carmichael numbers is given by Korselt's criterion.

It follows from this theorem that all Carmichael numbers are odd, since any even composite number that is square-free (and hence has only one prime factor of two) will have at least one odd prime factor, and thus

The first seven Carmichael numbers, from 561 to 8911, were all found by the Czech mathematician Václav Šimerka in 1885[11] (thus preceding not just Carmichael but also Korselt, although Šimerka did not find anything like Korselt's criterion).

[12] His work, published in Czech scientific journal Časopis pro pěstování matematiky a fysiky, however, remained unnoticed.Korselt was the first who observed the basic properties of Carmichael numbers, but he did not give any examples.

Jack Chernick[14] proved a theorem in 1939 which can be used to construct a subset of Carmichael numbers.

Whether this formula produces an infinite quantity of Carmichael numbers is an open question (though it is implied by Dickson's conjecture).

Paul Erdős heuristically argued there should be infinitely many Carmichael numbers.

In 1994 W. R. (Red) Alford, Andrew Granville and Carl Pomerance used a bound on Olson's constant to show that there really do exist infinitely many Carmichael numbers.

are relatively prime, then there are infinitely many Carmichael numbers in the arithmetic progression ⁠

[15] Löh and Niebuhr in 1992 found some very large Carmichael numbers, including one with 1,101,518 factors and over 16 million digits.

The distribution of Carmichael numbers by powers of 10 (sequence A055553 in the OEIS):[8] In 1953, Knödel proved the upper bound: for some constant ⁠

[17] He further gave a heuristic argument suggesting that this upper bound should be close to the true growth rate of ⁠

In 1981, Pomerance[20] sharpened Erdős' heuristic arguments to conjecture that there are at least Carmichael numbers up to ⁠

However, inside current computational ranges (such as the counts of Carmichael numbers performed by Pinch[8] up to 1021), these conjectures are not yet borne out by the data.

In 2021, Daniel Larsen proved an analogue of Bertrand's postulate for Carmichael numbers first conjectured by Alford, Granville, and Pomerance in 1994.

[4][21] Using techniques developed by Yitang Zhang and James Maynard to establish results concerning small gaps between primes, his work yielded the much stronger statement that, for any

⁠ is larger than the rationals it is easy to write down Carmichael ideals in ⁠

Both prime and Carmichael numbers satisfy the following equality: A positive composite integer

Carmichael numbers can be generalized using concepts of abstract algebra.

The above definition states that a composite integer n is Carmichael precisely when the nth-power-raising function pn from the ring Zn of integers modulo n to itself is the identity function.

A theorem states that n is prime if and only if all such functions pn are algebra endomorphisms.

In-between these two conditions lies the definition of Carmichael number of order m for any positive integer m as any composite number n such that pn is an endomorphism on every Zn-algebra that can be generated as Zn-module by m elements.

[22] Korselt's criterion can be generalized to higher-order Carmichael numbers, as shown by Howe.

A heuristic argument, given in the same paper, appears to suggest that there are infinitely many Carmichael numbers of order m, for any m. However, not a single Carmichael number of order 3 or above is known.