A cyclic group of order n has ϕ(n) generators

Dependencies:

1. Cyclic Group
2. Euler's Totient Function
3. Order of elements in cyclic group

A cyclic group $\langle a \rangle$ of order $n$ has $\phi(n)$ generators.

Proof

$\operatorname{order}(a^k) = \frac{n}{\gcd(k, n)}$.

For $a^k$ to be a generator, it should have order $n$. So $\gcd(k, n) = 1$. That means $k$ can take $\phi(n)$ values. Therefore, $\langle a \rangle$ has $\phi(n)$ generators.

Dependency for: None

Info:

• Depth: 5
• Number of transitive dependencies: 14

Transitive dependencies:

1. Euler's Totient Function
2. Coprime
3. Integer Division Theorem
4. GCD is the smallest Linear Combination
5. Common divisor divides GCD
6. gcd(a1/d, a2/d, ..., an/d) = gcd(a1, a_2, ..., an)/d
7. If x divides ab and x is coprime to a, then x divides b
8. Group
9. Identity of a group is unique
10. Subgroup
11. Inverse of a group element is unique
12. Conditions for a subset to be a subgroup
13. Cyclic Group
14. Order of elements in cyclic group