Question

find the generator of a cyclic group G of order 10 if 'a' is one of the generator of G​

Answer 1

Answer:

question samaz me nahi aaya

Answer 2

Answer:

Answer

Step-by-step explanation:

GATE Overflow

Log In Register

arrow_back Cyclic Group

S Harika

asked in Set Theory & Algebra Apr 14, 2017

1.5k views

1.5k views

1

How to find no. of generators of cyclic group of orden n ?

answer comment

1 Answer

Please log in or register to vote.

Best answer

6

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