An arithmetic circuit, the object a verifier checks in a proof system, is a network of gates, each adding or multiplying two previously computed values; inverting a random challenge, or cancelling a common factor from both sides of an identity, requires division as well. This section defines the ring, a set with two operations obeying the arithmetic laws of Z , and the field, a ring in which division by every nonzero element is possible. It shows that the residue classes Z / n Z of §2, in which this monograph computes, form a ring (4.6), the quotient of Z by the ideal n Z , and a field exactly when n is prime (4.26); it proves that every finite integral domain is a field (4.29) and that the characteristic of a domain is 0 or prime (4.32). Polynomials, linear algebra, roots of unity, and elliptic curves are developed over fields in the sections that follow, and the finite fields F p and F q underlie essentially all the elliptic-curve and proof-system constructions of the monograph. From §3 we assume only the theory of abelian groups; additive structure is written additively with identity 0 , multiplicative structure multiplicatively with identity 1 .
A ring is a set R equipped with two binary operations + and ⋅ such that:
multiplication is associative:
there is a multiplicative identity 1 with
multiplication distributes over addition on both sides:
The ring is commutative if moreover
Some authors omit requirement (3), saying “ring with unity” for the notion above and “rng” for the weaker one. In this monograph every ring has a 1 , and the structure-preserving maps between rings—the ring homomorphisms of 4.21 below—are required to preserve it. In the examples used here “ring” usually means “commutative ring”; commutativity is always stated explicitly when a result depends on it.
The distributive law, the only axiom coupling the two operations, yields the following identities, which are used without comment hereafter.
Let R be a ring and
for all integers
(1) From
(2) By distributivity and (1),
(3) Applying (2) twice,
(4) First fix
| (m a) (n b) = m (a (n b)) = m (n (a b)) = (m n) (a b), |
the final equality being the usual bookkeeping for iterated multiples in an abelian group, which we omit. □
Nothing in 4.1 forces
The integers Z form the prototype commutative ring; much of ring theory consists of determining which properties of Z hold in general.
The rationals Q , the reals R , and the complexes C are commutative rings, and moreover fields in the sense of §4.4.
The residue classes
The polynomial ring R [x] over a commutative ring R
consists of the polynomials
The matrix ring M n (R) of
| (0 1 0 0) (0 0 1 0) = (1 0 0 0), but (0 0 1 0) (0 1 0 0) = (0 0 0 1) . |
It is the basic noncommutative example.
The product ring
The zero ring { 0 } .
Let
| [a] n + [b] n := [a + b] n, [a] n ⋅ [b] n := [a b] n |
are well defined and make Z / n Z a commutative ring with additive identity [0] n and multiplicative identity [1] n . It has exactly n elements.
The right-hand sides are defined in terms of chosen representatives
Every ring axiom is now inherited from the corresponding law of Z by passing to classes. For instance, distributivity:
| [a] n ([b] n + [c] n) | = [a] n [b + c] n = [a (b + c)] n = [a b + a c] n | ||
| = [a b] n + [a c] n = [a] n [b] n + [a] n [c] n, |
using only the definitions and the distributive law of the integers.
Associativity and commutativity of both operations follow by the identical
pattern. The class [0] n is an additive identity and [1] n a
multiplicative one, since
Finally, by the division algorithm every integer is congruent modulo n
to exactly one of
Units are the elements by which one can divide, and zero divisors are the obstruction to cancellation, the removal of a nonzero common factor from both sides of an equation. The integers admit cancellation, since a product of nonzero integers is nonzero, but only ± 1 divide 1 .
An element u of a ring R is a unit (or is invertible)
if there exists
For any ring R , the set R × of units is a group under the multiplication of R , called the group of units (or multiplicative group) of R .
The identity 1 is a unit (it is its own inverse), so
| (u w) (w − 1 u − 1) = u (w w − 1) u − 1 = u ⋅ 1 ⋅ u − 1 = 1, |
and symmetrically
The units of the integers are
In Q , R , and C every nonzero element is a unit:
In the matrix ring, M n (R) × is the group of
invertible
A nonzero element a of a ring R is a left zero
divisor if
The term “cancellable” is justified by the following equivalence.
A nonzero element a of a ring R is not a left zero divisor if and
only if it is left-cancellable:
Suppose a is not a left zero divisor and
A unit is never a zero divisor: if
In Z / 6 Z ,
In a product ring
In M 2 (R) , the diagonal matrices diag (1, 0) and diag (0, 1) multiply to the zero matrix; more generally every nonzero singular matrix—the standard name for a square matrix that is not invertible—is a zero divisor there.
An integral domain (or simply domain) is a commutative ring
R with
Let
If
The integers Z form an integral domain, the example from which the
name derives. Every field is a domain
(4.28 below). The ring Z / n Z is a
domain exactly when n is prime
(4.15; the composite case is witnessed
concretely by Example 4.13(1)). If R is a
domain, so is the polynomial ring R [x] : let f and g be
nonzero of degrees m and n —the largest indices carrying
nonzero coefficients f m and g n , the leading
coefficients. In f g the coefficient of x m + n is
∑ i + j = m + n f i g j ; every term with
The ideals of a ring are the subsets by which one can form a quotient preserving both operations, just as any subgroup of an abelian group yields a quotient group (Proposition 3.35). They are needed here to construct Z / n Z as a quotient and to indicate the origin of the finite fields F q ; the general theory belongs to commutative algebra and is omitted.
Let R be a commutative ring. An ideal of R is a subset
I is a subgroup of the additive group
I absorbs multiplication by arbitrary ring elements:
In noncommutative rings one distinguishes left, right, and two-sided ideals according to the side on which absorption holds; commutative rings suffice for this volume, and there the three notions coincide.
No ideal other than R contains a unit, so none is a subring: if an
ideal I contains a unit u , then
In any commutative ring R , the subsets { 0 } and R are ideals—the trivial and improper ideals respectively.
For
| (a) := a R = { a r : r ∈ R }, |
the set of multiples of a ; absorption holds because
For
An integral domain in which every ideal is principal, as in (2), is called a principal ideal domain (PID).
Let I be an ideal of a commutative ring R . Since I is a
subgroup of the abelian group
| (a + I) (b + I) := a b + I . |
With the operations of 4.19, the set R / I is
a commutative ring—the quotient ring of R by I —with zero
Well-definedness is where absorption is needed. Let
| a ′ b ′ = (a + s) (b + t) = a b + a t + s b + s t, |
and each of a t , s b , s t lies in I by the absorption
property; hence
The ring axioms now pass to cosets exactly as in the proof of 4.6. For instance, distributivity reads
| (a + I) ((b + I) + (c + I)) | = (a + I) ((b + c) + I) = a (b + c) + I | ||
| = (a b + a c) + I = (a + I) (b + I) + (a + I) (c + I), |
and associativity and commutativity of both operations follow by the same
pattern from the corresponding laws in R . The coset
Ring homomorphisms, the maps preserving ring structure, make precise the sense in which the quotient construction generalises the passage from Z to Z / n Z .
A ring homomorphism between rings R and S is a map
| φ (a + b) = φ (a) + φ (b), φ (a b) = φ (a) φ (b), φ (1) = 1 |
for all
The kernel of a ring homomorphism out of a commutative ring is always an
ideal: it is a subgroup of
Take
The quotient map
| π : Z → Z / n Z, π (a) = [a] n, |
is a surjective ring homomorphism with kernel n Z . Every quotient construction in the volume’s algebra follows this pattern: one chooses a ring and an ideal of elements to be “declared zero”, and computes with cosets. On notation: we abbreviate [a] n to a ̄ (as in the examples above) or drop the decoration altogether, writing plain a , whenever the modulus is clear from context; Z / n Z and Z n are used interchangeably; and Z n always means this ring, never the n -adic integers (which do not appear in this series).
A field is a commutative ring F with
A subset
The unit criterion of §2 identifies the residue rings that are fields.
If p is prime, then every nonzero class in Z / p Z is a unit, so Z / p Z is a field; it is denoted F p . More generally, Z / n Z is a field if and only if n is prime.
Let p be prime and
The rationals Q , the reals R , and the complexes C are fields. The integers are not: 2 has no inverse in Z .
For p prime,
The subset
For any field F , the rational functions
Every field is an integral domain.
Let F be a field. Commutativity and
| b = 1 ⋅ b = (a − 1 a) b = a − 1 (a b) = a − 1 ⋅ 0 = 0 . |
Hence F has no zero divisors. □
The converse fails: Z is a domain but not a field (Example 4.16). For finite domains the converse holds, by a counting argument that recurs, the injectivity-implies-surjectivity argument: to invert an element a of a finite structure, one shows that multiplication by a is injective, hence onto by finiteness, and reads off a preimage of 1 . The same argument proves the claim of 4.12.
Every finite integral domain is a field.
Let R be a finite integral domain and
| μ a : R → R, μ a (x) = a x . |
It is injective: if
With 4.28, the theorem shows that a nonzero finite commutative ring is a field exactly when it has no zero divisors. Applied to Z / p Z , a finite domain by 4.15, it recovers 4.26, but establishes only that each inverse exists; the extended Euclidean algorithm of §2 computes it, in O (log p) division steps. Cryptography uses the existence statement in proofs and the algorithm in computation.
Every ring receives a canonical map from the integers; the characteristic, an invariant of the ring, describes that map and determines the image of Z inside the ring.
Let R be a ring, and for
The map
| ι : Z → R, ι (n) = n ⋅ 1, |
is a ring homomorphism: additivity is the bookkeeping of iterated
multiples in the abelian group
The rings Z , Q , R , and C all have characteristic 0 :
no positive multiple of 1 vanishes. For the residue rings,
The characteristic of an integral domain—in particular, of a field—is either 0 or a prime number.
Let R be an integral domain with
| 0 = n ⋅ 1 = (a b) (1 ⋅ 1) = (a ⋅ 1) (b ⋅ 1), |
so
Let F be a field. If