Chapter 30 of 30

Rings & Fields

A group has one operation. But the number systems we actually compute with, the integers, the rationals, the reals, arithmetic mod n, polynomials, matrices, all have two operations, addition and multiplication, tied together by the distributive law. Rings and fields are the abstract versions of these systems.

Why should a CS student care? Because the question "can I divide here?" decides whether an algorithm works. You can always divide by a non-zero number mod 7, but not mod 6 (2 × 3 ≡ 0 mod 6, so 2 has no inverse). That difference is why RSA, Diffie–Hellman and elliptic-curve cryptography work modulo primes, why AES does its byte arithmetic in a field with 256 elements, and why Reed–Solomon codes (in QR codes and storage systems) can correct errors. This chapter builds directly on Groups: every ring is an abelian group under addition with extra structure.

A ring (R, +, ·) is a set with two binary operations such that: (1) (R, +) is an abelian group, with identity 0 and inverses −a; (2) multiplication is associative: (ab)c = a(bc); (3) the distributive laws hold: a(b + c) = ab + ac and (a + b)c = ac + bc. A field is a commutative ring with unity 1 ≠ 0 in which every non-zero element has a multiplicative inverse.

A note on conventions: many modern books require every ring to have a multiplicative identity 1; others (and many Indian university syllabi) allow rings without one and say "ring with unity" when it exists. We follow the second convention and say "with unity" explicitly. All tables in this chapter were generated and checked by computer.


Kinds of Rings

Term

Extra condition

Commutative ring

ab = ba for all a, b

Ring with unity

There is 1 with 1a = a1 = a for all a

Unit

An element a with a multiplicative inverse (ab = ba = 1 for some b)

Zero divisor

A non-zero a such that ab = 0 for some non-zero b

Integral domain

Commutative ring with unity 1 ≠ 0 and no zero divisors

Division ring (skew field)

Ring with unity 1 ≠ 0 where every non-zero element is a unit

Field

Commutative division ring

The hierarchy: fields ⊂ integral domains ⊂ commutative rings with unity ⊂ rings.

Examples

Ring

Commutative?

Unity?

Zero divisors?

Field?

ℤ

Yes

Yes

No (integral domain)

No: 2 has no inverse in ℤ

ℚ, ℝ, ℂ

Yes

Yes

No

Yes

2ℤ (even integers)

Yes

No: 1 ∉ 2ℤ

No

No

ℤ6

Yes

Yes

Yes: 2·3 = 0

No

ℤ7

Yes

Yes

No

Yes

2 × 2 real matrices M2(ℝ)

No

Yes (identity matrix)

Yes

No

Polynomials ℤ[x], ℝ[x]

Yes

Yes

No

No: x has no polynomial inverse

Subsets of a set S, with A + B = A Δ B, A · B = A ∩ B

Yes

Yes (unity S)

Yes if |S| ≥ 2

Only if |S| = 1

The matrix ring shows two new phenomena at once. With A = [[1, 0], [0, 0]] and B = [[0, 0], [0, 1]], we get AB = 0 although A ≠ 0 and B ≠ 0 (zero divisors), and with C = [[0, 1], [0, 0]], AC = C but CA = 0 (non-commutative).

The last row is a Boolean ring: every element satisfies A · A = A (since A ∩ A = A) and A + A = 0 (since A Δ A = ∅). It is the algebra of sets and of bitwise operations: on bit vectors, + is XOR and · is AND.


Consequences of the Ring Axioms

These hold in every ring, and the proofs show how the distributive law links the two operations.

  • a · 0 = 0 · a = 0. Proof: a·0 = a·(0 + 0) = a·0 + a·0. Adding −(a·0) to both sides gives 0 = a·0. (Similarly for 0·a.) Notice this is a theorem, not an axiom.

  • (−a)b = a(−b) = −(ab). Proof: ab + (−a)b = (a + (−a))b = 0·b = 0, so (−a)b is the additive inverse of ab.

  • (−a)(−b) = ab. Apply the previous rule twice. This is why "minus times minus is plus": it is forced by distributivity.

  • If 1 = 0, the ring is {0}. For any a, a = a·1 = a·0 = 0. That is why fields and integral domains require 1 ≠ 0.

Cancellation and zero divisors

In a ring with no zero divisors, the cancellation law holds: if a ≠ 0 and ab = ac, then b = c.

Proof. ab = ac gives a(b − c) = 0. Since a ≠ 0 and there are no zero divisors, b − c = 0. ∎

In ℤ6 cancellation fails: 2·1 = 2·4 = 2 but 1 ≠ 4. Solving equations by "dividing both sides" is only safe in an integral domain.


The Rings ℤn

ℤn = {0, 1, …, n − 1} with addition and multiplication mod n is a commutative ring with unity. Its structure is decided completely by gcd:

  • a is a unit ⇔ gcd(a, n) = 1. If gcd(a, n) = 1, Bézout gives ax + ny = 1, so ax ≡ 1. Conversely, if ax ≡ 1 then ax − 1 is a multiple of n, so any common divisor of a and n divides 1. There are φ(n) units, and they form the group U(n) from Groups.

  • a ≠ 0 is a zero divisor ⇔ gcd(a, n) > 1. If d = gcd(a, n) > 1, then a · (n/d) = (a/d)·n ≡ 0 and n/d ≢ 0. Conversely, a unit is never a zero divisor: if a has an inverse and ab ≡ 0, then b = a−1ab ≡ 0. So when gcd(a, n) = 1, a is not a zero divisor.

  • So every non-zero element of ℤn is either a unit or a zero divisor, never both.

Theorem. For n ≥ 2 the following are equivalent: (a) n is prime; (b) ℤn is an integral domain; (c) ℤn is a field.

If n = rs with 1 < r, s < n, then r·s ≡ 0, so ℤn has zero divisors and is neither an integral domain nor (by the next section, since every field is an integral domain) a field. If n = p is prime, every a ∈ {1, …, p − 1} has gcd(a, p) = 1, so every non-zero element is a unit: ℤp is a field, and hence also an integral domain.

Worked example: ℤ12. Units: 1, 5, 7, 11 (φ(12) = 4). Zero divisors: 2, 3, 4, 6, 8, 9, 10 (for example 4 · 3 = 12 ≡ 0, and 8 · 3 = 24 ≡ 0). 4 + 7 = 11 non-zero elements. ✓

Computing inverses: extended Euclid

Find 7−1 in ℤ13.

13 = 1·7 + 6
 7 = 1·6 + 1          gcd = 1, so 7 is invertible

1 = 7 − 1·6
  = 7 − 1·(13 − 1·7)
  = 2·7 − 1·13        so 7·2 ≡ 1 (mod 13)

7⁻¹ = 2               check: 7·2 = 14 = 13 + 1 ✓

For a prime modulus there is a second way: by Fermat's little theorem ap−2 is the inverse of a (since a · ap−2 = ap−1 ≡ 1).

Solving a linear equation in a field. Solve 3x + 4 = 2 in ℤ7. Subtract 4: 3x = −2 = 5. The inverse of 3 is 5 (3·5 = 15 ≡ 1). So x = 5·5 = 25 ≡ 4. Check: 3·4 + 4 = 16 ≡ 2 ✓. The same steps work in any field, which is exactly why fields are so convenient.


Integral Domains and Fields

Every field is an integral domain.

Proof. Let F be a field and ab = 0 with a ≠ 0. Multiply by a−1: b = a−1ab = a−1·0 = 0. So no zero divisors. ∎

The converse is false: ℤ is an integral domain but not a field. However, the converse holds for finite rings:

Every finite integral domain is a field.

Proof. Let D be a finite integral domain and a ≠ 0. Consider the map f(x) = ax from D to D. It is one-to-one: ax = ay gives x = y by cancellation. A one-to-one map from a finite set to itself is also onto (pigeonhole, see Pigeonhole Principle). So some x has ax = 1, and x = a−1. (Commutativity makes it a two-sided inverse.) ∎

This gives a second proof that ℤp is a field: it is finite and has no zero divisors.

Characteristic

The characteristic of a ring with unity is the smallest positive n with 1 + 1 + … + 1 (n times) = 0, or 0 if no such n exists.

char(ℤ) = char(ℚ) = char(ℝ) = 0; char(ℤn) = n; the Boolean ring has characteristic 2. The characteristic of a field (and of any integral domain) is 0 or a prime. Reason: if char = n = rs with 1 < r, s < n, then (r·1)(s·1) = n·1 = 0 with both factors non-zero, a zero divisor.


Finite Fields

ℤp gives a field of every prime size. Are there fields of other sizes? A field with 4 elements cannot be ℤ4, because 2·2 = 0 in ℤ4. Instead we build it from polynomials, in the same way ℤp is built from integers:

  • Integers mod a prime p → a field with p elements.

  • Polynomials over ℤp mod an irreducible polynomial of degree n (one that cannot be factored into lower-degree polynomials over ℤp) → a field with pn elements.

Constructing GF(4)

Work over ℤ2 with m(x) = x2 + x + 1. It is irreducible because it has no root in ℤ2: m(0) = 1 and m(1) = 1 + 1 + 1 = 1. (For degree 2 and 3, "no root" is the same as "irreducible".) By contrast x2 + 1 = (x + 1)2 over ℤ2, so it would not work.

The elements are the remainders mod m(x): 0, 1, x, x + 1. Coefficients are mod 2, so addition is XOR of coefficients, and whenever x2 appears we replace it by x + 1 (because x2 + x + 1 = 0 and −1 = 1 in ℤ2).

   +   |  0    1    x   x+1          ·   |  0    1    x   x+1
 ------+--------------------        ------+--------------------
   0   |  0    1    x   x+1          0   |  0    0    0    0
   1   |  1    0   x+1   x           1   |  0    1    x   x+1
   x   |  x   x+1   0    1           x   |  0    x   x+1   1
  x+1  | x+1   x    1    0          x+1  |  0   x+1   1    x

Sample computations: x · x = x2 = x + 1; x · (x + 1) = x2 + x = (x + 1) + x = 1; (x + 1)2 = x2 + 1 = x. Every non-zero element has an inverse (x and x + 1 are inverses of each other), so this is a field, written GF(4) or 𝔽4 ("Galois field").

The big facts about finite fields

  • Every finite field has pn elements for some prime p (its characteristic) and n ≥ 1. There is no field with 6 or 10 elements.

  • For every prime power pn there is a field of that size, and it is unique up to isomorphism, so the name GF(pn) is unambiguous.

  • The non-zero elements of a finite field form a cyclic group under multiplication (of order pn − 1). In GF(4): x1 = x, x2 = x + 1, x3 = 1.

Where finite fields appear in computing

Application

Field used

AES (Rijndael) S-box and MixColumns

GF(28) with m(x) = x8 + x4 + x3 + x + 1; each byte is a field element

Reed–Solomon codes (QR codes, CDs/DVDs, RAID-6, deep-space links)

Usually GF(28)

CRC checksums

Polynomial arithmetic over GF(2) (the ring GF(2)[x])

RSA, Diffie–Hellman

The rings ℤn and the groups ℤp∗

Elliptic-curve cryptography

Curves over GF(p) for a large prime p, or over GF(2m)

In GF(28), adding two bytes is just XOR, and multiplication is "shift and XOR, reducing by m(x) whenever the degree reaches 8". The AES standard (FIPS 197) uses the example 0x57 · 0x83 = 0xC1, which our code reproduces below.


Subrings and Ideals (a Short Look)

A subring is a subset that is a ring under the same operations: it must be non-empty and closed under subtraction and multiplication. 2ℤ is a subring of ℤ; ℤ is a subring of ℚ.

An ideal I is a special subring that "absorbs" multiplication: r ∈ R and a ∈ I imply ra, ar ∈ I. The multiples nℤ form an ideal of ℤ. Ideals play the role that normal subgroups play for groups: ℤn is precisely the quotient ring ℤ / nℤ, and GF(pn) is ℤp[x] modulo the ideal generated by an irreducible polynomial. In both cases "quotient by a prime or irreducible" is what produces a field.


Checking with Code

Classify ℤ2 … ℤ12, compute inverses with extended Euclid, build the GF(4) multiplication table, reproduce the AES multiplication example, and verify the Boolean ring laws.

from math import gcd
from itertools import product

# 1. Classify Z_n
for n in range(2, 13):
    units = [a for a in range(1, n) if gcd(a, n) == 1]
    zero_divs = [a for a in range(1, n) if any(a * b % n == 0 for b in range(1, n))]
    kind = "field" if len(units) == n - 1 else "not an integral domain"
    print(f"Z_{n:<2}  units={units}  zero divisors={zero_divs}  -> {kind}")

# 2. Multiplicative inverse mod p with the extended Euclidean algorithm
def inverse_mod(a, m):
    old_r, r, old_s, s = a, m, 1, 0
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
    if old_r != 1:
        raise ValueError("not invertible")
    return old_s % m
print("7^-1 mod 13 =", inverse_mod(7, 13), "| 3^-1 mod 7 =", inverse_mod(3, 7))

# 3. GF(4) = Z_2[x] / (x^2 + x + 1); an element b1*x + b0 is stored as the bits b1 b0
def gf_mul(a, b, modulus, degree):
    result = 0
    while b:
        if b & 1:
            result ^= a            # addition in characteristic 2 is XOR
        b >>= 1
        a <<= 1
        if a >> degree:           # degree too high: subtract (XOR) the modulus
            a ^= modulus
    return result
names = ["0", "1", "x", "x+1"]
print("GF(4) multiplication table:")
for a in range(4):
    print(f"{names[a]:>4} |", " ".join(f"{names[gf_mul(a, b, 0b111, 2)]:>4}" for b in range(4)))

# 4. AES field GF(2^8) with modulus x^8 + x^4 + x^3 + x + 1  (0x11B)
print("AES: 0x57 * 0x83 =", hex(gf_mul(0x57, 0x83, 0x11B, 8)))

# 5. Boolean ring: subsets of {1,2} with symmetric difference (+) and intersection (*)
S = [frozenset(s) for s in ([], [1], [2], [1, 2])]
add = lambda A, B: A ^ B
mul = lambda A, B: A & B
ok = all(mul(A, add(B, C)) == add(mul(A, B), mul(A, C)) for A, B, C in product(S, S, S))
print("Distributive law holds:", ok, "| A*A == A for all A:", all(mul(A, A) == A for A in S),
      "| A+A == empty for all A:", all(add(A, A) == frozenset() for A in S))

Output:

Z_2   units=[1]  zero divisors=[]  -> field
Z_3   units=[1, 2]  zero divisors=[]  -> field
Z_4   units=[1, 3]  zero divisors=[2]  -> not an integral domain
Z_5   units=[1, 2, 3, 4]  zero divisors=[]  -> field
Z_6   units=[1, 5]  zero divisors=[2, 3, 4]  -> not an integral domain
Z_7   units=[1, 2, 3, 4, 5, 6]  zero divisors=[]  -> field
Z_8   units=[1, 3, 5, 7]  zero divisors=[2, 4, 6]  -> not an integral domain
Z_9   units=[1, 2, 4, 5, 7, 8]  zero divisors=[3, 6]  -> not an integral domain
Z_10  units=[1, 3, 7, 9]  zero divisors=[2, 4, 5, 6, 8]  -> not an integral domain
Z_11  units=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  zero divisors=[]  -> field
Z_12  units=[1, 5, 7, 11]  zero divisors=[2, 3, 4, 6, 8, 9, 10]  -> not an integral domain
7^-1 mod 13 = 2 | 3^-1 mod 7 = 5
GF(4) multiplication table:
   0 |    0    0    0    0
   1 |    0    1    x  x+1
   x |    0    x  x+1    1
 x+1 |    0  x+1    1    x
AES: 0x57 * 0x83 = 0xc1
Distributive law holds: True | A*A == A for all A: True | A+A == empty for all A: True

Exactly the primes 2, 3, 5, 7, 11 give fields, and every non-zero element of every other ℤn is either a unit or a zero divisor, as the theory predicts.


Common Mistakes

  • Thinking GF(4) = ℤ4. ℤ4 is not a field (2·2 = 0). GF(4) is built from polynomials over ℤ2.

  • Cancelling in a ring with zero divisors. 2x = 2y in ℤ6 does not imply x = y (x = 1, y = 4).

  • Calling ℤ a field. It is an integral domain; only ±1 are units.

  • Forgetting that (R, +) must be an abelian group. (ℕ, +, ×) is not a ring: no additive inverses.

  • Assuming every ring has a 1 or is commutative. 2ℤ has no unity; matrix rings are not commutative. Check the convention your exam uses.

  • Testing irreducibility of degree ≥ 4 only by roots. x4 + x2 + 1 = (x2 + x + 1)2 over ℤ2 has no roots but is reducible. "No roots ⇒ irreducible" is valid only for degree 2 and 3.


Practice and GATE-Style Questions

Q1. Which of ℤ9, ℤ11, ℤ15 are fields?

Only ℤ11, because 11 is prime. In ℤ9, 3·3 = 0; in ℤ15, 3·5 = 0.

Q2. How many units and how many zero divisors does ℤ20 have?

Units: φ(20) = 8. Every other non-zero element is a zero divisor: 19 − 8 = 11.

Q3. Find the inverse of 5 in ℤ17.

17 = 3·5 + 2, 5 = 2·2 + 1. Back-substitute: 1 = 5 − 2·2 = 5 − 2(17 − 3·5) = 7·5 − 2·17. So 5−1 = 7. Check: 35 = 2·17 + 1 ✓.

Q4. Is there a field with 12 elements? With 16? With 27?

The size of a finite field must be a prime power. 12 = 22·3 is not, so no. 16 = 24 and 27 = 33 are, so yes to both.

Q5. In a Boolean ring (a2 = a for all a), prove that a + a = 0 and that the ring is commutative.

(a + a)2 = a + a. Expanding, a2 + a2 + a2 + a2 = 4a, so 4a = 2a, giving 2a = 0, that is a = −a. Next, (a + b)2 = a + b expands to a + ab + ba + b, so ab + ba = 0, hence ab = −ba = ba. Commutative.

Q6. What is the characteristic of GF(8)? Of ℤ6?

GF(8) = GF(23) has characteristic 2. ℤ6 has characteristic 6 (allowed, since ℤ6 is not an integral domain).


Summary

  • A ring is an abelian group under + with an associative · that distributes over +. Commutative rings, rings with unity, integral domains and fields add conditions step by step.

  • a·0 = 0 and (−a)(−b) = ab follow from distributivity. Cancellation holds exactly when there are no zero divisors.

  • In ℤn: units are the a with gcd(a, n) = 1, all other non-zero elements are zero divisors, and ℤn is a field ⇔ n is prime. Inverses come from extended Euclid (or ap−2).

  • Every field is an integral domain; every finite integral domain is a field. Characteristic of a field is 0 or prime.

  • Finite fields have exactly pn elements, one for each prime power, built as ℤp[x] mod an irreducible polynomial. GF(28) powers AES and Reed–Solomon.

A ring lets you add, subtract and multiply; a field also lets you divide. Whether you can divide is the single most important question in modular arithmetic, and the answer is: exactly when the modulus is prime (or, for polynomials, irreducible).