Multiplicative group of integers modulo n

From Wikipedia, the free encyclopedia

In mathematics, the multiplicative group of integers modulo n is the group with multiplication as group operation and as elements the units in the ring

for a given integer n > 1. Units are the numbers having multiplicative inverses in the sense of modular arithmetic, modulo n. In this case those are more simply described as the residue classes of the numbers relatively prime to n. It is often denoted

or

.

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.

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. A cyclic group always has a generator; a generator of the multiplicative group modulo n is called a primitive root of n.

For all other cases, the 2-torsion subgroup is not cyclic (i.e. has a quotient that is a Klein four-group). For the smallest values of n we have: for n = 8, 12 the group is isomorphic to Z₂ × Z₂, and for n = 15, 16 to Z₄ × Z₂.

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 .