Multiplicative group of integers modulo n

In mathematics, the multiplicative group of integers modulo n is the group defined by multiplication of the units (that is, the numbers relatively prime to n) in the ring for a given integer n > 1. It is often denoted .

The order of the group is given by Euler's totient function. Thus for n prime, the order of the group is n - 1.

This group has many applications in number theory and cryptography. In particular, by finding the size of the group, one can determine if n is prime: n is prime if and only if the size of the group is n - 1. See primality test.

The multiplicative group is a cyclic group if and only if n = 2, n = 4, n = p^m, or n = 2p^m for some odd prime p and some m > 0. For all other cases, the 2-torsion subgroup is not cyclic (i.e. has a quotient that is a Klein four-group).

Using the Chinese remainder theorem, once we determine the structure of the group for prime powers, we can determine the structure of the group for all n. By the above, the group is cyclic for odd prime powers. For n = 2^k, the structure of the group is .