02a-what-is-a-ring.ipynb

Kernel: SageMath 10.5

What Is a Ring?

Module 02a | Rings, Fields, and Polynomials

Two operations, one structure. The distributive law is the glue that holds a ring together.

Question: In $\mathbb{Z}/12\mathbb{Z}$, we know that $3 \neq 0$ and $4 \neq 0$. But compute $3 \times 4$:

$$3 \times 4 = 12 \equiv 0 \pmod{12}$$

A product of two nonzero numbers is zero! In the integers, this never happens. What kind of algebraic structure allows such bizarre behavior? And why should a cryptographer care?

By the end of this notebook, you will know the answer: rings.

Objectives

By the end of this notebook you will be able to:

1. State the ring axioms and identify the role of each one

2. Verify the ring axioms concretely for $\mathbb{Z}$ and $\mathbb{Z}/12\mathbb{Z}$

3. Explain why the distributive law is the crucial axiom that connects the two operations

4. Distinguish rings from non-rings by finding a failed axiom

5. Articulate the difference between "a group plus multiplication" and an actual ring

Bridge from Module 01

In Module 01, you studied groups, a set with one operation satisfying four axioms (closure, associativity, identity, inverses). You saw groups like $(\mathbb{Z}/n\mathbb{Z}, +)$ and $(\mathbb{Z}/p\mathbb{Z}^*, \times)$.

But you always worked with one operation at a time. Addition or multiplication, never both together.

Now we add a second operation and study how the two interact. This is a fundamentally new idea: in a group, there is nothing connecting different operations. In a ring, there is, and that connection is the distributive law.

Structure	Operations	Key idea
Group	1 (e.g., $+$)	Symmetry, inverses
Ring	2 ($+$ and $\times$)	Two operations linked by distributivity

The Ring Axioms

A ring $(R, +, \times)$ is a set $R$ equipped with two binary operations satisfying:

Addition axioms, $(R, +)$ is an abelian group:

1. Closure under $+$: $a + b \in R$

2. Associativity of $+$: $(a + b) + c = a + (b + c)$

3. Additive identity: there exists $0 \in R$ with $a + 0 = a$

4. Additive inverses: for every $a$, there exists $-a$ with $a + (-a) = 0$

5. Commutativity of $+$: $a + b = b + a$

Multiplication axioms, $(R, \times)$ is a monoid: 6. Closure under $\times$: $a \times b \in R$ 7. Associativity of $\times$: $(a \times b) \times c = a \times (b \times c)$ 8. Multiplicative identity: there exists $1 \in R$ with $a \times 1 = 1 \times a = a$

The glue, the distributive law: 9. Left distributivity: $a \times (b + c) = a \times b + a \times c$ 10. Right distributivity: $(a + b) \times c = a \times c + b \times c$

Notice: multiplication does not need to be commutative, and elements do not need multiplicative inverses. These are optional upgrades (commutative rings, fields).

Verifying: $\mathbb{Z}$ Is a Ring

The integers under ordinary addition and multiplication form the most fundamental ring. Let's verify each axiom group.

# === The integers Z as a ring ===
R = ZZ
print(f'Ring: {R}')
print(f'Is ring? {R in Rings()}')
print(f'Is commutative? {R.is_commutative()}')
print()

# Pick concrete elements
a, b, c = 7, -3, 5
print('=== Addition axioms (abelian group) ===')
print(f'Closure: {a} + {b} = {a + b} (still an integer)')
print(f'Associativity: ({a}+{b})+{c} = {(a+b)+c}, {a}+({b}+{c}) = {a+(b+c)}')
print(f'Identity: {a} + 0 = {a + 0}')
print(f'Inverses: {a} + ({-a}) = {a + (-a)}')
print(f'Commutativity: {a}+{b} = {a+b}, {b}+{a} = {b+a}')
print()

print('=== Multiplication axioms (monoid) ===')
print(f'Closure: {a} * {b} = {a * b} (still an integer)')
print(f'Associativity: ({a}*{b})*{c} = {(a*b)*c}, {a}*({b}*{c}) = {a*(b*c)}')
print(f'Identity: {a} * 1 = {a * 1}')
print()

print('=== The glue: distributive law ===')
print(f'Left:  {a} * ({b} + {c}) = {a * (b + c)}')
print(f'       {a}*{b} + {a}*{c} = {a*b + a*c}')
print(f'Right: ({a} + {b}) * {c} = {(a + b) * c}')
print(f'       {a}*{c} + {b}*{c} = {a*c + b*c}')

All axioms check out. SageMath already knows $\mathbb{Z}$ is a ring, ZZ in Rings() returns True.

But notice what is missing: most integers have no multiplicative inverse. There is no integer $x$ with $7x = 1$. This is fine, rings do not require multiplicative inverses.

Verifying: $\mathbb{Z}/12\mathbb{Z}$ Is a Ring

From Module 01, you know $(\mathbb{Z}/12\mathbb{Z}, +)$ is a group. But $\mathbb{Z}/12\mathbb{Z}$ also has multiplication. Is it a ring?

Checkpoint: Before running the next cell, predict: what is $7 \times 9$ in $\mathbb{Z}/12\mathbb{Z}$? And does $5 \times (3 + 8)$ equal $5 \times 3 + 5 \times 8$ when we work mod 12?

# === Z/12Z as a ring ===
R = Zmod(12)
print(f'Ring: {R}')
print(f'Is ring? {R in Rings()}')
print()

a, b, c = R(7), R(9), R(5)

print('--- Addition (abelian group, just like Module 01) ---')
print(f'{a} + {b} = {a + b}')
print(f'Additive identity: 0 = {R.zero()}')
print(f'Additive inverse of {a}: {-a}  (check: {a} + {-a} = {a + (-a)})')
print()

print('--- Multiplication (monoid) ---')
print(f'{a} * {b} = {a * b}')
print(f'Multiplicative identity: 1 = {R.one()}')
print(f'{a} * 1 = {a * R.one()}')
print()

# The crucial test: distributive law
a, b, c = R(5), R(3), R(8)
print('--- Distributive law (the glue!) ---')
lhs = a * (b + c)
rhs = a * b + a * c
print(f'{a} * ({b} + {c}) = {a} * {b + c} = {lhs}')
print(f'{a}*{b} + {a}*{c} = {a*b} + {a*c} = {rhs}')
print(f'Equal? {lhs == rhs}')

Let's do a brute-force check of the distributive law for every triple $(a, b, c)$ in $\mathbb{Z}/12\mathbb{Z}$:

# Exhaustive verification of distributivity in Z/12Z
R = Zmod(12)
violations = 0
total = 0

for a in R:
    for b in R:
        for c in R:
            total += 1
            if a * (b + c) != a * b + a * c:
                violations += 1
                print(f'VIOLATION: {a}*({b}+{c}) != {a}*{b} + {a}*{c}')

print(f'\nChecked {total} triples. Violations: {violations}.')
print(f'The distributive law holds for ALL triples in Z/12Z.')

1,728 triples, zero violations. $\mathbb{Z}/12\mathbb{Z}$ is indeed a ring.

The Distributive Law: Why It Matters

Out of the 10 axioms, the distributive law is the only one that connects addition and multiplication. Without it, $+$ and $\times$ would just be two unrelated operations living on the same set, like having a bicycle and a piano in the same room. The distributive law is what makes them talk to each other.

Here is a concrete demonstration of its power:

# The distributive law lets us DERIVE new facts from old ones.
# Example: Why does a * 0 = 0 in any ring?
#
# Proof:  a * 0 = a * (0 + 0)       [since 0 is the additive identity]
#               = a*0 + a*0           [by the distributive law!]
# So:    a*0 = a*0 + a*0
# Subtract a*0 from both sides:  0 = a*0.  QED.

# Let's verify this consequence in Z/12Z:
R = Zmod(12)
print('a * 0 for every element of Z/12Z:')
for a in R:
    print(f'  {a} * 0 = {a * R.zero()}')

print('\nThis is not an axiom, it is a CONSEQUENCE of the distributive law.')
print('Without distributivity, we could not prove a*0 = 0.')

Checkpoint: Using the same style of argument, can you prove that $a \times (-b) = -(a \times b)$ in any ring? The key step uses distributivity: $a \times b + a \times (-b) = a \times (b + (-b)) = a \times 0 = 0$.

# Verify: a * (-b) == -(a * b) in Z/12Z
R = Zmod(12)
print('Checking a * (-b) == -(a*b) for all a, b in Z/12Z...')
all_hold = True
for a in R:
    for b in R:
        if a * (-b) != -(a * b):
            print(f'  FAIL: a={a}, b={b}')
            all_hold = False

if all_hold:
    print('Verified for all 144 pairs: a * (-b) = -(a*b) always holds.')
    print('\nThis is another consequence of the distributive law, not an axiom.')

The Big Misconception

Common mistake: "A ring is just a group with multiplication added on top." No! If you take an abelian group $(R, +)$ and slap a multiplication operation onto the same set, you do not automatically get a ring. You need the distributive law: $a(b + c) = ab + ac$. This is a nontrivial requirement that constrains how $\times$ can behave relative to $+$.

Think of it this way: there are many possible multiplication operations on $\{0, 1, \ldots, 11\}$, but only those satisfying distributivity (with respect to addition mod 12) produce a ring. The distributive law is what makes the two operations into a system.

To drive this home, let's construct a fake multiplication on $\mathbb{Z}/5\mathbb{Z}$ that does NOT satisfy the distributive law, proving that distributivity is a real constraint:

# A FAKE multiplication on Z/5Z that violates distributivity.
# Define: a (*) b = (a + b) mod 5   [this is NOT standard multiplication!]
#
# (Z/5Z, +) is an abelian group.
# (Z/5Z, (*)) has closure, associativity, and identity = 0.
# But is the distributive law satisfied?

n = 5

def fake_mult(a, b, n):
    """A fake 'multiplication': a (*) b = (a + b) mod n."""
    return (a + b) % n

# Test distributivity: a (*) (b + c) vs a (*) b + a (*) c
print('Testing fake multiplication a (*) b = (a + b) mod 5 for distributivity:\n')
violations = 0
for a in range(n):
    for b in range(n):
        for c in range(n):
            lhs = fake_mult(a, (b + c) % n, n)
            rhs = (fake_mult(a, b, n) + fake_mult(a, c, n)) % n
            if lhs != rhs:
                violations += 1
                if violations <= 3:  # show first few
                    print(f'  VIOLATION: {a} (*) ({b}+{c}) = {a} (*) {(b+c)%n} = {lhs}')
                    print(f'             {a}(*){b} + {a}(*){c} = {fake_mult(a,b,n)} + {fake_mult(a,c,n)} = {rhs}')
                    print()

print(f'Total violations: {violations} out of {n**3} triples.')
print(f'\nThis fake operation + standard addition does NOT form a ring.')
print('The distributive law is a genuine constraint, not a free bonus.')

A Non-Example: The Natural Numbers

The natural numbers $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ have addition and multiplication, and the distributive law holds. Are they a ring?

Checkpoint: Which ring axiom fails for $\mathbb{N}$? Predict before reading on.

# The natural numbers: what fails?
print('=== Checking N = {0, 1, 2, ...} ===')
print()
print('Closure under +?      Yes: 3 + 5 = 8 is in N')
print('Associativity of +?   Yes: (2+3)+4 = 9 = 2+(3+4)')
print('Additive identity?    Yes: 0 is in N, and a + 0 = a')
print('Commutativity of +?   Yes: 3 + 5 = 5 + 3')
print()
print('Additive inverses?    NO!')
print('  What is -3 in N? It would need to be a natural number x')
print('  with 3 + x = 0. But x = -3 is NOT a natural number.')
print()
print('Closure under *?      Yes: 3 * 5 = 15')
print('Associativity of *?   Yes')
print('Multiplicative id?    Yes: 1')
print('Distributive law?     Yes: 3*(4+5) = 27 = 12+15 = 3*4+3*5')
print()
print('VERDICT: N is NOT a ring. Additive inverses fail.')
print('(N, +) is not even a group, it is only a monoid.')

This is instructive: $\mathbb{N}$ satisfies 9 out of 10 axioms. But one failure is enough, all axioms must hold.

The fix is to "complete" $\mathbb{N}$ by adding additive inverses: $\mathbb{N} \to \mathbb{Z}$. The integers are the smallest ring containing the natural numbers.

Quick Comparison: Group vs Ring

Let's use SageMath to inspect the structural difference between a group and a ring.

# SageMath can tell us exactly what category an object belongs to
G = Zmod(12)  # as a ring, it has both + and *
print('Z/12Z as SageMath sees it:')
print(f'  Type: {type(G)}')
print(f'  In Rings()? {G in Rings()}')
print(f'  In Groups()? {G in Groups()}')
print(f'  Zero (additive identity): {G.zero()}')
print(f'  One (multiplicative identity): {G.one()}')
print(f'  Characteristic: {G.characteristic()}')
print()

# A group only has ONE operation
H = Zmod(12).additive_group()
print('The additive group of Z/12Z:')
print(f'  Type: {type(H)}')
print(f'  Order: {H.order()}')
print(f'  This is a GROUP, one operation only.')
print()

# The key difference
print('GROUP: one operation, four axioms.')
print('RING:  two operations, ten axioms (including distributivity).')

The Anatomy of a Ring, Summarized

Here is the complete picture:

$$\boxed{\text{Ring} = \underbrace{\text{Abelian group}}_{(R, +)} + \underbrace{\text{Monoid}}_{(R, \times)} + \underbrace{\text{Distributive law}}_{\text{connects } + \text{ and } \times}}$$

The abelian group gives you addition (with inverses). The monoid gives you multiplication (without requiring inverses). The distributive law is the bridge between them.

Common mistake: "If I know $(R, +)$ is a group and $(R, \times)$ is a monoid, then $(R, +, \times)$ must be a ring." Wrong! You also need the distributive law to hold. As we saw with the fake multiplication example, you can have a perfectly good group and a perfectly good monoid on the same set, and still fail to have a ring.

Exercises

Exercise 1 (Worked)

Verify all 10 ring axioms for $\mathbb{Z}/6\mathbb{Z}$. For each axiom, show a concrete example.

# Exercise 1 (Worked). Verify Z/6Z is a ring
R = Zmod(6)
a, b, c = R(4), R(5), R(3)

print(f'Ring: {R}\n')
print('=== Addition axioms (abelian group) ===')
print(f'1. Closure:       {a} + {b} = {a+b} is in Z/6Z')
print(f'2. Associativity: ({a}+{b})+{c} = {(a+b)+c}, {a}+({b}+{c}) = {a+(b+c)}  Equal: {(a+b)+c == a+(b+c)}')
print(f'3. Identity:      {a} + 0 = {a + R.zero()}')
print(f'4. Inverses:      {a} + ({-a}) = {a+(-a)}  (additive inverse of {a} is {-a})')
print(f'5. Commutativity: {a}+{b} = {a+b}, {b}+{a} = {b+a}  Equal: {a+b == b+a}')
print()

print('=== Multiplication axioms (monoid) ===')
print(f'6. Closure:       {a} * {b} = {a*b} is in Z/6Z')
print(f'7. Associativity: ({a}*{b})*{c} = {(a*b)*c}, {a}*({b}*{c}) = {a*(b*c)}  Equal: {(a*b)*c == a*(b*c)}')
print(f'8. Identity:      {a} * 1 = {a * R.one()}')
print()

print('=== Distributive law ===')
print(f'9.  Left:  {a}*({b}+{c}) = {a*(b+c)}, {a}*{b}+{a}*{c} = {a*b+a*c}  Equal: {a*(b+c) == a*b+a*c}')
print(f'10. Right: ({a}+{b})*{c} = {(a+b)*c}, {a}*{c}+{b}*{c} = {a*c+b*c}  Equal: {(a+b)*c == a*c+b*c}')
print()
print(f'All 10 axioms hold: Z/6Z is a ring. SageMath confirms: {R in Rings()}')

Exercise 2 (Guided)

Verify the distributive law for $\mathbb{Z}/7\mathbb{Z}$ by exhaustive computation. Count how many of the $7^3 = 343$ triples $(a, b, c)$ satisfy $a(b+c) = ab + ac$.

# Exercise 2 (Guided). Exhaustive distributivity check for Z/7Z
R = Zmod(7)
violations = 0
total = 0

for a in R:
    for b in R:
        for c in R:
            total += 1
            # TODO: check if a * (b + c) == a * b + a * c
            # If not, increment violations and print the triple
            pass  # replace this line

# TODO: print the total number of triples checked and violations found
# Hint: you should find 0 violations (Z/7Z really is a ring!)

# BONUS TODO: also check right distributivity (a+b)*c == a*c + b*c
# Question: for a COMMUTATIVE ring, does left distributivity
#           automatically imply right distributivity? Why?

Exercise 3 (Independent)

Consider the set of $2 \times 2$ integer matrices $M_2(\mathbb{Z})$. SageMath represents this as MatrixSpace(ZZ, 2).

1. Pick three matrices $A, B, C$ and verify left distributivity: $A(B + C) = AB + AC$.

2. Is multiplication commutative? Find matrices where $AB \neq BA$.

3. Does SageMath confirm this is a ring?

This is an example of a non-commutative ring, multiplication does not commute, but all ring axioms still hold.

# Exercise 3 (Independent). Your code here
# Hint: M = MatrixSpace(ZZ, 2)
#        A = M([1, 2, 3, 4])
#        B = M([0, 1, 1, 0])

Summary

Concept	Key idea
Ring	A set with two operations ($+$ and $\times$) satisfying ten axioms
Abelian group + monoid	$(R, +)$ must be an abelian group, and $(R, \times)$ must be a monoid (associative with identity)
Distributive law	The crucial axiom $a(b+c) = ab + ac$ is the only one involving both operations, making them a coherent system
$\mathbb{Z}$ and $\mathbb{Z}/n\mathbb{Z}$	Both are rings under ordinary (or modular) addition and multiplication
$\mathbb{N}$ is not a ring	The natural numbers fail the additive inverses axiom, one failure is enough
Optional upgrades	Rings do not require multiplicative inverses or commutativity of $\times$

Crypto foreshadowing: AES (the Advanced Encryption Standard) performs all of its operations inside the ring $\text{GF}(2)[x] / (x^8 + x^4 + x^3 + x + 1)$, a quotient of a polynomial ring. In Module 02f, you will build this ring yourself. The distributive law is what makes AES's MixColumns operation work correctly.

Next: Integers Mod n as a Ring, zero divisors, units, and the strange things that happen in $\mathbb{Z}/12\mathbb{Z}$ that cannot happen in $\mathbb{Z}$.