Elements of multiplicative group equal generators of additive group

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.