Cyclic Group Element Coprime with Order is Generator

From ProofWiki

Jump to: navigation, search

Theorem

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

Let $C_n = \left \langle {a} \right \rangle$, that is, that $C_n$ is generated by $a$.

Then:

$C_n = \left \langle {a^k} \right \rangle \iff k \perp n$

That is, $C_n$ is also generated by $a^k$ iff $k$ is coprime to $n$.

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

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

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle a^m$	$=$	$\displaystyle a^{m u k + m v n}$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle a^{m u k}$	$\displaystyle $	$\displaystyle $	$\displaystyle $	as $a^{m v n} = e$
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle \left({a^k}\right)^{m u}$	$\displaystyle $	$\displaystyle $	$\displaystyle $

Thus $a^k$ generates $C_n$.

Then we suppose that $C_n = \left \langle {a^k} \right \rangle$, that is, $a^k$ generates $C_n$.

Thus $\exists u: a = \left({a^k}\right)^u$ as $a$ is an element of the group generated by $a^k$.

Thus $u k \equiv 1 \left({\bmod\, n}\right) \implies 1 = u k + v n$ for some $u, v \in \Z$, and thus $k \perp n$ as we wanted to show.

$\blacksquare$

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a^m\)	\(=\)	\(\displaystyle a^{m u k + m v n}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a^{m u k}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	as $a^{m v n} = e$
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({a^k}\right)^{m u}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)