The exponent that is smaller than Euler's

Euler’s theorem says that a unit raised to the number of units gives one. It is the natural generalisation of Fermat’s and it is exactly true. It is also, for most moduli, not the best statement available — and the gap between what it says and what is true turns out to be exactly the gap a primality test leaks through.

Every order divides four. So $a^4 \equiv 1$ for all eight units, and Euler’s exponent of eight is doing no work that four does not already do. The eight units fall into rings of orders 1, 2, 2 and 4 rather than into one ring of eight, which is precisely the failure the residue whose powers are all of them locates: fifteen is neither a prime power nor twice one, so no generator exists and the largest order falls short of the count.

The smallest exponent that serves everything #

Define $\lambda(n)$ to be the smallest positive exponent with $a^{\lambda} \equiv 1$ for every unit $a$. It is the least common multiple of the orders, and since every order divides $\varphi(n)$ it divides $\varphi(n)$ too — so it is never larger and, as the figure shows, often smaller. It is called the Carmichael function, or the group’s exponent.

The two agree exactly when some unit has order $\varphi(n)$, which is exactly when a generator exists — so that theorem is the statement that $\lambda(p) = \varphi(p) = p-1$ for a prime, and the composite moduli where a generator fails are the ones where the two functions part.

How much smaller can $\lambda$ be? Considerably. The function multiplies across a factorisation in a way $\varphi$ does not: $\lambda(n)$ for $n$ a product of coprime pieces is the least common multiple of the pieces’ values, while $\varphi$ is the product. So a modulus with many prime factors, each of whose $p-1$ shares factors with the others, has a $\lambda$ far below its $\varphi$ — and the ratio can be made as large as one likes.

Where the gap comes from #

The two functions are computed from the same factorisation by two different rules, and setting the rules side by side is the whole explanation of why one is smaller.

For a prime power $p^k$, both are the same kind of object: $\varphi(p^k) = p^k - p^{k-1}$, and $\lambda(p^k)$ equals it as well, except for the powers of two above four, where $\lambda$ is half of $\varphi$. That exception is the reason sixteen has no generator, and it is the only exception among prime powers.

For a product of coprime pieces the rules diverge. The units modulo $n$ split into a product of the units modulo each piece — which is what two dials at once is about, stated multiplicatively, and the same splitting that makes a number’s divisor structure a product over its prime powers — so a unit is a list of one unit per piece, and raising it to a power raises each entry. Getting one in every entry therefore needs an exponent that is a multiple of each piece’s $\lambda$, and the smallest such is the least common multiple. Counting the units, on the other hand, multiplies.

$$\varphi(n) = \prod \varphi(p_i^{k_i}), \qquad \lambda(n) = \operatorname{lcm} \lambda(p_i^{k_i}).$$

A product against a least common multiple is where all the shrinkage lives. Modulo $3 \times 11 \times 17$ the totients of the pieces are $2, 10, 16$, whose product is $320$ and whose least common multiple is $80$ — a factor of four, from the twos the three pieces share. Choose primes whose predecessors share more and the factor grows without limit: the shrinkage is a statement about how much the numbers $p_i - 1$ have in common, and nothing prevents them from having a great deal.

Why a test can be fooled #

Fermat’s theorem is used backwards. To test whether $n$ is prime, pick a base $a$ and compute $a^{n-1}$ modulo $n$; if the answer is not one, $n$ is definitely composite. The test is fast — a few hundred squarings whatever the size of $n$ — and it is one-sided: passing proves nothing.

What does it take for a composite to pass? Exactly that $a^{n-1} \equiv 1$, which holds for every base coprime to $n$ precisely when $\lambda(n)$ divides $n-1$. The Carmichael function is not an aside; it is the quantity the test is really about. For $n=15$, $\lambda = 4$ and $n-1 = 14$, and four does not divide fourteen, so some base catches it. For $n = 561$, $\lambda = 80$ and $n - 1 = 560 = 7 \times 80$, and no base does.

A composite that passes for every base coprime to it is a Carmichael number. Since a base sharing a factor with $n$ gives away the factor immediately, such a number is invisible to Fermat’s test in any useful sense: the test can only be run at bases coprime to the modulus, and all of them say prime.

The criterion, which makes them findable #

Korselt stated the condition in 1899, sixteen years before anybody found a number satisfying it. A composite $n$ is a Carmichael number exactly when

1. $n$ is squarefree — no prime divides it twice — and
2. for every prime $p$ dividing $n$, $p - 1$ divides $n - 1$.

The reason is $\lambda$, computed from the factorisation. For $n$ squarefree with prime factors $p_1, \ldots, p_k$, the units split into a product of the units modulo each $p_i$, and $\lambda(n)$ is the least common multiple of the $p_i - 1$. So $\lambda \mid n-1$ is exactly condition 2. And if some prime divides $n$ twice, then $\lambda(n)$ is divisible by $p$, while $n-1$ is not — since $p$ divides $n$ — so condition 1 is forced.

The condition also shows that a Carmichael number needs at least three prime factors. Suppose $n = pq$ with $p < q$. Then $q - 1$ must divide $n - 1 = pq - 1 = p(q-1) + (p-1)$, so $q-1$ divides $p-1$, which is impossible for $p < q$. Two primes are never enough, and the smallest candidate is therefore a product of three.

Constructed rather than found #

A criterion that can be checked can be aimed at, and Chernick’s observation of 1939 is the cleanest way of aiming at this one. Take the three numbers $6k+1$, $12k+1$ and $18k+1$. If all three are prime, their product $n$ satisfies

$$n - 1 = 36k(36k^2 + 11k + 1),$$

which is divisible by $6k$, by $12k$ and by $18k$ — so condition 2 holds automatically, and the three primes are distinct so condition 1 does too. At $k=1$ the three are $7, 13, 19$ and the product is $1729$; at $k=6$ they are $37, 73, 109$ and the product is $294{,}409$.

That there is a construction changes the status of the phenomenon. Carmichael numbers are not rare accidents that one hopes to avoid by choosing candidates carefully — they can be produced to order, and Alford, Granville and Pomerance proved in 1994 that there are infinitely many, indeed at least $x^{2/7}$ of them below $x$. The proof is not a construction of the Chernick kind; it is an argument about how many products of primes from a suitable set satisfy the divisibility, and it settled a question that had been open since Carmichael asked it in 1912.

There is a second reading of condition 2 that is worth having, because it explains why these numbers feel like coincidences and are not.

$p - 1 \mid n - 1$ for every prime factor $p$ is a simultaneous divisibility, one condition per factor, and each is a condition on $n$ modulo something. For three given primes the conditions either all hold or they do not — there is nothing to adjust — so finding a Carmichael number means finding a set of primes whose predecessors all divide the product minus one. That is a search over sets rather than over numbers, and it is why the smallest one, $561$, is small while the density is thin: most triples fail and the ones that work can be engineered.

The engineering is the subject of the next section, and the shape of it is worth stating first. Write $n = pqr$. Then $n - 1 = pqr - 1$, and asking $p - 1 \mid pqr - 1$ is asking for a congruence between $qr$ and something modulo $p-1$ — three linked congruences, and the way to satisfy three linked congruences is to build the primes from a common parameter so that the links hold identically. A condition that must hold for a specific triple becomes easy once it is made to hold for a whole family at once, which is the standing tactic whenever a divisibility has to be arranged rather than checked.

How thin the leak is, measured #

The sweep puts a size on the problem and the size is the argument for how the test is actually used. Below two thousand there are a handful of composites that pass at base two, and almost all of them fail at base three — the bases that fool a given composite are a subgroup of its units, so if any base catches it, at least half do.

That last sentence is the whole reason a multi-base test works. The bases returning one form a subgroup; a subgroup that is not everything has index at least two; so at least half the bases catch a non-Carmichael composite, and $k$ random bases fail to catch it with probability at most $2^{-k}$. The failure mode is not a small probability but a total one, and it is confined to exactly the numbers Korselt’s criterion describes.

Which is why the Fermat test alone is not used and the repair is not more bases. The Miller–Rabin refinement, which the necklace proof states, watches the intermediate squarings for a square root of one that is neither $1$ nor $-1$. A Carmichael number cannot survive that, because a squarefree composite with three or more prime factors has at least eight square roots of one where a prime has two, and the extra ones are what the refinement looks for. So the refinement’s advantage over the plain test is precisely that it catches the class this essay is about, and its error probability is at most one in four per base for every composite, with no exceptional set at all.

The three primes are enough, and the argument that they are #

A Carmichael number needs three prime factors and the section above showed two cannot do. Whether three can is a separate question, and the answer is the whole of $561$: three, eleven and seventeen.

Take the smallest case seriously, because checking it by hand is the quickest way to see what the criterion is asking. $561 = 3 \times 11 \times 17$, and $560 = 2^4 \times 5 \times 7$. The three conditions are $2 \mid 560$, $10 \mid 560$ and $16 \mid 560$, and all three hold — $560 = 280 \times 2 = 56 \times 10 = 35 \times 16$. So $\lambda(561) = \operatorname{lcm}(2, 10, 16) = 80$, and $80$ divides $560$ seven times over.

What makes that arrangement possible is that $560$ is divisible by a high power of two and by both five and seven, so it has room for three predecessors at once. The next Carmichael numbers are $1105 = 5 \times 13 \times 17$ and $1729 = 7 \times 13 \times 19$, and each has the same character: a product minus one with enough small factors to be divisible by all three predecessors.

The three-factor case is where the phenomenon is cheapest and the infinitude is hardest. Every Carmichael number below ten thousand has exactly three prime factors, and the theorem that produces infinitely many of them produces ones with far more, for the reason the closing section gives. So the examples anybody meets and the examples anybody can prove exist are different examples, which is an unusual and honest state for a subject to be in.

What λ costs and what it gives #

It needs the factorisation. $\varphi(n)$ and $\lambda(n)$ are both computed from the prime factorisation of $n$ and neither is computable without one, as far as anybody knows. So the quantity the test is really about is inaccessible to the tester, which is the honest reason the test is stated with $n-1$ in the exponent rather than with $\lambda$.

It is not multiplicative. $\varphi$ multiplies across coprime factors, which makes it easy to tabulate; $\lambda$ takes a least common multiple instead, so it can stay small while $n$ grows, and its values are erratic. $\lambda(n)$ for $n$ up to forty takes only the values 1, 2, 4, 6, 10, 12, 16, 18 and a few more, and the sequence has no simple description. What can be said is a bound in the other direction: $\lambda(n)$ is at least about $\log n$, because a group in which every element satisfies $x^\lambda = 1$ has at most $\lambda$ elements of each order and cannot be too large — so the shrinkage, however severe, is bounded, and a modulus cannot have all its orders tiny.

It does not make the test better. Knowing that the right exponent is $\lambda(n)$ and not $n-1$ would let a tester ask the sharp question, and the tester cannot: computing $\lambda(n)$ needs the factorisation, and if the factorisation were available the primality would not be in question. So the whole subject is a description of a leak rather than a repair for it, and the repair — watching the intermediate squarings — comes from a different observation entirely.

And it is the sharp version of Euler’s theorem, so nothing is lost. Every statement Euler’s theorem makes, $\lambda$ makes too, and it makes some that Euler’s does not: that the units modulo sixteen all satisfy $a^4 = 1$ is false as a reading of Euler’s theorem and true as a reading of this one.

What the pictures cannot show #

The orders are computed by walking every unit’s orbit, which is why the figures are confined to moduli below forty for the order strips and to a few hundred for the base sweeps. Three hundred and twenty exponentiations modulo five hundred and sixty-one are instant; the same sweep at a modulus of two hundred digits is not a computation anybody performs, and it is not how the test is used.

Korselt’s criterion is drawn as a table of verdicts, and the table shows agreement rather than proving it. Both halves were computed for the numbers drawn — the criterion from the factorisation, the verdict from every base — and a number at which they disagreed would refuse to draw; that is evidence about the criterion at those numbers and not a proof of the equivalence, which is the paragraph of algebra above.

And nothing here shows the infinitude. Three Carmichael numbers below two thousand, seven below ten thousand, and the theorem says there are infinitely many — a statement about a density that no finite sweep approaches. The sweeps are what make the phenomenon concrete; the count is what makes it a subject.

Still open: how many there are, and how far apart #

The infinitude is proved and the density is not. Alford, Granville and Pomerance’s bound of $x^{2/7}$ below $x$ is far below what the heuristics predict, which is roughly $x^{1 - o(1)}$ — so the count is conjectured to be nearly as large as it could be and is known to be at least a small power. Closing that gap is open, and it has the same flavour as every other question about how thinly a condition on factorisations is satisfied — including how the primes themselves thin out, where the answer took a century and the method was not elementary.

The other open question is the reverse one and it is sharper. Are there infinitely many Carmichael numbers with exactly three prime factors? Chernick’s construction would give them if $6k+1$, $12k+1$ and $18k+1$ were simultaneously prime infinitely often, which is a case of a general conjecture about simultaneous primes in linear forms that nobody can prove for any such triple — not even for the pair $k$ and $k+2$, which is the twin prime question and is as far out of reach as the gap between a number and its double was not. So the smallest and most explicit family here rests on an unsolved problem about primes, and the general infinitude — proved — was obtained by a route that produces numbers with a great many factors instead.

What the two exponents are each for #

Euler’s theorem answers a question about every unit at once with a number that is easy to describe and usually too large. The Carmichael function answers the same question with the smallest number that works, and it is harder to describe, harder to compute, and the one the application depends on.

A statement that is true and not sharp can hide the thing it is about. Fermat’s test is stated in terms of $n-1$, and read that way the existence of composites passing it looks like bad luck. Read in terms of $\lambda$ it is not luck at all — the test asks whether $\lambda(n) \mid n-1$, that condition is satisfiable by composites, Korselt wrote down exactly which, and somebody can build one on request. The phenomenon was unexplained for as long as the sharp exponent was not named.

The general lesson is the one the sieve makes from the other direction: a test that can certify one answer and not the other should be described by what it actually measures, because the quantity it measures is where its exceptions live. Here the quantity is a least common multiple of orders, and every Carmichael number is a modulus where that least common multiple came out small.

There is one more reason to keep $\lambda$ in view, and it is practical rather than expository. The same function decides the exponents in RSA: the decryption exponent has to satisfy $ed \equiv 1$ modulo the exponent of the group, and using $\varphi(n)$ works while using $\lambda(n)$ works and gives a smaller $d$. The standard specification says $\lambda$ for exactly that reason. So the sharp version of a theorem stated in 1736 is the one a modern specification uses, and the reason is not elegance but the size of a number somebody has to store.