Multiplicative group mod n

The multiplicative group of integers modulo n, written (ℤ/nℤ)ˣ (also U(n)), is the group of residues coprime to n under multiplication mod n. It is abelian of order φ(n), where φ is Euler's totient.

Definition

(ℤ/nℤ)ˣ  =  { a mod n : gcd(a, n) = 1 },   under multiplication mod n.

A residue a is invertible mod n exactly when gcd(a, n) = 1, so these are the units of the ring ℤ/nℤ; hence |(ℤ/nℤ)ˣ| = φ(n).

Structure

By the Chinese remainder theorem, if n = p₁^k₁ ⋯ pᵣ^kᵣ then

(ℤ/nℤ)ˣ  ≅  (ℤ/p₁^k₁ℤ)ˣ × ⋯ × (ℤ/pᵣ^kᵣℤ)ˣ,

and every prime-power factor is known exactly:

modulus `m`	`(ℤ/mℤ)ˣ`
`2`	trivial
`4`	`C₂`
`2ᵏ`, `k ≥ 3`	`C₂ × C_2^k-2`
`pᵏ`, `p` odd prime	`C_p^k-1(p-1)` (cyclic)

Cyclic case (primitive roots)

(ℤ/nℤ)ˣ is cyclic — a primitive root mod n exists — if and only if

n ∈ { 1, 2, 4, pᵏ, 2pᵏ }     for an odd prime p.

For every other n it is a non-trivial direct product, e.g. (ℤ/8ℤ)ˣ = C₂ × C₂ and (ℤ/15ℤ)ˣ = C₂ × C₄.

Which groups occur

Not every finite abelian group is a unit group:

C₃ never occurs — no n has φ(n) = 3 (φ(n) is even for n > 2).
C₈ never occurs — φ(n) = 8 holds for n ∈ {15, 16, 20, 24, 30}, but none of these has a cyclic unit group.

A group may occur for several moduli: C₆ = (ℤ/7ℤ)ˣ = (ℤ/9ℤ)ˣ = (ℤ/14ℤ)ˣ = (ℤ/18ℤ)ˣ. Whether every attained order is attained by at least two moduli is Carmichael's totient conjecture, still open.

Examples