# GATE2009-22

2.8k views

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?

1. $a,b$ are generators
2. $b,c$ are generators
3. $c,d$ are generators
4. $d,a$ are generators

edited
8

1
Corrected previous table .

Now it is correct table.
4

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Here the identity element is $'a '$

------------------------------------------------------------------------

Note

If x is a generator the inverse(x) will be generator

------------------------------------------------------------------------

So the generators of the cyclic group will give the identity element when we do operation $'* '$ on them

Here,     $c*d=d*c=a$

So $c,d$ are generators .

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

0
Let you find a generator "x" for given group then x^m  will be also a generator but condition is GCD(m,n) =1 , where n is order of group (means total number of element in the group).

Also note that inverse of "x" will also be a generator of group.

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

edited by
0
can you please tell me how did u get c*c as b...we get d here as per the table given.
0
Is this a part of DMGT subject?
3
Yes, it is from Group Theory , from Discrete Math subject.
0
5
i want to add an additional information here that,,,if a group is cyclic then it will be abelian group but vice-versa need not to be true
7
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.
0
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
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.

$c^1 = c, c^2=c^1*c^1=d, c^3=c^2*c^1=d^c=a, c^4=c^3*c^1=a*c\\ d^1 = d, d^2=d^1*d^1=b, d^3=d^2*d^1=b^d=c, d^4=d^3*d^1=c*d=a\\$

$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)

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\}$

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.

edited by

## Related questions

1
1.9k views
Which one of the following is NOT necessarily a property of a Group? Commutativity Associativity Existence of inverse for every element Existence of identity
Consider the binary relation $R = \left\{(x,y), (x,z), (z,x), (z,y)\right\}$ on the set $\{x,y,z\}$. Which one of the following is TRUE? $R$ is symmetric but NOT antisymmetric $R$ is NOT symmetric but antisymmetric $R$ is both symmetric and antisymmetric $R$ is neither symmetric nor antisymmetric
A hard disk has $63$ sectors per track, $10$ platters each with $2$ recording surfaces and $1000$ cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number and $s$ is the sector number. Thus, the ... is $\langle 0, 15, 31 \rangle$ $\langle 0, 16, 30 \rangle$ $\langle 0, 16, 31 \rangle$ $\langle 0, 17, 31 \rangle$
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest common ... major order of $L[M, N]$. $L[p, q]$ needs to be computed before $L[r, s]$ if either $p<r$ or $q < s$.