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 , and the field, a ring in which division by every nonzero element is possible. It shows that the residue classes of §2, in which this monograph computes, form a ring (4.6), the quotient of by the ideal , and a field exactly when is prime (4.26); it proves that every finite integral domain is a field (4.29) and that the characteristic of a domain is 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 and 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 , multiplicative structure multiplicatively with identity .
A ring is a set equipped with two binary operations and such that:
multiplication is associative:
there is a multiplicative identity 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 , 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 be a ring and
for all integers
(1) From
(2) By distributivity and (1),
(3) Applying (2) twice,
(4) First fix
the final equality being the usual bookkeeping for iterated multiples in an abelian group, which we omit. □
Nothing in 4.1 forces
The integers form the prototype commutative ring; much of ring theory consists of determining which properties of hold in general.
The rationals , the reals , and the complexes are commutative rings, and moreover fields in the sense of §4.4.
The residue classes
The polynomial ring over a commutative ring
consists of the polynomials
The matrix ring of
It is the basic noncommutative example.
The product ring
The zero ring .
Let
are well defined and make a commutative ring with additive identity and multiplicative identity . It has exactly elements.
The right-hand sides are defined in terms of chosen representatives
Every ring axiom is now inherited from the corresponding law of by passing to classes. For instance, distributivity:
using only the definitions and the distributive law of the integers.
Associativity and commutativity of both operations follow by the identical
pattern. The class is an additive identity and a
multiplicative one, since
Finally, by the division algorithm every integer is congruent modulo
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 divide .
An element of a ring is a unit (or is invertible)
if there exists
For any ring , the set of units is a group under the multiplication of , called the group of units (or multiplicative group) of .
The identity is a unit (it is its own inverse), so
and symmetrically
The units of the integers are
In , , and every nonzero element is a unit:
In the matrix ring, is the group of
invertible
A nonzero element of a ring is a left zero
divisor if
The term “cancellable” is justified by the following equivalence.
A nonzero element of a ring is not a left zero divisor if and
only if it is left-cancellable:
Suppose is not a left zero divisor and
A unit is never a zero divisor: if
In ,
In a product ring
In , the diagonal matrices and 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
with
Let
If
The integers form an integral domain, the example from which the
name derives. Every field is a domain
(4.28 below). The ring is a
domain exactly when is prime
(4.15; the composite case is witnessed
concretely by Example 4.13(1)). If is a
domain, so is the polynomial ring : let and be
nonzero of degrees and —the largest indices carrying
nonzero coefficients and , the leading
coefficients. In the coefficient of is
; 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 as a quotient and to indicate the origin of the finite fields ; the general theory belongs to commutative algebra and is omitted.
Let be a commutative ring. An ideal of is a subset
is a subgroup of the additive group
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 contains a unit, so none is a subring: if an
ideal contains a unit , then
In any commutative ring , the subsets and are ideals—the trivial and improper ideals respectively.
For
the set of multiples of ; absorption holds because
For
An integral domain in which every ideal is principal, as in (2), is called a principal ideal domain (PID).
Let be an ideal of a commutative ring . Since is a
subgroup of the abelian group
With the operations of 4.19, the set is
a commutative ring—the quotient ring of by —with zero
Well-definedness is where absorption is needed. Let
and each of , , lies in by the absorption
property; hence
The ring axioms now pass to cosets exactly as in the proof of 4.6. For instance, distributivity reads
and associativity and commutativity of both operations follow by the same
pattern from the corresponding laws in . The coset
Ring homomorphisms, the maps preserving ring structure, make precise the sense in which the quotient construction generalises the passage from to .
A ring homomorphism between rings and is a map
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
is a surjective ring homomorphism with kernel . 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 to (as in the examples above) or drop the decoration altogether, writing plain , whenever the modulus is clear from context; and are used interchangeably; and always means this ring, never the -adic integers (which do not appear in this series).
A field is a commutative ring with
A subset
The unit criterion of §2 identifies the residue rings that are fields.
If is prime, then every nonzero class in is a unit, so is a field; it is denoted . More generally, is a field if and only if is prime.
Let be prime and
The rationals , the reals , and the complexes are fields. The integers are not: has no inverse in .
For prime,
The subset
For any field , the rational functions
Every field is an integral domain.
Let be a field. Commutativity and
Hence has no zero divisors. □
The converse fails: 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 of a finite structure, one shows that multiplication by is injective, hence onto by finiteness, and reads off a preimage of . The same argument proves the claim of 4.12.
Every finite integral domain is a field.
Let be a finite integral domain and
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 , 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 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 inside the ring.
Let be a ring, and for
The map
is a ring homomorphism: additivity is the bookkeeping of iterated
multiples in the abelian group
The rings , , , and all have characteristic :
no positive multiple of vanishes. For the residue rings,
The characteristic of an integral domain—in particular, of a field—is either or a prime number.
Let be an integral domain with
so
Let be a field. If