# 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.