Adding integers, multiplying non-zero fractions, rotating a square, shuffling a deck of cards, composing two functions: very different activities, yet they obey the same handful of rules. You can combine any two things and get another thing of the same kind, brackets do not matter, there is a "do nothing" element, and every action can be undone. Group theory studies exactly the consequences of these rules, once, so that the results apply to every example at the same time.
Groups are the language of symmetry in physics and chemistry, and in computer science they sit underneath modular arithmetic, RSA and elliptic-curve cryptography, error-correcting codes, and the analysis of puzzles like the Rubik's cube. In this chapter we build up from binary operations through semigroups and monoids to groups, then study element orders, cyclic groups, subgroups, Lagrange's theorem and homomorphisms. We use modular arithmetic and the gcd freely, and the ideas of bijection from Functions and partitions from Equivalence Relations & Partitions. The next chapter, Rings & Fields, adds a second operation.
A group (G, ∗) is a set G with a binary operation ∗ such that: (1) closure: a ∗ b ∈ G for all a, b ∈ G; (2) associativity: (a ∗ b) ∗ c = a ∗ (b ∗ c); (3) identity: there is e ∈ G with e ∗ a = a ∗ e = a for all a; (4) inverses: for every a there is a−1 ∈ G with a ∗ a−1 = a−1 ∗ a = e. If also a ∗ b = b ∗ a for all a, b, the group is abelian (commutative).
Every table, order and subgroup claim in this chapter was checked by brute force over the elements.
From Binary Operations to Groups
A binary operation on a set S is a function ∗ : S × S → S. The "→ S" part already contains closure: the answer must land back in S. Subtraction is a binary operation on ℤ but not on ℕ (2 − 5 ∉ ℕ).
Adding the axioms one at a time gives a ladder of structures:
Structure | Closure | Associative | Identity | Inverses | Commutative |
|---|---|---|---|---|---|
Algebraic system (magma / groupoid) | ✓ | ||||
Semigroup | ✓ | ✓ | |||
Monoid | ✓ | ✓ | ✓ | ||
Group | ✓ | ✓ | ✓ | ✓ | |
Abelian group | ✓ | ✓ | ✓ | ✓ | ✓ |
Examples to classify
Set and operation | Strongest structure | Reason |
|---|---|---|
(ℤ, −) | Magma only | (5 − 3) − 1 = 1 but 5 − (3 − 1) = 3: not associative |
(ℕ+ = {1, 2, …}, +) | Semigroup | No identity (0 is missing) |
(ℕ = {0, 1, 2, …}, +) | Monoid | Identity 0, but 3 has no inverse in ℕ |
Strings over an alphabet, concatenation | Monoid | Identity is the empty string ε; no string can "cancel" another |
(ℤ, ×) | Commutative monoid | Identity 1, but 2 has no integer inverse |
(ℤ, +), (ℚ, +), (ℝ, +) | Abelian group | Identity 0, inverse −a |
(ℚ − {0}, ×), (ℝ − {0}, ×) | Abelian group | Identity 1, inverse 1/a |
(ℤn, +n), addition mod n | Abelian group | Identity 0, inverse of a is n − a (and 0 for 0) |
Invertible n × n real matrices, × | Non-abelian group (n ≥ 2) | Matrix product is associative but not commutative |
Bijections of {1, …, n}, composition (Sn) | Group, non-abelian for n ≥ 3 | Identity map; inverse function |
Worked example: a custom operation
On ℤ, define a ∗ b = a + b − 1. Is (ℤ, ∗) a group?
Closure: a + b − 1 is an integer. ✓
Associativity: (a ∗ b) ∗ c = (a + b − 1) + c − 1 = a + b + c − 2, and a ∗ (b ∗ c) = a + (b + c − 1) − 1 = a + b + c − 2. ✓
Identity: we need a + e − 1 = a, so e = 1. Check: a ∗ 1 = a. ✓
Inverse: we need a + b − 1 = 1, so b = 2 − a, an integer. ✓
Commutative: a + b − 1 = b + a − 1. ✓
So (ℤ, ∗) is an abelian group with identity 1, and the inverse of 5 is −3 (check: 5 + (−3) − 1 = 1). The identity of a group does not have to be 0 or 1 of ordinary arithmetic: always solve for it.
A GATE favourite in the same spirit: on ℝ − {−1}, a ∗ b = a + b + ab is an abelian group with identity 0 and inverse a−1 = −a/(1 + a). (It is ordinary multiplication in disguise: 1 + (a ∗ b) = (1 + a)(1 + b).)
How many binary operations are there?
A binary operation on an n-element set is a function from the n2 ordered pairs to n possible answers, so there are nn² of them (16 for n = 2). A commutative one is fixed by its values on the n(n + 1)/2 unordered pairs (including pairs {a, a}), giving nn(n+1)/2 (8 for n = 2).
First Properties of Groups
Each of these follows from the axioms alone, so it holds in every group.
The identity is unique. If e and e′ are both identities, then e = e ∗ e′ = e′.
Inverses are unique. If b and c are both inverses of a, then b = b ∗ e = b ∗ (a ∗ c) = (b ∗ a) ∗ c = e ∗ c = c. (Associativity does the work.)
Cancellation laws. If a ∗ b = a ∗ c then b = c (multiply on the left by a−1); similarly on the right.
Socks-and-shoes rule. (a ∗ b)−1 = b−1 ∗ a−1, because (a ∗ b) ∗ (b−1 ∗ a−1) = a ∗ e ∗ a−1 = e. You take off your shoes before your socks.
(a−1)−1 = a.
Equations are solvable: a ∗ x = b has the unique solution x = a−1 ∗ b.
Cancellation has a neat consequence for the Cayley table (the operation table) of a finite group: every element appears exactly once in each row and each column, like a Sudoku (a Latin square). A table with a repeated entry in a row cannot be a group.
Notation: in a general group we usually write ab for a ∗ b and ak for a ∗ a ∗ … ∗ a (k times), with a0 = e and a−k = (a−1)k. In additive groups like ℤn, the same thing is written ka.
Two Small Groups
A non-abelian group: S3
S3 is the set of all 6 permutations of {1, 2, 3} under composition (equivalently, the symmetries of an equilateral triangle). We write f ∘ g for "first g, then f". Take the transpositions (1 2), which swaps 1 and 2, and (1 3):
(1 2) ∘ (1 3): 1 → 3 → 3, 2 → 2 → 1, 3 → 1 → 2 result: 1→3, 2→1, 3→2 = (1 3 2)
(1 3) ∘ (1 2): 1 → 2 → 2, 2 → 1 → 3, 3 → 3 → 1 result: 1→2, 2→3, 3→1 = (1 2 3)
The results differ, so S3 is not abelian. It is the smallest non-abelian group: every group of order 1, 2, 3, 4 or 5 is abelian.
Two groups of order 4
Compare (ℤ4, +4) with U(8) = {1, 3, 5, 7} under multiplication mod 8:
+4 | 0 1 2 3 ×8 | 1 3 5 7
---+--------- ---+---------
0 | 0 1 2 3 1 | 1 3 5 7
1 | 1 2 3 0 3 | 3 1 7 5
2 | 2 3 0 1 5 | 5 7 1 3
3 | 3 0 1 2 7 | 7 5 3 1
Both are abelian groups of order 4 and both tables are Latin squares. But in U(8), every element squared is 1 (the diagonal is all 1s), while in ℤ4, 1 + 1 = 2 ≠ 0. So they are genuinely different groups. U(8) is the Klein four-group V4. Up to isomorphism, ℤ4 and V4 are the only groups of order 4.
Order of an Element and Cyclic Groups
The order of a group, |G|, is its number of elements. The order of an element a, written o(a), is the smallest positive integer k with ak = e (infinite if there is none).
In ℤ12: o(4) = 3 because 4 + 4 + 4 = 12 ≡ 0, o(9) = 4 (9, 6, 3, 0), and o(5) = 12. In general, in ℤn the element k has order n / gcd(n, k). So o(8) = 12/4 = 3 and o(10) = 12/2 = 6.
A group G is cyclic if G = ⟨g⟩ = {gk : k ∈ ℤ} for some g ∈ G. Such a g is a generator. A finite group G is cyclic exactly when some element has order |G|.
ℤ is cyclic, generated by 1 (or −1). ℤn is cyclic, generated by 1.
The generators of ℤn are exactly the k with gcd(k, n) = 1, so a cyclic group of order n has φ(n) generators (Euler's totient). ℤ12 has φ(12) = 4: namely 1, 5, 7, 11.
U(10) = {1, 3, 7, 9} is cyclic: 31 = 3, 32 = 9, 33 = 27 ≡ 7, 34 = 81 ≡ 1. U(8) is not cyclic, since all its non-identity elements have order 2.
Every cyclic group is abelian: gigj = gi+j = gjgi. The converse is false (V4).
Every cyclic group of order n is isomorphic to ℤn, and every infinite cyclic group is isomorphic to ℤ.
In a cyclic group of order n, for each divisor d of n there are exactly φ(d) elements of order d. In ℤ12: orders 1, 2, 3, 4, 6, 12 occur 1, 1, 2, 2, 2, 4 times (total 12). ✓
Subgroups
A subset H of a group G is a subgroup (H ≤ G) if H is itself a group under the same operation.
We do not have to recheck associativity (it is inherited from G). The practical tests:
One-step test: H ≤ G if and only if H is non-empty and a, b ∈ H ⇒ ab−1 ∈ H.
Finite test: if H is finite, H ≤ G if and only if H is non-empty and closed under the operation. (The powers of a ∈ H must eventually repeat, so ak = e for some k ≥ 1, and then a−1 = ak−1 ∈ H.)
Examples: the even integers 2ℤ ≤ ℤ; {0, 4, 8} ≤ ℤ12; the rotations {identity, (1 2 3), (1 3 2)} ≤ S3. Every group has the two trivial subgroups {e} and G. The positive integers are not a subgroup of (ℤ, +): no inverses. The odd integers are not either: 1 + 1 = 2 is not odd.
For any a ∈ G, the set ⟨a⟩ = {ak} is a subgroup, the cyclic subgroup generated by a, and |⟨a⟩| = o(a).
Subgroups of cyclic groups are cyclic. Moreover, a cyclic group of order n has exactly one subgroup of each order d dividing n, and no others. ℤ12 therefore has exactly 6 subgroups, of orders 1, 2, 3, 4, 6, 12 (generated by 0, 6, 4, 3, 2, 1).
Cosets and Lagrange's Theorem
For H ≤ G and a ∈ G, the left coset of H by a is aH = {ah : h ∈ H}.
Example: H = {0, 4, 8} in ℤ12 (written additively, a + H). The cosets are {0, 4, 8}, {1, 5, 9}, {2, 6, 10} and {3, 7, 11}. They split ℤ12 into 4 disjoint blocks of 3 elements each: 12 = 4 × 3.
That picture is always true, and it gives the most important theorem about finite groups.
Lagrange's theorem. If G is a finite group and H ≤ G, then |H| divides |G|. The number of distinct cosets, |G| / |H|, is called the index [G : H].
Proof.
Every coset has |H| elements. The map h ↦ ah from H to aH is onto by definition, and one-to-one by cancellation (ah1 = ah2 ⇒ h1 = h2). So it is a bijection and |aH| = |H|.
Two cosets are equal or disjoint. Suppose x ∈ aH ∩ bH, say x = ah1 = bh2. Then a = bh2h1−1, so for any h ∈ H, ah = b(h2h1−1h) ∈ bH. Thus aH ⊆ bH, and by symmetry bH ⊆ aH.
The cosets cover G, since a = ae ∈ aH.
So the cosets form a partition of G (they are the classes of the equivalence relation a ~ b ⇔ a−1b ∈ H) into blocks of equal size |H|. If there are k blocks, |G| = k·|H|. ∎
Corollaries
o(a) divides |G| for every a ∈ G, because o(a) = |⟨a⟩|.
a|G| = e for every a ∈ G.
Every group of prime order p is cyclic (and so abelian): any a ≠ e has order dividing p and greater than 1, so o(a) = p and ⟨a⟩ = G.
Fermat's little theorem: if p is prime and p ∤ a, then ap−1 ≡ 1 (mod p). Apply a|G| = e in the group {1, …, p − 1} under multiplication mod p, which has order p − 1. Example: 36 = 729 = 7·104 + 1 ≡ 1 (mod 7).
Euler's theorem: if gcd(a, n) = 1 then aφ(n) ≡ 1 (mod n), using the group U(n) of order φ(n). This is the identity that makes RSA decryption work.
The converse of Lagrange is false. The alternating group A4 (the 12 even permutations of 4 objects) has order 12, and 6 divides 12, yet A4 has no subgroup of order 6. (For cyclic groups the converse does hold, as we saw.)
Homomorphisms and Isomorphisms
A homomorphism from (G, ∗) to (H, ·) is a function f : G → H with f(a ∗ b) = f(a) · f(b) for all a, b. A bijective homomorphism is an isomorphism, and then G ≅ H: the two groups are the same up to renaming.
f(n) = n mod m from (ℤ, +) to (ℤm, +m) is a homomorphism (onto, not one-to-one).
exp : (ℝ, +) → (ℝ+, ×), x ↦ ex, is an isomorphism, since ex+y = exey. Its inverse is ln. This is why logarithm tables turned multiplication into addition.
The determinant from invertible matrices (×) to ℝ − {0} (×) is a homomorphism: det(AB) = det(A)det(B).
Every homomorphism sends the identity to the identity and inverses to inverses. Its kernel ker f = {a : f(a) = eH} is a subgroup of G, and f is one-to-one exactly when ker f = {e}. The kernel is in fact a normal subgroup of G (a subgroup N with aN = Na for every a ∈ G), which is the starting point of quotient groups in an abstract algebra course.
Isomorphic groups share every structural property: order, being abelian or cyclic, the number of elements of each order. To prove two groups are not isomorphic, find a property that differs. ℤ4 ≇ V4 because ℤ4 has an element of order 4 and V4 does not.
The number of non-isomorphic groups of order n = 1, 2, …, 8 is 1, 1, 1, 2, 1, 2, 1, 5. Order 6: ℤ6 and S3. Order 8: three abelian ones (ℤ8, ℤ4 × ℤ2, ℤ2 × ℤ2 × ℤ2) and two non-abelian ones (the dihedral group of the square and the quaternion group).
Checking with Code
A brute-force group checker, element orders, generators and subgroups of ℤ12, and a search confirming that A4 has no subgroup of order 6.
from math import gcd
from itertools import product, permutations, combinations
def is_group(elements, op):
"""Brute-force check of closure, associativity, identity and inverses."""
S = list(elements)
if any(op(a, b) not in S for a, b in product(S, S)):
return False, "not closed"
if any(op(op(a, b), c) != op(a, op(b, c)) for a, b, c in product(S, S, S)):
return False, "not associative"
ids = [e for e in S if all(op(e, a) == a == op(a, e) for a in S)]
if not ids:
return False, "no identity"
e = ids[0]
for a in S:
if not any(op(a, b) == e == op(b, a) for b in S):
return False, f"{a} has no inverse"
return True, f"group, identity {e}"
def order(a, op, e):
k, x = 1, a
while x != e:
x, k = op(x, a), k + 1
return k
for n in (6, 7):
nonzero = range(1, n)
print(f"Z_{n} without 0, multiplication mod {n}:", is_group(nonzero, lambda a, b: a * b % n))
for n in (8, 10):
U = [a for a in range(1, n) if gcd(a, n) == 1]
mul = lambda a, b, n=n: a * b % n
orders = {a: order(a, mul, 1) for a in U}
print(f"U({n}) = {U} {is_group(U, mul)[1]} orders {orders}",
"cyclic" if len(U) in orders.values() else "NOT cyclic")
n = 12
add = lambda a, b: (a + b) % n
print("Orders in Z_12:", {a: order(a, add, 0) for a in range(n)})
print("Generators of Z_12:", [a for a in range(n) if order(a, add, 0) == n])
# Subgroups of Z_12 are generated by single elements (Z_12 is cyclic)
subgroups = {frozenset((k * a) % n for k in range(n)) for a in range(n)}
print("Subgroup orders of Z_12:", sorted(len(H) for H in subgroups))
# A4 = even permutations of {0,1,2,3}: does it have a subgroup of order 6?
def compose(p, q): # (p o q)(i) = p(q(i))
return tuple(p[q[i]] for i in range(len(q)))
def is_even(p):
inversions = sum(1 for i in range(4) for j in range(i + 1, 4) if p[i] > p[j])
return inversions % 2 == 0
A4 = [p for p in permutations(range(4)) if is_even(p)]
print("|A4| =", len(A4), "| group check:", is_group(A4, compose)[0])
def closed(H):
return all(compose(a, b) in H for a in H for b in H)
identity = (0, 1, 2, 3)
others = [p for p in A4 if p != identity]
count6 = sum(1 for c in combinations(others, 5) if closed(set(c) | {identity}))
print("Subgroups of A4 with 6 elements:", count6)
Output:
Z_6 without 0, multiplication mod 6: (False, 'not closed')
Z_7 without 0, multiplication mod 7: (True, 'group, identity 1')
U(8) = [1, 3, 5, 7] group, identity 1 orders {1: 1, 3: 2, 5: 2, 7: 2} NOT cyclic
U(10) = [1, 3, 7, 9] group, identity 1 orders {1: 1, 3: 4, 7: 4, 9: 2} cyclic
Orders in Z_12: {0: 1, 1: 12, 2: 6, 3: 4, 4: 3, 5: 12, 6: 2, 7: 12, 8: 3, 9: 4, 10: 6, 11: 12}
Generators of Z_12: [1, 5, 7, 11]
Subgroup orders of Z_12: [1, 2, 3, 4, 6, 12]
|A4| = 12 | group check: True
Subgroups of A4 with 6 elements: 0
The first line shows why we must remove more than 0 when n is composite: 2 × 3 ≡ 0 (mod 6), so {1, …, 5} is not even closed. Only the elements coprime to n, the group U(n), survive.
Common Mistakes
Forgetting closure. {1, …, 5} under multiplication mod 6 fails before you even look for inverses.
Assuming the identity is 0 or 1. For a ∗ b = a + b − 1 it is 1; for a ∗ b = a + b + 5 it is −5. Solve a ∗ e = a.
Writing (ab)−1 = a−1b−1. The correct order is b−1a−1; the two agree only when the elements commute.
Believing the converse of Lagrange. A divisor of |G| need not be the order of any subgroup (A4 and 6) or of any element (V4 has no element of order 4).
Thinking abelian implies cyclic. V4 is abelian but not cyclic. Cyclic does imply abelian.
Checking only one side for identity or inverse. In a non-abelian setting you need both e ∗ a = a and a ∗ e = a (though in a group, a one-sided inverse turns out to be two-sided).
Practice and GATE-Style Questions
Q1. How many generators does a cyclic group of order 20 have?
φ(20) = 20 × (1 − 1/2)(1 − 1/5) = 8 (in ℤ20: 1, 3, 7, 9, 11, 13, 17, 19).
Q2. What is the order of 18 in ℤ30?
30 / gcd(30, 18) = 30/6 = 5. Check: 5 × 18 = 90 = 3 × 30.
Q3. A group G has order 35. Can it contain an element of order 10? Can it have a subgroup of order 7?
10 does not divide 35, so by Lagrange no element of order 10. A subgroup of order 7 is allowed by Lagrange (and in fact exists: every group of order 35 is cyclic), but note that Lagrange alone only says it is possible.
Q4. On ℚ − {0}, define a ∗ b = ab/2. Find the identity and the inverse of 4.
a ∗ e = ae/2 = a gives e = 2. The inverse b of 4 needs 4b/2 = 2, so b = 1. (Associativity: (ab/2)c/2 = abc/4 = a(bc/2)/2. ✓)
Q5. Compute 2100 mod 7 using group theory.
In the multiplicative group mod 7, o(2) = 3 since 23 = 8 ≡ 1. 100 = 3 × 33 + 1, so 2100 = (23)33 · 2 ≡ 2 (mod 7).
Q6. How many binary operations can be defined on a set with 3 elements? How many are commutative?
39 = 19683 in total; commutative ones: 36 = 729 (6 unordered pairs including the 3 pairs {a, a}).
Summary
Closure → magma; + associativity → semigroup; + identity → monoid; + inverses → group; + commutativity → abelian group.
Identity and inverses are unique; cancellation holds; (ab)−1 = b−1a−1; a Cayley table is a Latin square.
In ℤn, o(k) = n / gcd(n, k); a cyclic group of order n has φ(n) generators and exactly one subgroup per divisor of n.
Lagrange: |H| divides |G| because cosets partition G into equal blocks. Consequences: o(a) | |G|, prime-order groups are cyclic, Fermat and Euler's theorems. The converse is false (A4).
Homomorphisms preserve the operation; isomorphic groups are identical in structure. ℤ4 and V4 are the two groups of order 4; S3 is the smallest non-abelian group.
A group is the minimum structure in which every action can be combined and undone. Lagrange's theorem shows how much that little structure forces: the size of every subgroup must divide the size of the whole.