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:

\(\ds a^m\) \(=\) \(\ds a^{m \paren 1}\) Integer Multiplication Identity is One
\(\ds \) \(=\) \(\ds a^{m \paren {u k + v n} }\) as shown above
\(\ds \) \(=\) \(\ds a^{m \paren {u k} + m v n}\) Integer Multiplication Distributes over Addition
\(\ds \) \(=\) \(\ds a^{m \paren {u k} } a^{m v n}\) Product of Powers
\(\ds \) \(=\) \(\ds a^{m \paren {u k} } e\) as $a^{m v n} = e$
\(\ds \) \(=\) \(\ds a^{m \paren {u k} }\) Definition of Identity Element
\(\ds \) \(=\) \(\ds a^{\paren {m u} k}\) Integer Multiplication is Associative
\(\ds \) \(=\) \(\ds a^{k \paren {m u} }\) Integer Multiplication is Commutative
\(\ds \) \(=\) \(\ds \paren {a^k}^{m u}\) Power of Power

Thus $a^k$ generate $C_n$.

$\Box$


Although this article appears correct, it's inelegant. There has to be a better way of doing it.
In particular: Do we really need all the above clutter? The arithmetic properties of the integers are really not under the microscope here -- is it really necessary to go blow by blow through all this?
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by redesigning it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Improve}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



Sufficient Condition

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

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

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

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Power_of_Generator_of_Cyclic_Group_is_Generator_iff_Power_is_Coprime_with_Order&oldid=676894"