Generators of a finite cyclic group ($⟨k⟩=C_n⟺\gcd (n,k)=1$)

An element $k$ of the additive finite cyclic group $C_n=\mathbb{Z}/n\mathbb{Z}$ is a generator of a group precisely when $\gcd (n,k)=1$. The order of an element of a finite cyclic group proves this immediately: its cyclic subgroup has size $n/\gcd (n,k)$, and this equals $n$ exactly when the greatest common divisor is one. There are therefore $\phi (n)$ choices, where $\phi$ is the Euler totient function.

For $C_6$, the two choices are $1$ and $5$, so $\phi (6)=2$. For $C_8$, they are $1,3,5,7$. Starting from zero and repeatedly adding $3$ modulo eight gives $0,3,6,1,4,7,2,5,0$, visiting every element once before returning. By contrast, adding $2$ gives $0,2,4,6,0$ and misses the odd integers represented in the other coset.

If the cyclic group is written multiplicatively as $⟨g⟩$ with $g$ of order $n$, the same statement says that $g^k$ is a generator of a group exactly when $k$ and $n$ are coprime. This changes notation without changing the calculation.