Elements of multiplicative group equal generators of additive group

From Groupprops
Jump to: navigation, search

Statement

Let n be a positive integer, and consider the group of integers modulo n. Then, an element in this is a generator for the group of integers modulo n if and only if it is an element of the multiplicative group modulo n.

Note that these are also the same as the elements in \{0,1,2,\dots,n-1\} that are relatively prime to n, and the number of such elements is \varphi(n).

Proof

Generator of additive group implies element of multiplicative group

If x is a generator of \mathbb{Z}/n\mathbb{Z}, then some integer multiple of x must be equal to the element 1 \in \mathbb{Z}/n\mathbb{Z}. Thus, there exists m such that mx = 1 in \mathbb{Z}/n\mathbb{Z}. Viewing m as a congruence class modulo n, we see that x is invertible modulo n, and hence is in the multiplicative group.

Element of multiplicative group implies generator of additive group

If x is a element of the multiplicative group modulo n, there exists an integer m such that mx = 1 \mod n. Thus, the cyclic subgroup containing x must also contain 1. But any subgroup containing 1 must equal the whole group \mathbb{Z}/n\mathbb{Z}, so x generates the whole group.