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

From ProofWiki
Jump to navigation Jump to search

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

Then by Integer Combination of Coprime Integers:

$\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$


Sources