Difference between revisions of "GATE2009 q22"

Revision as of 12:28, 14 July 2014

For the composition table of a cyclic group shown below

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

Solution by Happy Mittal

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 can't 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. Then (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 it is not a generator.
Now for c, c*c = b. Then (c*c)*c = b*c = d. Then (c*c*c)*c = d*c = a. Then (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. Then (d*d*d)*d = c*d = a. Then (d*d*d*d)*d = a*d = d. So we have generated all elements of group from d, so d is a generator.
So c and d are generators. So option (C) is correct.