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

Good reads: http://sites.millersville.edu/bikenaga/abstract-algebra-1/cyclic-groups/cyclic-groups.pdf

---

Without checking the Cayley table,we can answer it directly by inspecting the options. Here, we see a is an identity element,so it can't be generator,hence throw option A and D right now. Generators can't exist in isolation,so if g is generator,so is g inverse. We see C and D are inverses of each other ,so it has to right  

---

$\color{Red}\text{Understand the solution:}$

https://youtu.be/83GuHnqT8UA?list=PLIPZ2_p3RNHhXves0XVa8d5O6F4rUi3KR&t=1786

Answer 1

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 2

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.

Answer 3

a*a=a, a*b=b, a*c=c, a*d=d
Clearly, from this first row of the table, a is an identity element, and identity element can't be a generator

Eg: Suppose we have set-> {1,2,3} and operation is multiplication modulo 4, so here identity element is 1, now see:

(1^1)mod 4=(1) mod 4=1
(1^2)mod 4=(1*1) mod 4=1
(1^3)mod 4=(1*1*1) mod 4=1

So, identity element keep on repeating the same number again & again, hence it can't be a generator.

So, options A and D are ruled out.

Now, from option B and C, c is common in both, so definitely, c is a generator, and now go to that row which contains c, there, c*d=a, which means, d is inverse of c, or c and d are inverses of each other and there is a property that, if an element is a generator then its inverse is also a generator, hence d is also a generator.
 

So, we are left with option C only.

Answer 4

In a group each element has a unique inverse , also inverse of identity element is itself. Now we observe from table that a is the identity element . How ? Find an element x such that x when operated with any element , gives that element itself (Here first row/column remains as it is after operation with a ).

Order of group is 4 , apart from identity element 3 elements are left. Now since remaining elements are odd in number , we can infer that one such element exists (apart from identity) such that the inverse of the element is that element itself. Why ? Since each element has unique inverse so elements and their respective inverses come in pair and if we form pairs(of the from { element,inverse(element) } ) then one element will be left alone and that element’s inverse is the element itself. Now check from table which element x when operated with itself gives identity element i.e find a x such that x * x = a. We find b is that element , so now the remaining 2 elements are inverse of each other i.e. c * d = a . Also if an element is a generator its inverse will also be a generator so option C is correct.