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