Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| (6 intermediate revisions by the same user not shown) | |||
| Line 9: | Line 9: | ||
! d | ! d | ||
|- | |- | ||
| − | |b | + | !a |
| − | |b | + | |a |
| + | | b | ||
| + | | c | ||
| + | | d | ||
| + | |- | ||
| + | !b | ||
| + | | b | ||
| a | | a | ||
| d | | d | ||
| c | | c | ||
|- | |- | ||
| − | + | !c | |
| c | | c | ||
| + | | b | ||
| d | | d | ||
| − | |||
| a | | a | ||
|- | |- | ||
| − | + | !d | |
| d | | d | ||
| c | | c | ||
| + | | a | ||
| b | | b | ||
| − | |||
|} | |} | ||
Which one of the following choices is correct? | 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 | |
==={{Template:Author|Happy Mittal|{{mittalweb}} }}=== | ==={{Template:Author|Happy Mittal|{{mittalweb}} }}=== | ||
An element is a generator for a cyclic group if on repeated applications of it upon itself, it can generate all | An element is a generator for a cyclic group if on repeated applications of it upon itself, it can generate all | ||
elements of group. | elements of group. | ||
| − | + | ||
| − | For example here : a*a = | + | 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. | + | we can't generate any other element except $a$, so $a$ is not a generator. |
| − | + | ||
| − | Now for b, b*b = | + | 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. | + | on repeated application of $b$ on itself. So it is not a generator. |
| − | + | ||
| − | Now for c, c*c = | + | 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$. We see that we have generated |
| − | all elements of group | + | all elements of group, so $c$ is a generator. |
| − | + | ||
| − | For d, d*d = | + | 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$. We have generated all elements |
| − | of group from d, so d is a generator. | + | of group from $d$, so $d$ is a generator. |
| − | + | ||
| − | + | Thus $c$ and $d$ are generators. So option <b>(C)</b> is correct. | |
| Line 59: | Line 65: | ||
[[Category: GATE2009]] | [[Category: GATE2009]] | ||
| − | [[Category: Graph Theory questions]] | + | [[Category: Graph Theory questions from GATE]] |
For the composition table of a cyclic group shown below
| * | a | b | c | d |
|---|---|---|---|---|
| a | a | b | c | d |
| b | b | a | d | c |
| c | c | b | d | a |
| d | d | c | a | b |
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
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$. 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$. We have generated all elements of group from $d$, so $d$ is a generator.
Thus $c$ and $d$ are generators. So option (C) is correct.
For the composition table of a cyclic group shown below
| * | a | b | c | d |
|---|---|---|---|---|
| b | b | a | d | c |
| c | c | d | b | a |
| d | d | c | b | a |
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
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.
GATECSE