GATE CS

Monoids and groups

A group is a set with one associative operation that has an identity and gives every element an inverse. The skills this topic needs are testing these properties for an operation given by a formula or a table, and using Lagrange's theorem, element orders and cyclic groups to count elements and subgroups quickly.

7 previous-year questions · 7 solved · 6 practice questions

Binary operations and their properties

A binary operation $*$ on a set $S$ assigns to each ordered pair $(a, b)$ with $a, b \in S$ an element $a * b$ . It is closed on $S$ if $a * b \in S$ for all $a, b \in S$ (defining a binary operation as a map $S \times S \to S$ builds closure in). Check closure first; many failures happen here (for example, subtraction on ${1, 2, 3, \dots}$ , since $1 - 2 = - 1$ ). Conventions used below: $e$ is the identity, $∣ G ∣$ is the number of elements of $G$ , $Z_{n} = {0, 1, \dots, n - 1}$ under addition modulo $n$ , $a^{k} = a * a * \dots * a$ ( $k$ factors) for $k \geq 1$ , $a^{0} = e$ and $a^{- k} = (a^{- 1})^{k}$ . In additive notation $a^{k}$ is written $k a$ and $e$ is written $0$ .

Properties to check, in order

Closure: $a * b \in S$ for all $a, b \in S$ .
Associativity: $(a * b) * c = a * (b * c)$ for all $a, b, c \in S$ .
Identity: some $e \in S$ has $e * a = a * e = a$ for all $a \in S$ . If an identity exists it is unique.
Inverses: for each $a$ there is $a^{- 1} \in S$ with $a * a^{- 1} = a^{- 1} * a = e$ . In a monoid (so in a group) an inverse, when it exists, is unique.
Commutativity: $a * b = b * a$ for all $a, b$ (needed only for an abelian group).

Operation given by a formula. To find the identity, solve $a * e = a$ for $e$ , confirm that $e$ does not depend on $a$ and lies in $S$ , and check $e * a = a$ too unless $*$ is commutative. To find an inverse, solve $a * x = e$ for $x$ , check $x \in S$ , and check $x * a = e$ too unless $*$ is commutative. One counterexample disproves a property; proving one needs an argument for all elements.

Operation given by a table (rows and columns listed in the same order). Closure: every entry belongs to the set. Commutativity: the table is symmetric about the main diagonal. Identity: one element $e$ whose row repeats the header row and whose column repeats the header column. Inverses: for each element $a$ some $b$ has $a * b = b * a = e$ , so the $e$ entries sit in symmetric positions and every row and column contains $e$ . Associativity cannot be read off the table; it must be checked on triples or known from how the operation is defined.

EXAM TIP

A table in which every row and every column contains each element exactly once (a Latin square) does not by itself make a group, because associativity may fail. Conversely, a missing identity or a row or column with a repeated entry rules out a group quickly.

NUMBER OF BINARY OPERATIONS ON AN N-ELEMENT SET

n^{n^{2}} in all, n^{n (n + 1) /2} commutative

A binary operation on a set of $n$ elements is a filled $n \times n$ table, each of its $n^{2}$ entries chosen from the $n$ elements. A commutative one is fixed by the $n (n + 1) /2$ entries on and above the main diagonal. For $n = 2$ : $16$ in all, $8$ commutative.

Semigroups, monoids and groups

What each structure requires

Structure	Closure	Associative	Identity	Inverses	Commutative
Semigroup	Yes	Yes	No	No	No
Monoid	Yes	Yes	Yes	No	No
Group	Yes	Yes	Yes	Yes	No
Abelian group	Yes	Yes	Yes	Yes	Yes

"No" means the property is not required, not that it must fail. Every group is a monoid and every monoid is a semigroup.

Common examples

Set and operation	Closed and associative	Identity	Every element invertible	Verdict
${1, 2, 3, \dots}$ under $+$	Yes	None	No	Semigroup
Even integers under $\times$	Yes	None	No	Semigroup
${0, 1, 2, \dots}$ under $+$	Yes	0	No	Monoid
$Z$ under $+$	Yes	0	Yes	Abelian group
$Z$ under $\times$	Yes	1	No (only $\pm 1$ )	Monoid
$Z_{n}$ under $\times$ mod $n$ , $n \geq 2$	Yes	1	No ( $0$ has none)	Monoid
Nonzero rationals under $\times$	Yes	1	Yes	Abelian group
$2 \times 2$ real matrices under $\times$	Yes	$I$	No (singular ones)	Monoid, not commutative
Invertible $2 \times 2$ real matrices under $\times$	Yes	$I$	Yes	Group, not abelian
Strings over an alphabet of two or more symbols under concatenation	Yes	empty string	No	Monoid, not commutative (with one symbol it is commutative)

INVERSE OF A PRODUCT

(a * b)^{- 1} = b^{- 1} * a^{- 1}

Holds in every group; note the reversed order. If the group is abelian the order does not matter. Also $(a^{- 1})^{- 1} = a$ .

Cancellation holds in a group: $a * b = a * c \Rightarrow b = c$ , and $b * a = c * a \Rightarrow b = c$ . It can fail in a monoid: in $Z$ under $\times$ , $0 \cdot 2 = 0 \cdot 3$ but $2 \neq = 3$ . In a group the equations $a * x = b$ and $y * a = b$ have the unique solutions $x = a^{- 1} * b$ and $y = b * a^{- 1}$ , so every row and every column of a finite group's table contains each element exactly once. The identity is the only element with $a * a = a$ (cancel one $a$ ). A group in which $a * a = e$ for every $a$ is abelian: $a * b = (a * b)^{- 1} = b^{- 1} * a^{- 1} = b * a$ .

Subgroups and Lagrange's theorem

A non-empty subset $H$ of a group $G$ is a subgroup if $H$ is itself a group under the operation of $G$ . Every group has the trivial subgroup ${e}$ and the whole group $G$ as subgroups; a subgroup other than $G$ is called proper. The order of a group is $∣ G ∣$ , the number of its elements.

Subgroup tests for a non-empty subset H

Two-step test: $a, b \in H \Rightarrow a * b \in H$ and $a^{- 1} \in H$ .
One-step test: $a, b \in H \Rightarrow a * b^{- 1} \in H$ (write $a - b$ in additive groups).
If $H$ is finite (in particular if $G$ is finite), closure alone is enough: $a, b \in H \Rightarrow a * b \in H$ .

LAGRANGE'S THEOREM

∣ H ∣ divides ∣ G ∣, ∣ G ∣ = [G : H] \cdot ∣ H ∣

For a finite group $G$ and any subgroup $H$ ; $[G : H]$ is the number of distinct left cosets of $H$ in $G$ .

A left coset of $H$ is $a H = {a * h : h \in H}$ . All cosets have exactly $∣ H ∣$ elements, and two cosets are equal or disjoint, so they split $G$ into $[G : H]$ equal blocks. That is the whole idea behind Lagrange's theorem. Right cosets $H a$ split $G$ the same way and also number $[G : H]$ .

EXAM TIP

The converse of Lagrange's theorem is false: a group of order $12$ need not have a subgroup of order $6$ (the group $A_{4}$ has none). Lagrange can only rule orders out. Partial converses that do hold: if a prime $p$ divides $∣ G ∣$ , then $G$ has an element of order $p$ , and so a subgroup of order $p$ (Cauchy's theorem); and a finite cyclic group, or more generally a finite abelian group, has a subgroup of every order dividing $∣ G ∣$ .

SIZE OF A PRODUCT SET

∣ H K ∣ = \frac{∣ H ∣ ∣ K ∣}{∣ H \cap K ∣}

For subgroups $H, K$ of a finite group, where $H K = {hk : h \in H, k \in K}$ . $H K$ is a subgroup if and only if $H K = K H$ (always true in an abelian group).

The intersection of two subgroups is always a subgroup. The union of two subgroups is a subgroup only when one of them contains the other; in particular, no group is the union of two proper subgroups.

Order of an element and cyclic groups

The order of an element $a$ , written $o (a)$ , is the smallest positive integer $m$ with $a^{m} = e$ (in additive notation, $ma = 0$ ). If no such $m$ exists, the order is infinite. The set $⟨ a ⟩ = {a^{k} : k \in Z}$ is a subgroup with exactly $o (a)$ elements (infinitely many if $o (a)$ is infinite). A group is cyclic if $G = ⟨ a ⟩$ for some $a$ , called a generator.

ORDER OF AN ELEMENT DIVIDES THE GROUP ORDER

o (a) divides ∣ G ∣, a^{∣ G ∣} = e

In every finite group, by Lagrange applied to $⟨ a ⟩$ . Also $a^{k} = e ⟺ o (a) ∣ k$ .

ORDER OF A POWER

o (a^{k}) = \frac{n}{g cd ( n , k )} when o (a) = n

Holds in any group. In $Z_{n}$ the element $k$ has order $n / g cd (n, k)$ . If $G = ⟨ a ⟩$ has order $n$ , the element $a^{k}$ generates $G$ exactly when $g cd (n, k) = 1$ .

More facts about element orders

$o (a) = o (a^{- 1})$ and $o (ab) = o (ba)$ for all $a, b$ .
In a finite group, elements with $a \neq = a^{- 1}$ pair off as ${a, a^{- 1}}$ . So a group of even order has an odd number of elements of order $2$ , and at least one.

NUMBER OF GENERATORS OF A CYCLIC GROUP

# {generators} = ϕ (n)

For a cyclic group of order $n$ , where $ϕ (n)$ is Euler's totient (the count of $k$ with $1 \leq k \leq n$ and $g cd (k, n) = 1$ ).

EULER'S TOTIENT

ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p})

The product runs over the distinct primes $p$ dividing $n$ . For a prime $p$ , $ϕ (p) = p - 1$ and $ϕ (p^{k}) = p^{k} - p^{k - 1}$ .

SUBGROUPS OF A CYCLIC GROUP

one subgroup of each order d ∣ n, containing ϕ (d) generators

A cyclic group of order $n$ has exactly one subgroup for each positive divisor $d$ of $n$ , so the number of subgroups equals the number of divisors of $n$ . Every subgroup of a cyclic group is cyclic, and the group has exactly $ϕ (d)$ elements of order $d$ for each $d ∣ n$ .

The infinite cyclic group. $(Z, +)$ is cyclic and infinite. It has only two generators, $1$ and $- 1$ , and its subgroups are $n Z = {nk : k \in Z}$ for $n = 0, 1, 2, \dots$ , all of them cyclic.

ORDER IN A DIRECT PRODUCT

o ((a, b)) = lcm (o (a), o (b))

In $G \times H$ with finite $o (a)$ and $o (b)$ . Consequently $Z_{m} \times Z_{n}$ is cyclic if and only if $g cd (m, n) = 1$ .

EXAM TIP

To count elements of a given order in a cyclic group of order $n$ : first check that the order $d$ divides $n$ (if not, the answer is $0$ ), then the answer is $ϕ (d)$ . The identity is the only element of order $1$ . Check: $\sum_{d ∣ n} ϕ (d) = n$ , since every element has exactly one order.

Standard groups and small groups

Integers modulo $n$ under addition. $(Z_{n}, +_{n})$ is a cyclic abelian group of order $n$ generated by $1$ . Units modulo $n$ under multiplication ( $n \geq 2$ ). $U (n) = {k : 1 \leq k < n, g cd (k, n) = 1}$ under multiplication modulo $n$ is an abelian group with $ϕ (n)$ elements. It is not always cyclic: in $U (8) = {1, 3, 5, 7}$ , $3^{2} = 9 \equiv 1$ , $5^{2} = 25 \equiv 1$ and $7^{2} = 49 \equiv 1$ , so every element has order at most $2$ . $U (n)$ is cyclic exactly for $n = 2, 4, p^{k}, 2 p^{k}$ with $p$ an odd prime and $k \geq 1$ . For $n \geq 2$ , $Z_{n}$ without $0$ under multiplication modulo $n$ is a group exactly when $n$ is prime.

Isomorphism. Two groups $(G, *)$ and $(H, \circ)$ are isomorphic, written $G ≅ H$ , if some bijection $f : G \to H$ satisfies $f (a * b) = f (a) \circ f (b)$ for all $a, b$ ; they are the same group with the elements renamed. A map with this property that need not be a bijection is a homomorphism; it sends the identity of $G$ to the identity of $H$ and $a^{- 1}$ to $f (a)^{- 1}$ . An isomorphism preserves the order of every element. Every cyclic group of order $n$ is isomorphic to $Z_{n}$ , and every infinite cyclic group to $Z$ .

Groups of small order

Order	Groups up to isomorphism	Notes
1	trivial group	only $e$
2, 3, 5, 7 (prime)	$Z_{p}$ only	every group of prime order is cyclic
4	$Z_{4}$ and $Z_{2} \times Z_{2}$	both abelian; the second has no element of order 4
6	$Z_{6}$ and $S_{3}$	$S_{3}$ (permutations of three objects) is not abelian; it is the smallest non-abelian group
8	$Z_{8}$ , $Z_{4} \times Z_{2}$ , $Z_{2} \times Z_{2} \times Z_{2}$ , and two non-abelian groups (the symmetries of a square and the quaternion group)	five groups, three of them abelian

From the table: every group of order at most $5$ is abelian, and a non-abelian group has order at least $6$ .

GROUPS OF PRIME ORDER

∣ G ∣ = p prime \Rightarrow G ≅ Z_{p}

Any non-identity element has order dividing $p$ , so order $p$ , hence generates $G$ . Every non-identity element is a generator, giving $p - 1$ generators.

CYCLIC IMPLIES ABELIAN

G cyclic \Rightarrow G abelian

Since $a^{i} a^{j} = a^{i + j} = a^{j} a^{i}$ . The converse is false: $Z_{2} \times Z_{2}$ is abelian and not cyclic.

WORKED EXAMPLE

On $Z$ define $a * b = a + b - 3$ . Show that $(Z, *)$ is an abelian group, and find its identity and the inverse of $10$ .

Solution

Closure: $a + b - 3$ is an integer.
Associativity: $(a * b) * c = a + b + c - 6 = a * (b * c)$ .
Identity: solve $a * e = a$ , so $a + e - 3 = a$ and $e = 3$ , which is independent of $a$ ; also $3 * a = 3 + a - 3 = a$ .
Inverse: solve $a * x = 3$ , so $a + x - 3 = 3$ and $x = 6 - a$ , which is an integer; $*$ is commutative, so $x * a = 3$ as well.
Commutativity: $a + b - 3 = b + a - 3$ . So it is an abelian group. For $a = 10$ the inverse is $6 - 10 = - 4$ ; check: $10 + (- 4) - 3 = 3$ .

Answer: Identity $3$ ; the inverse of $10$ is $- 4$ .

WORKED EXAMPLE

Let $G$ be a cyclic group of order $24$ with generator $a$ . Find the number of elements of order $8$ , the order of $a^{18}$ , and the number of subgroups of $G$ .

Solution

Elements of order $8$ : $8$ divides $24$ , so there are $ϕ (8) = 8 - 4 = 4$ of them.
Order of $a^{18}$ : $24/ g cd (24, 18) = 24/6 = 4$ .
Subgroups: one for each divisor of $24$ , namely $1, 2, 3, 4, 6, 8, 12, 24$ , which is $8$ divisors.

Answer: 4 elements of order 8; $o (a^{18}) = 4$ ; 8 subgroups.

EXAM TIP

Quick check that a group is not cyclic: find two different elements of order $2$ (a cyclic group has at most one), or a non-commuting pair. Quick check that an element order is impossible: it must divide $∣ G ∣$ . In $U (n)$ the order of the group is $ϕ (n)$ , not $n - 1$ unless $n$ is prime.

PREVIOUS-YEAR QUESTIONS

7 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2025 Set 1 · GATE CSE 2024 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2020 · GATE CSE 2018

GATE 2025 CS1 Q.49

GATE 2025 · CS1Q.49 · 2 marks · MSQ

$A = {0, 1, 2, 3, \dots}$ is the set of non-negative integers. Let $F$ be the set of functions from $A$ to itself. For any two functions $f_{1}, f_{2} \in F$ , we define

(f_{1} ⊙ f_{2}) (n) = f_{1} (n) + f_{2} (n)

for every number $n$ in $A$ . Which of the following is/are CORRECT about the mathematical structure $(F, ⊙)$ ?

(A)
$(F, ⊙)$ is an Abelian group.
(B)
$(F, ⊙)$ is an Abelian monoid.
(C)
$(F, ⊙)$ is a non-Abelian group.
(D)
$(F, ⊙)$ is a non-Abelian monoid.

Answer and solution

GATE 2025 CS1 Q.49: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.49: answer and solution

GATE 2024 CS1 Q.52

GATE 2024 · CS1Q.52 · 2 marks · MSQ

Consider the operators ◊ and □ defined by $a ◊ b = a + 2 b$ , $a □ b = ab$ , for positive integers. Which of the following statements is/are TRUE?

(A)
Operator ◊ obeys the associative law
(B)
Operator □ obeys the associative law
(C)
Operator ◊ over the operator □ obeys the distributive law
(D)
Operator □ over the operator ◊ obeys the distributive law

Answer and solution

GATE 2024 CS1 Q.52: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.52: answer and solution

GATE 2024 CS2 Q.63

GATE 2024 · CS2Q.63 · 2 marks · NAT

Let $Z_{n}$ be the group of integers ${0, 1, 2, \dots, n - 1}$ with addition modulo $n$ as the group operation. The number of elements in the group $Z_{2} \times Z_{3} \times Z_{4}$ that are their own inverses is

Answer and solution

GATE 2024 CS2 Q.63: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.63: answer and solution

GATE 2023 CS Q.51

GATE 2023 · CSQ.51 · 2 marks · MSQ

Let $X$ be a set and $2^{X}$ denote the powerset of $X$ . Define a binary operation $Δ$ on $2^{X}$ as follows:

A Δ B = (A - B) \cup (B - A) .

Let $H = (2^{X}, Δ)$ . Which of the following statements about $H$ is/are correct?

(A)
$H$ is a group.
(B)
Every element in $H$ has an inverse, but $H$ is NOT a group.
(C)
For every $A \in 2^{X}$ , the inverse of $A$ is the complement of $A$ .
(D)
For every $A \in 2^{X}$ , the inverse of $A$ is $A$ .

Answer and solution

GATE 2023 CS Q.51: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.51: answer and solution

GATE 2022 CS Q.27

GATE 2022 · CSQ.27 · 1 mark · MSQ

Which of the following statements is/are TRUE for a group $G$ ?

(A)
If for all $x, y \in G$ , $(x y)^{2} = x^{2} y^{2}$ , then $G$ is commutative.
(B)
If for all $x \in G$ , $x^{2} = 1$ , then $G$ is commutative. Here, $1$ is the identity element of $G$ .
(C)
If the order of $G$ is $2$ , then $G$ is commutative.
(D)
If $G$ is commutative, then a subgroup of $G$ need not be commutative.

Answer and solution

GATE 2022 CS Q.27: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.27: answer and solution

GATE 2020 CS Q.18

GATE 2020 · CSQ.18 · 1 mark · NAT

Let $G$ be a group of 35 elements. Then the largest possible size of a subgroup of $G$ other than $G$ itself is ______.

Answer and solution

GATE 2020 CS Q.18: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.18: answer and solution

GATE 2018 CS Q.19

GATE 2018 · CSQ.19 · 1 mark · NAT

Let $G$ be a finite group on 84 elements. The size of a largest possible proper subgroup of $G$ is ______.

Answer and solution

GATE 2018 CS Q.19: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.19: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 11 mark · MCQ

Which of the following is a group under the stated operation?

(A)
${1, 2, 3, \dots}$ under addition
(B)
$Z$ under multiplication
(C)
${1, 2, 3, 4, 5}$ under multiplication modulo $6$
(D)
The nonzero rational numbers under multiplication

Answer and solution

Answer: (D)

A has no identity ( $0$ is not in the set).
B has an identity $1$ but $2$ has no integer inverse.
C is not closed: $2 \times 3 = 6 \equiv 0$ , which is not in the set.
D is closed, associative, has identity $1$ , and $1/ q$ is the inverse of $q$ . So D.

PRACTICE 21 mark · NAT

How many generators does a cyclic group of order $36$ have?

Answer and solution

Answer: $12$

The number of generators is $ϕ (36)$ .
$36 = 2^{2} \cdot 3^{2}$ , so $ϕ (36) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$ .

PRACTICE 32 marks · NAT

The set $U (20) = {1, 3, 7, 9, 11, 13, 17, 19}$ is a group under multiplication modulo $20$ . How many elements of order $2$ does it have?

Answer and solution

Answer: $3$

An element has order $2$ exactly when $x \neq = 1$ and $x^{2} \equiv 1 (mod 20)$ .
$9^{2} = 81 \equiv 1$ , $1 1^{2} = 121 \equiv 1$ , $1 9^{2} = 361 \equiv 1$ .
$3^{2} \equiv 9$ , $7^{2} = 49 \equiv 9$ , $1 3^{2} = 169 \equiv 9$ , $1 7^{2} = 289 \equiv 9$ , none equal to $1$ .
So there are $3$ elements: $9, 11, 19$ .

PRACTICE 42 marks · MCQ

In the group $(Z_{30}, +_{30})$ let $H$ be the smallest subgroup containing both $12$ and $18$ . How many elements does $H$ have?

(A)
3
(B)
5
(C)
6
(D)
10

Answer and solution

Answer: (B)

$H$ contains $18 - 12 = 6$ , so $H \supseteq ⟨ 6 ⟩$ ; and $12$ and $18$ are multiples of $6$ , so $⟨ 6 ⟩$ already contains both. Hence $H = ⟨ 6 ⟩$ .
$H = {0, 6, 12, 18, 24}$ .
Its order is $30/ g cd (30, 6) = 5$ . So B.

PRACTICE 51 mark · NAT

How many commutative binary operations can be defined on the set ${a, b}$ ?

Answer and solution

Answer: $8$

A binary operation on ${a, b}$ is a $2 \times 2$ table with entries $a * a$ , $a * b$ , $b * a$ , $b * b$ , each $a$ or $b$ .
Commutativity forces $b * a = a * b$ , so the operation is fixed by the $3$ entries $a * a$ , $a * b$ , $b * b$ .
Each has $2$ choices: $2^{3} = 8$ , which matches $n^{n (n + 1) /2}$ with $n = 2$ .

PRACTICE 62 marks · MSQ

For which of the following numbers $m$ is it true that NO group of order $12$ has a subgroup of order $m$ ?

(A)
$5$
(B)
$6$
(C)
$4$
(D)
$8$

Answer and solution

Answer: (A), (D)

By Lagrange's theorem the order of a subgroup must divide $12$ .
$5$ and $8$ do not divide $12$ , so no group of order $12$ has a subgroup of either order.
The cyclic group $Z_{12}$ has the subgroups $⟨ 2 ⟩$ of order $6$ and $⟨ 3 ⟩$ of order $4$ , so $6$ and $4$ do occur (even though $A_{4}$ has no subgroup of order $6$ ). So A and D.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Monoids, Groups

Preparing in Kolkata? IAE Academy's course for GATE CSE.