Motivation
Why look beyond Euler's theorem
Euler's theorem says that whenever . The exponent always works, but it is often far from the smallest exponent that works for every unit at once. Modulo , the units are , and each of them squares to . So the exponent already annihilates every unit, although . Modulo , we will see that every unit satisfies , although .
This leads to a natural question: what is the smallest positive exponent such that for every unit ? The answer is Carmichael's function . It is also the right tool for a second question. Fermat's little theorem says that a prime satisfies for every coprime to . Which composite numbers satisfy for every coprime base? The answer, Korselt's criterion, becomes almost mechanical once is understood.
Throughout, . We write for the multiplicative group of residue classes modulo that are coprime to , so . For a unit , denotes its order in . We use the basic fact from finite group theory that if and only if .
The universal exponent
Definition 3.2.1
(Universal exponent and Carmichael's function)
Let . A positive integer is a universal exponent modulo if
By Euler's theorem, is a universal exponent, so the set of universal exponents is nonempty. Carmichael's function is the least universal exponent modulo .
Theorem 3.2.2
(Structure of universal exponents)
Let , and let be the least common multiple of the orders as ranges over . Then:
- a positive integer is a universal exponent modulo if and only if ;
- ;
- is a universal exponent if and only if , and in particular .
Proof
(Orders and their least common multiple)
The integer is a universal exponent exactly when for every unit . This happens exactly when for every unit . An integer is divisible by each member of a finite list of positive integers if and only if it is divisible by their least common multiple, so this condition is equivalent to . This proves (1).
By (1), the universal exponents are exactly the positive multiples of , and the least of these is itself. Hence , which is (2). Statement (3) restates (1) using (2). Since is a universal exponent by Euler's theorem, .
The divisibility in (3) is the important part. Minimality alone would only give . The structure theorem says more: every exponent that works for all units is a multiple of the least one.
Units only. The definition quantifies over units, and nothing more is true. If , then is impossible for every . Indeed, divides both and , so it would have to divide . For example, is , , or , and never .
Splitting the modulus with the Chinese remainder theorem
Theorem 3.2.3
(The lcm formula)
If and , then
Consequently, if with distinct primes , then
Proof
(Universal exponents for coprime factors)
Put . We show that a positive integer is a universal exponent modulo if and only if it is a universal exponent modulo both and .
Suppose first that is universal modulo , and let be any unit modulo . By the Chinese remainder theorem, choose an integer with
Then is coprime to because is, and coprime to because . Hence is coprime to . So , and reducing modulo gives . Thus is universal modulo , and symmetrically modulo .
Conversely, suppose is universal modulo both and , and let . Then is coprime to each , so and both divide . Because , their product divides .
By the structure theorem, the universal exponents modulo are therefore exactly the positive integers divisible by both and . These are the positive multiples of , and the least of them is that lcm.
The formula for a general follows by induction on . The prime powers are pairwise coprime, is coprime to , and the lcm is associative.
The theorem reduces the computation of to prime powers. Odd prime powers and powers of behave differently, so we treat them separately.
Odd prime powers
Theorem 3.2.4
(Odd prime powers)
If is an odd prime and , then .
Proof
(A generator has order )
We use the primitive-root theorem for odd prime powers, established earlier: is cyclic for every odd prime and every . Let be a generator. Then .
By the structure theorem, is a multiple of every unit order, so . The structure theorem also gives . Hence the two are equal.
The case gives , which we will use repeatedly.
Powers of two
Theorem 3.2.5
(Powers of two)
Proof
(Squaring for the upper bound, the unit for the lower bound)
Proof of the small cases. and , so . . Here and , so and .
Upper bound for . We prove by induction on that every odd satisfies
For , write . Then , and is even, so .
For the inductive step, suppose for some integer . Squaring gives
Since , the right side is , which is the statement for . Hence is a universal exponent modulo , and by the structure theorem.
Exact order of . We show that for every ,
that is, , where denotes the exponent of in the prime factorization.
For , we have , so is odd. If the claim holds for , then by the binomial theorem
Here is odd and is even, so is odd. This completes the induction.
Now fix . By the upper bound, divides , so it equals for some . Suppose . Then , so , which means . The claim with says this valuation is exactly , a contradiction. Hence .
Combining the two parts: because is a multiple of the order of , and by the upper bound. Therefore .
Proof X-ray
Anatomy of the power-of-two argument
- Upper bound. The squaring step turns the error term into . So the exponent needed to reach doubles when the modulus doubles.
- Lower bound. One explicit unit of large order suffices. For , the identity is proved directly by the binomial theorem. No unstated lifting lemma is used.
- Why . The base case uses . For , the formula would give , but . For , the formula does not even produce an integer.
The gap between and already appears at .
Counterexample mode
$\lambda(8)$ is strictly smaller than $\varphi(8)$
Modulo , we have , , , and , all . Since , the exponent does not work, so . But .
So no unit modulo has order , and is not cyclic. More generally, for we have . Hence there is no primitive root modulo . Thus the odd-prime-power primitive-root assertion used above does not extend to powers of two with exponent at least three.
The exponent also says nothing about non-units: , , and .
Worked example 3.2.6
(Computing )
Factor . By the lcm formula and the prime-power theorems,
while . So every unit modulo satisfies .
As a spot check, and . Note that divides , as the structure theorem requires, and the quotient is large.
Concept lensStructural
Carmichael's function as the exponent of a group
In group language, is the exponent of the finite abelian group : the least common multiple of the orders of its elements. In an abelian group this least common multiple is always attained. If commuting elements have coprime orders and , their product has order ; combining, for each prime, an element whose order has the largest power of that prime gives a unit of order exactly . Thus is cyclic exactly when , which fails at .
Carmichael numbers
Definition 3.2.7
(Carmichael number)
A Carmichael number is a composite integer such that
By the structure theorem, the defining condition says exactly that is a universal exponent modulo . So a composite is a Carmichael number if and only if .
Boundary cases. Primes are excluded by definition. For example, satisfies the congruence for every unit, by Fermat's little theorem, but it is not composite. The smallest composite number, , fails: , and concretely .
Theorem 3.2.8
(Korselt's criterion)
A composite integer is a Carmichael number if and only if
- is square-free, and
- for every prime .
Proof
(Two witnesses for necessity, the lcm formula for sufficiency)
Proof of necessity: square-freeness. Let be a Carmichael number, and suppose some prime has . Write with and . By the Chinese remainder theorem, choose with
If , take . Then and , so . Hence .
Since , reduce modulo , where . For any , the binomial theorem gives
With we get , so . But , so , a contradiction. The argument is valid for as well.
Proof of necessity: the divisibility condition. Let and write with . If , then divides everything, so assume is odd. By the case of the primitive-root theorem, there is a primitive residue modulo , that is, . Since , the integer is also a unit modulo , so it serves as a lift of the primitive residue. By the Chinese remainder theorem, choose with
Then , so . Reducing modulo gives . Therefore divides .
Proof of sufficiency. Let be composite and square-free, say with distinct primes, and suppose for each . By the odd-prime-power theorem, for odd , and by the power-of-two theorem. The lcm formula gives
Each divides , so their lcm divides . Thus , so is a universal exponent and is a Carmichael number.
Proof X-ray
Where each hypothesis is forced
- Square-free. The unit behaves like "" modulo . Raising it to the power would require , which is incompatible with .
- . A primitive residue modulo has order exactly . The Chinese remainder theorem plants it inside a unit modulo without disturbing the other prime factors.
- Sufficiency. For square-free , is the lcm of the numbers , and the hypothesis is exactly that each of these divides .
Worked example 3.2.9
(561 is a Carmichael number)
We have , which is composite and square-free, and . Check the three divisibilities:
By Korselt's criterion, is a Carmichael number. In the language of , we have and .
Euler's theorem alone does not explain this. Here , which does not divide . It is the smaller exponent that divides .
Worked example 3.2.10
(341 passes base 2 but is not Carmichael)
Take , which is square-free. Since , we have , so . The base cannot detect that is composite.
However, , so . Korselt's criterion therefore says some unit fails. Take :
- Modulo : . Since , we get .
- Modulo : Fermat gives , so . Now and , so .
Hence .
Counterexample mode
Square-free is not enough: $n=15$
The number is composite and square-free, but , so is not a Carmichael number. Here .
The proof's recipe produces a witness. The residue is primitive modulo , so solve and , giving . Then and , so .
Some bases nevertheless pass. Because for every unit, we have . So exactly the units with pass, namely . These are four of the eight units.
One base versus all bases
For a unit base satisfying , the Fermat test asks whether . Failure proves that is composite, by Fermat’s little theorem. Success proves nothing by itself: the worked example on shows that passes base , and passes base . A composite number that passes for one particular base is not thereby a Carmichael number.
The Carmichael condition is a statement about every unit. It is equivalent to the single divisibility . Verifying it directly from the definition would require checking residues. Korselt's criterion replaces this with one divisibility test per prime factor, but it presupposes the factorization of . This is why the criterion is a structural characterization rather than a shortcut for recognizing primes.
Bases sharing a factor with are outside the definition. In particular, , because while .
Common misconceptions
- "Minimal means merely smallest." The structure theorem gives more than minimality: every universal exponent is a multiple of .
- "Square-free composite numbers are Carmichael." The number is a counterexample. The divisibility condition is essential.
- "Passing one Fermat base means Carmichael, or prime." The number is a counterexample.
Common mistake
(Assuming )
This holds for odd prime powers and for , but fails for , , , and many others.
Common mistake
(Using for small )
The formula requires . The correct values for small are and .
Common mistake
(Applying a universal exponent to non-units)
It works only for units. A non-unit never has a power congruent to .
Exercises
Quick check
(Compute and compare it with .)
Solution
We have . By the lcm formula and the prime-power theorems,
On the other hand, .
Quick check
(Prove that is even for every . What happens when ?)
Solution · Answer
Let . Then , because , while . So . By the structure theorem, . For , we have and is odd, so the hypothesis is necessary.
Quick check
(Show that is a Carmichael number and compute .)
Solution · Answer
The number is composite and square-free, and . Thus , , and all divide , and Korselt's criterion applies. Moreover, and .
Quick check
(Prove that every Carmichael number is odd and has at least three distinct prime factors.)
Solution
Let be a Carmichael number. By Korselt's criterion, is square-free.
Oddness. Suppose . Since is composite and square-free, it has a prime factor , which is odd. Then is even and divides , which is odd. This is impossible.
At least three prime factors. A square-free composite number has at least two distinct prime factors. Suppose with primes . Then
Since , it follows that . But , a contradiction. Hence has at least three distinct prime factors, all of them odd.
Quick check
(Let be a Carmichael number. Prove that for every integer , including non-units.)
Solution
Let be a prime dividing . If , then both and are . If , Fermat's little theorem gives . By Korselt's criterion, , so and hence .
Thus every prime factor of divides . Since is square-free, it is the product of these pairwise coprime primes, so .
For example, with and , we get , even though . The congruence holds for all , while is guaranteed only for units.