A Carmichael number is a composite positive integer that mimics a prime with respect to Fermat's little theorem. In concrete terms, a composite n is called a Carmichael number when for every integer b that is relatively prime to n the congruence b^(n-1) ≡ 1 (mod n) holds. The concept arises in number theory as one class of pseudoprimes: numbers that satisfy a primality-test condition without actually being prime. This property is an obstruction to simple Fermat-based primality tests because Carmichael numbers pass those base-dependent checks for every admissible base, thus behaving like primes arithmetically in that specific sense.

Key properties and characterization

Carmichael numbers have a compact algebraic description due to a criterion attributed to Korselt. A composite n is a Carmichael number if and only if n is squarefree (no prime squared divides n) and, for every prime p dividing n, the number p − 1 divides n − 1. This divisibility condition explains why Carmichael numbers force b^(n-1) ≡ 1 (mod n) for all b coprime to n: the order of any unit modulo each prime factor divides n − 1, and the Chinese remainder theorem then combines the local congruences into the global one. From the criterion follow several immediate corollaries: every Carmichael number is odd, it is squarefree, and it must have at least three distinct prime factors. These restrictions distinguish Carmichael numbers from most composite integers.

Examples and small cases

The smallest and most commonly cited example is 561 = 3·11·17, which was identified early in the study of such numbers; 561 satisfies b^(560) ≡ 1 (mod 561) for every b coprime to 561. Another standard example is 1105 = 5·13·17. These numbers show explicitly how the Korselt divisibility condition holds: for 561, each prime factor p has p − 1 dividing 560. Lists of small Carmichael numbers are used in teaching and in testing the robustness of primality algorithms. More examples can be found in computational tables and references in the literature of prime numbers and pseudoprimes.

History and development

The term honors Robert Carmichael, who studied such composite numbers in the early 20th century and drew attention to 561 as an instructive example. The structural criterion that makes their verification practical is due to Korselt and was later popularized in discussions of Fermat pseudoprimes. For many decades Carmichael numbers appeared to be rare curiosities; however, in a significant advance, researchers proved that there are infinitely many Carmichael numbers, so they are more than isolated counterexamples to naive primality checks. For background on the congruence idea underlying their definition see discussions of modular arithmetic and congruences.

Uses, significance, and impact on algorithms

Carmichael numbers are important in computational number theory because they expose weaknesses in simple primality tests based only on Fermat's little theorem. A number n that satisfies b^(n-1) ≡ 1 (mod n) for a particular base b is called a Fermat pseudoprime to base b; Carmichael numbers are Fermat pseudoprimes to every base coprime to n. This led to the development and adoption of stronger probabilistic and deterministic tests (for example, tests that rely on additional structure such as the Miller–Rabin or the deterministic AKS algorithm) to guard against being deceived by these universal pseudoprimes. Practical primality testing therefore treats Carmichael numbers as instructive worst-case examples when evaluating test reliability.

Notable distinctions and facts

  • Squarefree and multifactored: Every Carmichael number is squarefree and has at least three distinct prime divisors; therefore they are never prime and never powers of primes.
  • Infinitude: It is a theorem that there exist infinitely many Carmichael numbers, a result that altered earlier expectations about their scarcity and has consequences for density estimates in analytic number theory.
  • Relation to other pseudoprimes: Carmichael numbers are sometimes called absolute or universal Fermat pseudoprimes because they fool the Fermat test for all coprime bases; however, they can often be detected by stronger criteria such as Euler or strong pseudoprime tests.
  • Computational role: Knowing properties such as Korselt's criterion helps in constructing and verifying Carmichael numbers and in designing primality testing routines that avoid false positives.

For readers who wish to explore further, introductory texts on modular arithmetic and primality testing provide accessible routes into the subject, while computational number theory resources collect tables and algorithms for identifying Carmichael numbers and related pseudoprimes. See discussions of integers and compositeness tests for more context. composite, positive integer, Fermat's little theorem.