Engineering / Mathematics — Primality Testing
The Fermat Test and Carmichael Numbers
The Fermat primality test, pseudoprimes, and the Carmichael numbers that defeat it for every base.
Executive summary
The Fermat test checks whether a candidate satisfies Fermat's little theorem for a chosen base. Failure proves compositeness; success proves nothing.
Carmichael numbers pass for every base coprime to them, so no amount of repetition rescues the test. They are the reason Miller-Rabin exists.
Learning objectives
- State the Fermat test and its one-sided guarantee.
- Define pseudoprimes and Carmichael numbers.
- Explain why Carmichael numbers make the test unrepairable.
01The test
Fermat primality test
candidate n, base acomposite (certain), or probably prime- Choose a base a with 1 < a < n.
- If gcd(a, n) ≠ 1, report composite with factor gcd(a, n).
- Compute r = a^{n−1} mod n by repeated squaring.
- If r ≠ 1, report composite.
- Otherwise report probably prime.
one modular exponentiation, O(len(n)³)The guarantee is one-sided. A verdict of composite is certain, since a prime would necessarily satisfy the congruence. A verdict of probably prime carries no certainty at all.
02Pseudoprimes and Carmichael numbers
Fermat pseudoprime and Carmichael number
A composite n is a Fermat pseudoprime to base a if a^{n−1} ≡ 1 (mod n).
A composite n is a Carmichael number if it is a pseudoprime to every base coprime to n.
Korselt's criterion
A composite n is a Carmichael number if and only if n is squarefree and (p − 1) | (n − 1) for every prime p dividing n.
The criterion explains the mechanism. Squarefreeness plus the divisibility condition makes λ(n) divide n − 1, so every unit raised to n − 1 gives 1 — exactly the Fermat condition, satisfied for structural reasons rather than by accident.
03Why Miller-Rabin succeeds
The Fermat test examines only the order of the group. Miller–Rabin examines the sequence of squarings leading to the final value, and looks for a square root of 1 other than ±1.
Write n − 1 = 2^s · d with d odd
Separates the odd part from the powers of two.
Compute a^d, then square repeatedly
This traces the path to a^{n−1} through s squarings.
Watch for a non-trivial square root of 1
If some value squares to 1 without being ±1, n is composite.
Conclude
A prime modulus admits only ±1 as square roots of 1, so this cannot happen.
04Frequently asked questions
Are Carmichael numbers rare?
They are sparse but infinite — it was proved in 1994 that infinitely many exist. Below 10^16 there are around 250,000, which is negligible relative to the primes but far too many to enumerate as exceptions.
Is the Fermat test useless?
Not entirely. It is cheap and rejects the overwhelming majority of composites, so it works as a pre-filter. It simply cannot serve as the final test.
Why does the gcd check appear first?
Because a base sharing a factor with n would fail the congruence for an uninteresting reason, and the gcd incidentally reveals a factor. It costs little and occasionally yields a factorisation for free.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 245-247.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.