Engineering / Mathematics — Primality Testing
The Structure of the Group of Units Modulo n
The structure of Z_n* as a product of cyclic groups, the Carmichael function, and why prime moduli behave differently.
Executive summary
The group of units modulo n decomposes by the Chinese remainder theorem into a product of groups modulo each prime power. Each factor is cyclic except for powers of two above the fourth.
This structure determines everything about primality testing and discrete logarithms modulo composite numbers.
Learning objectives
- State the decomposition of Z_n* into prime power factors.
- Give the structure of each factor.
- Define the Carmichael function and distinguish it from Euler's phi.
01The decomposition
Structure of the unit group
For n = p₁^e₁ ··· pₖ^eₖ,
Z_n* ≅ Z_{p₁^e₁}* × ··· × Z_{pₖ^eₖ}*.
Each factor for odd p is cyclic of order p^{e−1}(p−1). For p = 2: Z₂* is trivial, Z₄* is cyclic of order 2, and Z_{2^e}* for e ≥ 3 is a product of a cyclic group of order 2 and one of order 2^{e−2}.
The exception at powers of two is genuine and consequential. It is why x² ≡ 1 (mod 8) has four solutions rather than two, and why the analysis of primality tests treats even moduli separately.
02The Carmichael function
Carmichael function
λ(n) is the smallest positive integer such that a^{λ(n)} ≡ 1 (mod n) for every unit a.
It is the exponent of the group Z_n*, and it divides φ(n).
| n | φ(n) | λ(n) | Cyclic? |
|---|---|---|---|
| 7 | 6 | 6 | Yes |
| 8 | 4 | 2 | No |
| 15 | 8 | 4 | No |
| 16 | 8 | 4 | No |
| p prime | p−1 | p−1 | Yes |
The two coincide exactly when Z_n* is cyclic, which happens for n = 1, 2, 4, p^e and 2p^e with p an odd prime, and for no other n.
For RSA, λ(n) may be used in place of φ(n) when deriving the private exponent, giving a smaller d and slightly faster decryption. Both are valid because λ divides φ.
03Consequences for primality testing
A primality test works by finding a property that holds for prime moduli and usually fails for composite ones. The structure above explains both when it holds and how it fails.
Prime modulus
Z_p* is cyclic of order p−1, so x² = 1 has exactly two solutions: 1 and −1.
Composite modulus
The group is a product of at least two non-trivial factors, so x² = 1 has at least four solutions.
The exploit
Miller–Rabin detects a square root of 1 other than ±1, which cannot exist modulo a prime.
This is why Miller–Rabin succeeds where the Fermat test fails. The Fermat condition tests only the group order; Miller–Rabin additionally tests the number of square roots of unity, which is a structural property no composite can fake.
04Frequently asked questions
Why is Z_{2^e}* not cyclic for e ≥ 3?
Because both 1 and 2^{e−1} − 1 and 2^{e−1} + 1 and −1 square to 1, giving four square roots of unity. A cyclic group of even order has exactly two, so the group cannot be cyclic.
Is finding λ(n) as hard as factoring?
Yes, by the same argument as for φ(n). Knowledge of either yields the factorisation of a semiprime in polynomial time.
Why does cyclicity matter for cryptography?
Because it guarantees a generator exists, so the group is a faithful copy of the integers modulo its order under addition. The discrete logarithm is the isomorphism, and its difficulty is what the schemes rest on.
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.