GATE CS 2009 Q22 — Monoids and Groups

To find the generators of the given cyclic group $G = \{a, b, c, d\}$ of order $4$, we first identify the identity element and then compute the order of each element. An element $g \in G$ is a generator if and only if its order is equal to the order of the group, which is $4$ (i.e., $g^4 = e$ and $g^k \neq e$ for $1 \le k < 4$, where $e$ is the identity element).

Step 1: Identify the Identity Element

Looking at the row and column for $a$ in the composition table:

• $a * a = a,\; a * b = b,\; a * c = c,\; a * d = d$
• $a * a = a,\; b * a = b,\; c * a = c,\; d * a = d$

Since operating any element with $a$ leaves the element unchanged, $a$ is the identity element of the group.

Step 2: Determine the Order of Each Element

• For element $b$:
  • $b^1 = b$
  • $b^2 = b * b = a$ (identity)
  Since $b^2 = a$, the order of $b$ is $2$. Thus, $b$ is not a generator.


• For element $c$:
  • $c^1 = c$
  • $c^2 = c * c = b$
  • $c^3 = c^2 * c = b * c = d$
  • $c^4 = c^3 * c = d * c = a$ (identity)
  Since the smallest positive integer $k$ for which $c^k = a$ is $4$, the order of $c$ is $4$. Thus, $c$ is a generator.


• For element $d$:
  • $d^1 = d$
  • $d^2 = d * d = b$
  • $d^3 = d^2 * d = b * d = c$
  • $d^4 = d^3 * d = c * d = a$ (identity)
  Since the smallest positive integer $k$ for which $d^k = a$ is $4$, the order of $d$ is $4$. Thus, $d$ is a generator.

Therefore, the generators of the group are $c$ and $d$.