The Lumenary · Early undergraduate

Algebraic structures: monoids, groups and rings

Name: ______________________

Date: ______________________

You will learn to

Define binary operations, monoids, groups, rings and fields, and test examples and non-examples such as $(\N, +)$ , $(\Z, +)$ , $(\Z, \times)$ , $\Z/n\Z$ , $2 \times 2$ matrices and functions under composition
Prove that an identity element is unique and that inverses in a monoid are unique, and derive the basic rules of algebra in a group
Explain why $\Z$ is a ring but not a field while $\Q$ is a field, and prove that $\Z/n\Z$ is a field exactly when $n$ is prime
Show that the functions from a set to itself form a monoid under composition whose invertible elements form the symmetric group
Recognise homomorphisms and isomorphisms, and prove that a group homomorphism preserves identities and inverses

1.
Which of these are groups? (Choose all that apply.)
- A. $(\N, +)$
- B. $(\Z, +)$
- C. $(\Z \setminus \{0\}, \times)$
- D. $(\Q_{>0}, \times)$ , the positive rationals
- E. $(\Z/6\Z, \times)$
- F.the bijections $\{1, 2, 3\} \to \{1, 2, 3\}$ under composition
2.
The operation $a \ast b = \gcd(a, b)$ on $\N = \{0, 1, 2, \dots\}$ is associative and commutative. Which natural number $e$ is its identity element, i.e. satisfies $\gcd(e, a) = a$ for every $a \in \N$ ?
3.
Find the inverse of $7$ in $\Z/26\Z$ : the number $x \in \{1, \dots, 25\}$ with $7x \equiv 1 \pmod{26}$ . (This is the key step in decoding an affine cipher.)
4.
The proof that inverses in a monoid are unique reads: if $ba = 1$ and $ac = 1$ then $b = b1 = b(ac) = (ba)c = 1c = c$ . Which equality uses associativity?
- A. $b = b1$
- B. $b1 = b(ac)$
- C. $b(ac) = (ba)c$
- D. $1c = c$
5.
Between groups, any $f$ with $f(ab) = f(a)f(b)$ automatically satisfies $f(1) = 1$ . Which example shows that this fails for monoids, so that $f(1) = 1$ must be required separately?
- A. $f : (\Z, \times) \to (\Z, \times)$ , $f(a) = 0$
- B. $\exp : (\R, +) \to (\R_{>0}, \times)$
- C. $\Z \to \Z/5\Z$ , $a \mapsto a \bmod 5$ , for multiplication
- D.the identity map $(\N, +) \to (\N, +)$
6.
$\Z/91\Z$ is not a field. Find the smallest $x \in \{1, \dots, 90\}$ with $7x \equiv 0 \pmod{91}$ , which exhibits $7$ as a zero divisor.
7.
Which Lean statement correctly formalises "in a monoid, a left inverse and a right inverse of the same element are equal"?
- A.theorem t {M : Type*} [Monoid M] {a b c : M} (hb : b * a = 1) (hc : a * c = 1) : b = c
- B.theorem t {M : Type*} [Monoid M] {a b c : M} (hb : a * b = 1) (hc : a * c = 1) : b = c
- C.theorem t {M : Type*} [Monoid M] {a b c : M} : b * a = 1 ∧ a * c = 1 ∧ b = c
- D.theorem t {M : Type*} [Group M] {a b : M} (h : b * a = 1) : b = a⁻¹
8.
Write is_group(elements, op) that returns True exactly when op (a Python function of two arguments) is a group operation on the finite list elements: check closure, associativity, an identity, and inverses. Then test it on addition modulo 5, multiplication modulo 6, and multiplication modulo 12 on the units $\{1, 5, 7, 11\}$ .
Computational — Practice

Answer key — Algebraic structures: monoids, groups and rings

1.
$(\Z, +)$ , $(\Q_{>0}, \times)$ and $S_3$ are groups. $(\N, +)$ , $(\Z \setminus \{0\}, \times)$ and $(\Z/6\Z, \times)$ are monoids in which some elements have no inverse ( $1$ , $2$ and $2$ respectively, for example).
2.
Every natural number divides $0$ , so $\gcd(0, a) = a$ for all $a$ : the identity is $0$ . (For $\operatorname{lcm}$ the identity is $1$ .) An identity element is whatever does nothing — it need not be the $0$ of addition or the $1$ of multiplication, and here it is $0$ for a reason unrelated to addition.
3.
Back-substituting in Euclid's algorithm: $1 = 5 - 2 \cdot 2 = 5 - 2(7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3(26 - 3 \cdot 7) - 2 \cdot 7 = 3 \cdot 26 - 11 \cdot 7$ . So $7 \cdot (-11) \equiv 1$ , and $-11 \equiv 15 \pmod{26}$ . Check: $7 \cdot 15 = 105 = 4 \cdot 26 + 1$ . The inverse exists because $\gcd(7, 26) = 1$ .
4.
The step $b(ac) = (ba)c$ is associativity. The other steps use the identity laws and the two hypotheses. The proof of uniqueness of the identity, by contrast, uses no associativity at all.
5.
The zero map on $(\Z, \times)$ preserves products, $0 = 0 \cdot 0$ , but sends $1 \mapsto 0$ . In a group, $f(1)f(1) = f(1)$ lets us cancel $f(1)$ ; in the monoid $(\Z, \times)$ , the equation $0 \cdot 0 = 0$ cannot be cancelled to give $0 = 1$ .
6.
$91 = 7 \cdot 13$ , so $7 \cdot 13 = 91 \equiv 0$ , while neither $7$ nor $13$ is $0$ modulo $91$ . If $7x \equiv 0$ then $13 \mid x$ , so $13$ is the smallest choice. A field has no zero divisors (if $ab = 0$ and $a \neq 0$ then $b = a^{-1}ab = 0$ ), so $\Z/91\Z$ is not a field — exactly as Theorem 8 predicts for a composite modulus.
7.
Option (a): the hypotheses are b * a = 1 (left inverse) and a * c = 1 (right inverse) in a Monoid, and the conclusion is b = c. Option (b) assumes two right inverses, which can differ; (c) turns hypotheses into claims about all elements, which is false; (d) is a different (true) theorem about groups.

def is_group(elements, op):
    s = set(elements)
    if any(op(a, b) not in s for a in elements for b in elements):
        return False
    if any(op(op(a, b), c) != op(a, op(b, c))
           for a in elements for b in elements for c in elements):
        return False
    ids = [e for e in elements
           if all(op(e, a) == a == op(a, e) for a in elements)]
    if not ids:
        return False
    e = ids[0]
    return all(any(op(a, b) == e == op(b, a) for b in elements)
               for a in elements)

By Theorem 1 there is at most one identity, so taking ids[0] loses nothing. Checking associativity takes $n^3$ evaluations — feasible for small tables, but it is exactly the kind of check that a proof does once for all sizes.