Semigroups, Monoids and Groups

An algebraic structure is a set with one or more operations. The structures GATE asks about are defined by which axioms a single binary operation ∗ satisfies.

The axioms

(ℤ, −) is not a semigroup, since subtraction is not associative. (ℕ, +) has no inverses, so it is a monoid but not a group. Invertible matrices under multiplication form a group that is not abelian.

Basic facts in any group: the identity is unique, each element's inverse is unique, (ab)⁻¹ = b⁻¹a⁻¹, and the cancellation laws hold (ab = ac ⇒ b = c). In the Cayley table (operation table) of a finite group, every element appears exactly once in each row and each column.

Checking the axioms by brute force over a small set:

def check(name, S, op):
    S = list(S)
    closed = all(op(a, b) in S for a in S for b in S)
    assoc = all(op(op(a, b), c) == op(a, op(b, c)) for a in S for b in S for c in S)
    ids = [e for e in S if all(op(e, a) == a == op(a, e) for a in S)]
    inverses = bool(ids) and all(any(op(a, b) == ids[0] for b in S) for a in S)
    group = closed and assoc and bool(ids) and inverses
    print(f"{name:26} closed {closed!s:5} assoc {assoc!s:5} identity {bool(ids)!s:5} inverses {inverses!s:5} group {group}")

check("{0..5} under + mod 6", range(6), lambda a, b: (a + b) % 6)
check("{1..4} under x mod 5", range(1, 5), lambda a, b: a * b % 5)
check("{0..5} under x mod 6", range(6), lambda a, b: a * b % 6)
check("{1..5} under x mod 6", range(1, 6), lambda a, b: a * b % 6)

{0..5} under + mod 6       closed True  assoc True  identity True  inverses True  group True
{1..4} under x mod 5       closed True  assoc True  identity True  inverses True  group True
{0..5} under x mod 6       closed True  assoc True  identity True  inverses False group False
{1..5} under x mod 6       closed False assoc True  identity True  inverses False group False

Multiplication mod 5 on {1, 2, 3, 4} is a group because 5 is prime; mod 6, the elements 2, 3 and 4 have no inverses (and 2 × 3 = 0 is not even in {1, …, 5}).

Order of an element and subgroups

The order of a group is its number of elements. The order of an element a is the smallest k ≥ 1 with aᵏ = e (in additive notation, k·a = 0).

A subgroup is a subset that is itself a group under the same operation. For a finite non-empty subset H, being closed under the operation is enough.

So a group of prime order p has no subgroups other than {e} and itself, and every non-identity element generates the whole group: every group of prime order is cyclic (and abelian).

Cyclic groups

A group is cyclic if some element g (a generator) produces every element as a power gᵏ. (ℤₙ, +) is cyclic with generator 1.

In ℤₙ:

• The order of a is n / gcd(a, n). In ℤ₁₂, the element 8 has order 12 / 4 = 3 (8, 16 ≡ 4, 24 ≡ 0).
• a is a generator exactly when gcd(a, n) = 1, so ℤₙ has φ(n) generators (Euler's totient). ℤ₁₂ has the 4 generators 1, 5, 7, 11.
• For each divisor d of n there is exactly one subgroup of order d. So ℤₙ has as many subgroups as n has divisors.

Every cyclic group is abelian, and every subgroup of a cyclic group is cyclic. The Klein four-group (for example {1, 3, 5, 7} under multiplication mod 8) has order 4 but no element of order 4, so it is the smallest non-cyclic group.

The multiplicative group U(n) = {a : 1 ≤ a < n, gcd(a, n) = 1} under multiplication mod n has φ(n) elements. U(p) is cyclic for every prime p; its generators are called primitive roots (3 is a primitive root mod 7: its powers are 3, 2, 6, 4, 5, 1).

Practice questions