Study guide: Algebraic Structures
Overview
An algebraic structure is a set together with operations that obey stated rules. Adding more rules gives stronger structures: semigroups, monoids and groups. Groups capture symmetry and underlie modern cryptography.
Key ideas explained
Closure, associativity, identity, inverses
A semigroup has a closed, associative operation. A monoid also has an identity element. A group also has an inverse for every element. If the operation is commutative as well, the group is abelian.
Reading a Cayley table
A Cayley table lists a ∘ b for all pairs. Closure holds when every entry is in the set. The identity is the element whose row and column repeat the headers. In a group each element appears exactly once in every row and column, so the table is a Latin square.
Subgroups, order and Lagrange's theorem
A subgroup is a subset that is itself a group. Lagrange's theorem says the size of a subgroup divides the size of the group, and so does the order of any element. A cyclic group is generated by a single element.
Common examples
(ℤ, +) is a group; (ℤ, ·) is only a monoid; (ℤₙ, +) is a cyclic group; the non-zero residues modulo a prime p form a group under multiplication; strings under concatenation form a monoid; permutations of n ≥ 3 objects form a non-abelian group.
Worked examples
Addition modulo 4
Problem. Analyse ({0,1,2,3}, + mod 4).
- The identity is 0. Inverses: 0 ↔ 0, 1 ↔ 3, 2 ↔ 2.
- It is commutative, so the group is abelian.
- Starting from 1 we get 1, 2, 3, 0, so 1 generates the group (and so does 3).
- The subset {0, 2} is a subgroup of order 2, which divides 4.
Answer. A cyclic abelian group of order 4.
Multiplication modulo 4 versus modulo 5
Problem. Is ({0,1,2,3}, × mod 4) a group? What about ({1,2,3,4}, × mod 5)?
- Modulo 4 the identity is 1, but 0 has no inverse, and 2·x gives only 0 or 2, never 1, so 2 has no inverse either.
- Modulo 5 every element has an inverse: 1 ↔ 1, 2 ↔ 3, 4 ↔ 4.
Answer. The first is only a monoid. The second is a group.
Enter these same values in the calculator above and compare each step with the working shown here.
Common mistakes to avoid
- Assuming closure without checking every pair. The odd integers are not closed under addition.
- Assuming commutativity.
- Confusing the identity with 0. It is 0 for addition and 1 for multiplication.
- Forgetting that 0 has no multiplicative inverse, which is why the multiplicative group uses non-zero residues.
- Testing associativity on a few examples. For a finite structure, a complete check needs every triple.
Where this shows up in computer science
- Diffie–Hellman key exchange and elliptic-curve cryptography work in finite groups, and RSA works in the units modulo n.
- Error-correcting codes use finite fields built from the same ideas.
- Symmetry groups describe molecules, crystals and puzzles such as the Rubik's cube.
Test yourself
Try each question before opening the answer.
Is (ℤ, −) a group?
No. Subtraction is not associative: (5 − 3) − 1 = 1, but 5 − (3 − 1) = 3.
How many generators does (ℤ₆, +) have?
Two: 1 and 5, the residues coprime to 6 (φ(6) = 2).
Can a group of order 12 have a subgroup of order 5?
No. By Lagrange's theorem 5 does not divide 12.