Finite Cyclic Group has Euler Phi Generators

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $C_n$ be a (finite) cyclic group of order $n$.


Then $C_n$ has $\map \phi n$ generators, where $\map \phi n$ denotes the Euler $\phi$ function.


Proof

From List of Elements in Finite Cyclic Group, the elements of $G$ are:

$\set {g^k: g \in G, 0 \le k < n}$

From Power of Generator of Cyclic Group is Generator iff Power is Coprime with Order, $g^k$ generates $G$ if and only if $k \perp n$.

The result follows by definition of the Euler $\phi$ function.

$\blacksquare$


Sources