# Power of Generator of Cyclic Group is Generator iff Power is Coprime with Order

## Theorem

Let $C_n$ be the cyclic group of order $n$.

Let $C_n = \gen a$, that is, that $C_n$ is generated by $a$.

Then:

$C_n = \gen {a^k} \iff k \perp n$

That is, $C_n$ is also generated by $a^k$ if and only if $k$ is coprime to $n$.

## Proof

### Necessary Condition

Let $k \perp n$.

$\exists u, v \in \Z: 1 = u k + v n$

So $\forall m \in \Z$, we have:

 $\displaystyle a^m$ $=$ $\displaystyle a^{m u k + m v n}$ $\displaystyle$ $=$ $\displaystyle a^{m u k}$ as $a^{m v n} = e$ $\displaystyle$ $=$ $\displaystyle \paren {a^k}^{m u}$

Thus $a^k$ generate $C_n$.

$\Box$

### Sufficient Condition

Let $C_n = \gen {a^k}$.

That is, let $a^k$ generate $C_n$.

 $\displaystyle \exists u \in \Z: \ \$ $\displaystyle a$ $=$ $\displaystyle \paren {a^k}^u$ as $a$ is an element of the group generated by $a^k$ $\displaystyle \leadsto \ \$ $\displaystyle u k$ $\equiv$ $\displaystyle 1$ $\displaystyle \pmod n$ $\displaystyle \leadsto \ \$ $\displaystyle \exists u, v \in \Z: \ \$ $\displaystyle 1$ $=$ $\displaystyle u k + v n$ $\displaystyle \leadsto \ \$ $\displaystyle k$ $\perp$ $\displaystyle n$ Integer Combination of Coprime Integers

$\blacksquare$