= Generators of a finite cyclic group
{title2=$\langle k\rangle=C_n\iff\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 $\varphi(n)$ choices, where $\varphi$ is the <Euler totient function>.
For $C_6$, the two choices are $1$ and $5$, so $\varphi(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 $\langle g\rangle$ 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.
Back to article page
