Multiplicative group of integers modulo n

The group ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ is cyclic if and only if n is 1, 2, 4, p^k or 2p^k, where p is an odd prime and k > 0. For all other values of n the group is not cyclic.[1][2][3] This was first proved by Gauss.[4]

This means that for these n:

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \mathrm {C} _{\varphi (n)},}$ where ${\displaystyle \varphi (p^{k})=\varphi (2p^{k})=p^{k}-p^{k-1}.}$

By definition, the group is cyclic if and only if it has a generator g (a generating set {g} of size one), that is, the powers ${\displaystyle g^{0},g^{1},g^{2},\dots ,}$ give all possible residues modulo n coprime to n (the first ${\displaystyle \varphi (n)}$ powers ${\displaystyle g^{0},\dots ,g^{\varphi (n)-1}}$ give each exactly once). A generator of ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ is called a primitive root modulo n.[5] If there is any generator, then there are ${\displaystyle \varphi (\varphi (n))}$ of them.

Modulo 1 any two integers are congruent, i.e., there is only one congruence class, [0], coprime to 1. Therefore, ${\displaystyle (\mathbb {Z} /1\,\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}$ is the trivial group with φ(1) = 1 element. Because of its trivial nature, the case of congruences modulo 1 is generally ignored and some authors choose not to include the case of n = 1 in theorem statements.

Modulo 2 there is only one coprime congruence class, [1], so ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}$ is the trivial group.

Modulo 4 there are two coprime congruence classes, [1] and [3], so ${\displaystyle (\mathbb {Z} /4\mathbb {Z} )^{\times }\cong \mathrm {C} _{2},}$ the cyclic group with two elements.

Modulo 8 there are four coprime congruence classes, [1], [3], [5] and [7]. The square of each of these is 1, so ${\displaystyle (\mathbb {Z} /8\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$ the Klein four-group.

Modulo 16 there are eight coprime congruence classes [1], [3], [5], [7], [9], [11], [13] and [15]. ${\displaystyle \{\pm 1,\pm 7\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$ is the 2-torsion subgroup (i.e., the square of each element is 1), so ${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }}$ is not cyclic. The powers of 3, ${\displaystyle \{1,3,9,11\}}$ are a subgroup of order 4, as are the powers of 5, ${\displaystyle \{1,5,9,13\}.}$   Thus ${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{4}.}$

The pattern shown by 8 and 16 holds[6] for higher powers 2^k, k > 2: ${\displaystyle \{\pm 1,2^{k-1}\pm 1\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$ is the 2-torsion subgroup (so ${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }}$ is not cyclic) and the powers of 3 are a cyclic subgroup of order 2^{k − 2}, so ${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2^{k-2}}.}$

By the fundamental theorem of finite abelian groups, the group ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ is isomorphic to a direct product of cyclic groups of prime power orders.

More specifically, the Chinese remainder theorem[7] says that if ${\displaystyle \;\;n=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\dots ,\;}$ then the ring ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ is the direct product of the rings corresponding to each of its prime power factors:

${\displaystyle \mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} \dots \;\;}$

Similarly, the group of units ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ is the direct product of the groups corresponding to each of the prime power factors:

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong (\mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} )^{\times }\dots \;.}$

For each odd prime power ${\displaystyle p^{k}}$ the corresponding factor ${\displaystyle (\mathbb {Z} /{p^{k}}\mathbb {Z} )^{\times }}$ is the cyclic group of order ${\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}}$, which may further factor into cyclic groups of prime-power orders. For powers of 2 the factor ${\displaystyle (\mathbb {Z} /{2^{k}}\mathbb {Z} )^{\times }}$ is not cyclic unless k = 0, 1, 2, but factors into cyclic groups as described above.

The order of the group ${\displaystyle \varphi (n)}$ is the product of the orders of the cyclic groups in the direct product. The exponent of the group, that is, the least common multiple of the orders in the cyclic groups, is given by the Carmichael function ${\displaystyle \lambda (n)}$ (sequence A002322 in the OEIS). In other words, ${\displaystyle \lambda (n)}$ is the smallest number such that for each a coprime to n, ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$ holds. It divides ${\displaystyle \varphi (n)}$ and is equal to it if and only if the group is cyclic.

The smallest example with a nontrivial subgroup of false witnesses is 9 = 3 × 3. There are 6 residues coprime to 9: 1, 2, 4, 5, 7, 8. Since 8 is congruent to −1 modulo 9, it follows that 8⁸ is congruent to 1 modulo 9. So 1 and 8 are false positives for the "primality" of 9 (since 9 is not actually prime). These are in fact the only ones, so the subgroup {1,8} is the subgroup of false witnesses. The same argument shows that n − 1 is a "false witness" for any odd composite n.

For n = 91 (= 7 × 13), there are ${\displaystyle \varphi (91)=72}$ residues coprime to 91, half of them (i.e., 36 of them) are false witnesses of 91, namely 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88, and 90, since for these values of x, x⁹⁰ is congruent to 1 mod 91.

n = 561 (= 3 × 11 × 17) is a Carmichael number, thus s⁵⁶⁰ is congruent to 1 modulo 561 for any integer s coprime to 561. The subgroup of false witnesses is, in this case, not proper; it is the entire group of multiplicative units modulo 561, which consists of 320 residues.