Let (G,*) be a Cyclic group of order ' n ': The number of Generators is G="Φ(n)"
Euler's totient function counts the positive integers up to a given integer n that are relatively prime (co- prime) to n.
Co-prime : It can be defined more formally as the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1.
For eg:
Number of generators of cyclic group of order 3 = Φ(3) ={1,2} = 2 generators .
Number of generators of cyclic group of order 7 = Φ(7) = {1,2,3,4,5,6} = 6 generators .
Number of generators of cyclic group of order 6 = Φ(6) ={1,5} = 2 generators .
------------------------------------------------------------------------------------------------------------------
Suppose if the number is large then what will u do : If n is very large then we need to do, split the n in such a way that it becomes multiplication of two prime numbers.
- n = p * q
- Φ(n) = Φ(p) * Φ(q)
for example: if we need to find out how many generators exists in cyclic group of order 77 then
77 = 7 * 11
Φ(77) = Φ(7) * Φ(11)
By above explanation, Φ(7) = 6 generators and Φ(11) = 10 generators.
So total number of generators will be = 6 * 10 = 60 generators in cyclic group of order 77.
------------------------------------------------------------------------------------------------------------------
Eg 2: Number of generators in cyclic group of order 35:
Φ(35) = Φ(7) * Φ(5)
= 6 * 4 =24 generators.
------------------------------------------------------------------------------------------------------------------
Another special cases: Number of generators in cyclic group of order 25:
Φ(25) = Φ(52)
General Formula is: if Φ(Pn) = Pn - Pn-1
Now Φ(25) = 52 - 5(2-1)
= 20 generators.
------------------------------------------------------------------------------------------------------------------
Eg: Number of generators in cyclic group of order 84:
84 = 22 * 3 * 7
Φ(84) = Φ(22 * 3 * 7)
= Φ(22) * Φ(3) * Φ(7)
= 22 - 2(2-1) * 2 * 6
= 24 Generators
