Skip to content
Tutorials Center
My learning

Topics

Lesson 52 of 68 ยท Algebraic Structures and Boolean Algebra

Groups, Rings and Fields (Gentle Intro)

Meet groups, rings and fields through modular arithmetic and the symmetries of a square, and check the axioms by brute force in Python.

You have used operations like addition, multiplication and function composition many times, and they all obey similar rules: there is a "do nothing" element, every action can be undone, and grouping does not matter. Abstract algebra takes those shared rules, names them, and studies every system that satisfies them at once. A result proved for "any group" then applies to clock arithmetic, to rotating a square, to shuffling cards and to the keys used in cryptography.

This is a gentle introduction. We define groups, rings and fields, build them from modular arithmetic and from symmetries of a square, and, because everything here is finite, we verify the axioms by exhaustively checking them in Python. You do not need any theory beyond sets and functions.

Three levels of structure

Group One operation that can always be undone.
Ring Add, subtract and multiply.
Field A ring where you can also divide.
1 / 2

What a group is

A group is a set G with a binary operation โˆ˜ such that:

  1. Closure: for all a, b in G, a โˆ˜ b is in G.
  2. Associativity: (a โˆ˜ b) โˆ˜ c = a โˆ˜ (b โˆ˜ c).
  3. Identity: there is an element e with e โˆ˜ a = a โˆ˜ e = a for every a.
  4. Inverses: for every a there is an element aโปยน with a โˆ˜ aโปยน = aโปยน โˆ˜ a = e.

If also a โˆ˜ b = b โˆ˜ a for all a, b, the group is abelian (commutative). The number of elements is the group's order.

Familiar examples: the integers under addition (identity 0, the inverse of a is -a), the nonzero rationals under multiplication, and the integers modulo n under addition. Non-examples teach just as much: the integers under multiplication fail because 2 has no integer inverse, and the natural numbers under addition fail because there are no negatives.

For finite structures, we can check all four axioms directly. The following code does it, and applies it to four small structures from modular arithmetic. Watch which ones pass.

Python Checking group axioms by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output shows a general pattern. Z_n under addition is always a group. Z_n under multiplication is not (0 has no inverse, and neither do numbers sharing a factor with n). Dropping 0 helps only when n is prime, as with Z_7. For any n, the set of units, the residues coprime to n, is a group under multiplication, written Z_n^*. That is the group behind Euler's theorem and RSA.

Permutation groups and the symmetries of a square

Groups often arise as symmetries: the ways to move an object that leave it looking unchanged. Combining two symmetries (do one, then the other) is the group operation; the identity is "do nothing"; the inverse is "undo".

A permutation of a set is a bijection from the set to itself. All permutations of {0, 1, ..., n-1} under composition form the symmetric group S_n, which has n! elements. S_3 has 6 elements, and it is the smallest non-abelian group: swapping the first two items and then the last two is not the same as doing them in the opposite order.

Now label the corners of a square 0, 1, 2, 3 going around. Which rigid motions return the square onto itself? Four rotations (0ยฐ, 90ยฐ, 180ยฐ, 270ยฐ) and four reflections (two across the diagonals, two across the midlines). That gives a group of 8 elements, the dihedral group D_4. Each motion is just a permutation of the four corners, so we can compute with it. We generate the whole group from two ingredients: the 90ยฐ rotation r and one reflection s.

Python The symmetry group of a square

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two things to notice. The element orders show that two elements of D_4 have order 4 (the quarter turns), five have order 2 (the half turn and four reflections), and the identity has order 1. And D_4 is non-abelian: rotating then reflecting gives a different result from reflecting then rotating. That is intuitive for physical motions, and it means order matters.

A set of elements that is a group on its own is a subgroup. The rotations {e, r, rยฒ, rยณ} form a subgroup of order 4. Lagrange's theorem says the order of a subgroup always divides the order of the group, so a group of order 8 can only have subgroups of orders 1, 2, 4 or 8. It is one reason why group structure is so restrictive and so useful.

Subgroups, cyclic groups and cosets

A subset H of a group G is a subgroup when it is a group on its own under the same operation. You do not need to recheck all four axioms. The subgroup test says that a nonempty finite subset H is a subgroup exactly when it is closed under the operation: a โˆ˜ b is in H whenever a and b are. (In a finite group, closure alone forces the identity and inverses, because repeated powers of an element eventually cycle back to the identity.)

The order of an element a is the smallest k โ‰ฅ 1 with a^k = e, where a^k means a combined with itself k times. The powers e, a, aยฒ, ..., a^(k-1) form a subgroup โŸจaโŸฉ, the subgroup generated by a, and it has exactly k elements. If one element generates the whole group, the group is cyclic. Z_n under addition is cyclic with generator 1, and the generators of Z_n are the residues coprime to n.

A Cayley table lists every product a โˆ˜ b in a grid. It is the group's multiplication table: every row and every column contains each element exactly once, which is a quick visual test for inverses and cancellation.

Python Orders, generators, subgroups and a Cayley table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Cosets and Lagrange's theorem

Take a subgroup H and any element g of G. The left coset gH is the set {g โˆ˜ h : h in H}, and the right coset Hg is {h โˆ˜ g : h in H}. Three facts make cosets useful:

  1. Every coset has exactly |H| elements (multiplying by g is reversible).
  2. Two left cosets are either identical or completely disjoint, so the left cosets partition G.
  3. Therefore |G| = (number of cosets) ยท |H|, which is Lagrange's theorem: the order of a subgroup divides the order of the group. The number of cosets is the index of H in G.

A direct consequence is that the order of every element divides |G| (because โŸจaโŸฉ is a subgroup), so a^|G| = e. For the group Z_n^* of units, that statement is exactly Euler's theorem from modular arithmetic.

In an abelian group, gH = Hg always. In a non-abelian group, left and right cosets can differ, as the symmetric group S_3 shows.

Python Left and right cosets in S3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The subgroup {e, swap} has left and right cosets that disagree, but the rotation subgroup does not. Subgroups whose left and right cosets always agree are called normal. They are exactly the subgroups that can be the kernel of a homomorphism, and they let you divide a group by a subgroup to get a smaller quotient group.

Rings and fields

Many systems have two operations. A ring is a set with addition and multiplication where:

  • the set is an abelian group under addition (identity 0),
  • multiplication is associative (and usually has an identity 1),
  • multiplication distributes over addition: a(b + c) = ab + ac.

The integers and the integers mod n are rings. A ring need not allow division. In Z_6, we have 2 ยท 3 = 0, so 2 and 3 are "zero divisors", and 2 has no multiplicative inverse.

A field is a commutative ring where every nonzero element has a multiplicative inverse. In other words, you can add, subtract, multiply and divide (except by zero). The rationals, the reals and the complex numbers are fields. Surprisingly, there are also finite fields: Z_p is a field exactly when p is prime. Finite fields are everywhere in modern computing: error-correcting codes, AES encryption and elliptic curves all calculate inside them.

Finite fields exist for every size p^k with p prime, but only the prime-size ones are Z_p. A field of 4 elements cannot be Z_4 (since 2 ยท 2 = 0). One builds it from polynomials over {0, 1} modulo xยฒ + x + 1: the four elements are 0, 1, x, x + 1, addition is XOR on coefficients, and multiplication multiplies polynomials and then reduces using xยฒ = x + 1. We can verify that this really is a field with the same style of brute force.

Python Which Z_n are fields, and a field of 4 elements

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first table is exactly the pattern from primes and divisibility: Z_n supports division precisely when n has no nontrivial factors. The GF(4) table shows a field that is not made of ordinary numbers, yet every nonzero element has an inverse.

Ring axioms and integral domains

To see what each ring axiom buys you, check them one by one. A ring (R, +, ยท) requires (R, +) to be an abelian group, multiplication to be associative, and both distributive laws (a(b + c) = ab + ac and (a + b)c = ac + bc). If multiplication commutes the ring is commutative; if some 1 satisfies 1 ยท a = a, the ring has a unity.

Three nested classes matter:

  • A commutative ring with unity can have zero divisors: nonzero a, b with ab = 0.
  • An integral domain is a commutative ring with unity 1 โ‰  0 and no zero divisors. The integers are the model. The key benefit is cancellation: if a โ‰  0 and ab = ac, then b = c.
  • A field is a commutative ring with unity where every nonzero element has an inverse.

Every field is an integral domain (multiply ab = 0 by aโปยน). The reverse fails for infinite rings: the integers are a domain but not a field. For finite rings it holds: every finite integral domain is a field. So Z_n is a domain exactly when n is prime, and then it is a field.

Python Ring axioms, zero divisors and cancellation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that "no zero divisors", "cancellation works" and "is a field" switch on together for prime n. That is why arithmetic modulo a prime supports linear algebra, polynomial interpolation and secret sharing, while arithmetic modulo a composite number does not divide cleanly.

Why algebra pays off

Proving a fact once for all groups is far more efficient than proving it for each example. Here are a few payoffs you will meet later:

  • Cryptography: RSA lives in the group Z_n^*; Diffie-Hellman uses a cyclic group; elliptic-curve cryptography uses a group of points on a curve.
  • Coding theory: error-correcting codes such as Reed-Solomon (QR codes, CDs) are built over finite fields.
  • Symmetry in science and puzzles: crystal structures, molecules and the Rubik's Cube all have group descriptions, and the cube's group has more than 43 quintillion elements.
  • Counting: the number of essentially different colorings of a necklace comes from counting symmetries (Burnside's lemma).

You do not need all that now. Remember the pattern: name the rules, then check them. Our brute-force checkers are slow but they show exactly what the axioms mean.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which of these is a group?

    Integers under addition satisfy closure, associativity, identity 0 and inverses -a. The other three lack inverses for some elements.
  2. 2. How many elements does the symmetric group S4 have?

    S_n has n! elements, and 4! = 24.
  3. 3. Why is the symmetry group of a square (D4) non-abelian?

    The check sr == rs fails; the order in which you apply symmetries can change the result.
  4. 4. For which n is Z_n (integers mod n) a field?

    Every nonzero residue needs an inverse, which happens only when n has no factor shared with any nonzero residue, i.e. n is prime.
  5. 5. A subgroup of a group of order 8 could have which order?

    By Lagrange's theorem the order of a subgroup divides the order of the group, and only 4 divides 8 among these choices.

Summary

  • A group is a set with one operation that is closed and associative, has an identity, and gives every element an inverse; abelian groups also commute.
  • Z_n is a group under addition; the units of Z_n (residues coprime to n) form a group under multiplication.
  • Symmetries form groups; permutations of n objects form S_n of order n!, and the symmetries of a square form the 8-element non-abelian group D_4.
  • A ring has addition and multiplication linked by distributivity; a field also lets you divide by every nonzero element.
  • Z_n is a field exactly when n is prime, and finite fields of size p^k also exist (for example GF(4)).
  • With finite sets you can check every axiom by brute force.

Next: Finite Automata and Regular Languages, where machines with a few states recognize patterns.