GATE CSE 2009 | Question: 22

Question

For the composition table of a cyclic group shown below:
$$\begin{array}{|c|c|c|c|c|} \hline \textbf{*} & \textbf{a}& \textbf{b} &\textbf{c} & \textbf{d}\\\hline \textbf{a} & \text{a}& \text{b} & \text{c} & \text{d} \\\hline \textbf{b} & \text{b}& \text{a} & \text{d} &\text{c}\\\hline \textbf{c} & \text{c}& \text{d} & \text{b} & \text{a}\\\hline \textbf{d} & \text{d}& \text{c} & \text{a} & \text{b} \\\hline \end{array}$$
Which one of the following choices is correct?

• A. $a,b$ are generators
• B. $b,c$ are generators
• C. $c,d$ are generators
• D. $d,a$ are generators

Comments

Easiest solution:-

Observe table carefully you will find a is an identity element so a can't be the generator

Note: Identity element is generator iff order of group is 1

So option A and D both are eliminated

Now, c is present in both option B, C so don't check c. Now just check what is the inverse of c which is d so answer must be c, d

So, option C is correct

---

1. a identity hai → order 1 → never generator
    

2. (identity se group generate nahi hota) 

3. b ko dekho:

Row of b:
 

b * a = b
 

b * b = a
 

b * c = d
 

b * d = c

Cycle b → a = order = 2→ not generator

 c ko check karo:

Row:

c * a = c
 

c * b = d

 

c * c = b
 

c * d = a

Cycle:
 

c → d → a → b → back to c
 

Order = 4 → c is generator

4. d ko dekho:

Row:

d * a = d
d * b = c
d * c = a
d * d = b

Cycle:
d → c → a → b → back to d
Order = 4 → d is generator

 

So c and d are genrator.
option C

---

We know that if an element is inverse of itself and the order of group is greater than 2 then it cannot be a generator, since b is inverse of itself and a is identity element. c and d must be the generators since they are inverse to each other.

Answer 1

An element is a generator for a cyclic group if on repeated applications of it upon itself, it can generate all elements of group.
For example here: $a*a = a,$ then $(a*a)*a = a*a = a,$ and so on. Here, we see that no matter how many times we apply $a$ on itself, we cannot generate any other element except $a.$ So, $a$ is not a generator.

Now for $b, b*b = a.$ Then, $(b*b)*b = a*b = b, (b*b*b)*b = b*b = a,$ and so on. Here again, we see that we can only generate $a$ and $b$ on repeated application of $b$ on itself. So, $b$ is not a generator.

Now for $c, c*c = b.$ Then, $(c*c)*c = b*c = d, (c*c*c)*c = d*c = a, (c*c*c*c)*c = a*c = c.$ So, we see that we have generated all elements of group. So, $c$ is a generator.

For $d, d*d = b.$ Then $(d*d)*d = b*d = c, (d*d*d)*d = c*d = a, (d*d*d*d)*d = a*d = d.$ So, we have generated all elements of group from $d.$ So, $d$ is a generator.

$c$ and $d$ are generators.

Option (C) is correct.

http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2009.html

Comments

When we have found c as a generator, note that in a cyclic group if g is a generator so $g^{-1}$ is also a generator.

Since a is the identity element of the group, $c^{-1}$ is d, so d is also a generator.

---

Proof that b is not a generator:

if b's power is even:   b^(2n) = b^2 * b^2 * ........ n times = a * a * ........ n times  = a

if b's power is odd:   b^(2n+1) = b^(2n) * b= a * b = b

Hence b can only generate a and b

---

nice explaination

Answer 2

a * a = a. So a can not generate anything other than a. In fact a is identity so a can not be generator.

So this eliminates Option A & D.

b*b = a. Also a is just identity, so b*a=a*b = a. So b can not generate all elements . So Option B is out.

So Answer is C.

Answer 3

$1.$ Let $(G,*)$ be a multiplicative group and $e$ is identity.  The smallest postive integer $m$ such that $x^m=e$ is called order of x

$2.$ An element $x\in G$ such that $O(x)=O(G)$ is called generator of group $(G,*)$

$3.$ A group having atleast one generator is called Cyclic Group

$4.$ The number of generators in a cyclic group of order $n=\phi(n)$

$5.$ $\phi(n)=$ No. of positive integers less than n and relatively prime to n.

$6.$ $\phi(n)=n(1-\frac{1}{p1})(1-\frac{1}{p2}).....(1-\frac{1}{pk})$ where $p1,p2...pk$ are distinct prime factors of n.

---

$G=\{\{a,b,c,d\},*\}$

$\phi(4)=4(1-\frac{1}{2})=2$ $\{1,3\}$

$a^2=a|$ $O(a)\neq O(G)$

$b^2=a|$ $O(b)\neq O(G)$

$c^2=b|c^3=c^2*c=b*c=d|c^4=c^2*c^2=b*b=a|$ $O(c)= O(G)$

Now, either you can continue finding other generators using brute force or after finding one generator you can easily find other generators by putting that generator to the power of $\{1,3\}$  for this question.

$c^1=c$ (Which we already find out as one of the generator)

$c^3=c^2*c=b*c=d$ (We have found another generator which is d)

Correct Answer: C

Answer 4

Answer is C.

Answer 5

Let G be a group and let $a\in G$

The " subgroup generated by a " is the subgroup $\{a^n|n\in Z\}$

$\{...(a^{-1})^2,a^{-1},e,a^1,a^2,a^3...\}=<a>$

Now,

A group is called cyclic if there exists an element $a\in G$ s.t  $<a>=G$ i.e

$G= \{...(a^{-1})^2,a^{-1},e,a^1,a^2,a^3...\}$

---

$<c>=\{e,c^1,c^2,c^3,c^4...\}=\{e,c,b,d,a\}$

$<d>=\{e,d^1,d^2,d^3,d^4...\}=\{e,d,b,c,a\}$

 

Correct answer is (C)

Answer 6

1. From the properties of cyclic group, we know that –

if the order of the group, $O(G) > 1$ then it can’t be generated by the identity element.

from the Cayley table we found that –

the identity element is $a$ and

$b$ inverse is $b$(self inverse)

$c$ inverse is $d$.

therefore, $G ≠  <a>$ (G isn’t generated by $a$), option A and D can’t be the answer.

2. If a group is generated by an element then  it is also generated by its inverse. (property of cyclic group) 
3. if a cyclic group has oder $n$ then the no. of generators  = $Ψ(n) = n(1−1p1)(1−1p2).....(1−1pk)ϕ(n)=n(1−1p1)(1−1p2).....(1−1pk) where p1, p2...pkp1,p2...pk are distinct prime factors of n.)$ 

∴ The group has 2 generators. $[ $4 = 2^2$]$

If option  B is the answer and c is the generator then $d$ will also be the generator. but the group can’t have 3 generators, Option B is wrong.

Answer: Option $C$ i.e. $c, d$ are the generators.

 

Comments

Great explanation.