The Zcash ArboretumI Math Guide
Contents
PDF
Theme

4 Rings and fields

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 ℤ/nℤ of §2, in which this monograph computes, form a ring (4.6), the quotient of ℤ by the ideal nℤ, 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 𝔽p and 𝔽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.

4.1 Rings

Definition 4.1 (Ring).

A ring is a set R equipped with two binary operations + and ⋅ such that:

  1. 1.

    (R,+) is an abelian group: addition is associative and commutative, there is an element 0 with a+0=a for all a, and every a has an additive inverse −a with a+(−a)=0;

  2. 2.

    multiplication is associative: a⋅(b⋅c)=(a⋅b)⋅c;

  3. 3.

    there is a multiplicative identity 1 with 1⋅a=a⋅1=a for all a;

  4. 4.

    multiplication distributes over addition on both sides: a⋅(b+c)=a⋅b+a⋅c and (a+b)⋅c=a⋅c+b⋅c.

The ring is commutative if moreover a⋅b=b⋅a for all a,b∈R. We write ab for a⋅b, let multiplication bind tighter than addition, and call 0 the zero and 1 the unity of the ring.

Remark 4.2.

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.

Proposition 4.3 (Elementary ring arithmetic).

Let R be a ring and a,b∈R. Then:

  1. 1.

    0⋅a=a⋅0=0;

  2. 2.

    (−a)b=a(−b)=−(ab);

  3. 3.

    (−a)(−b)=ab;

  4. 4.

    for all integers m,n∈ℤ, (ma)(nb)=(mn)(ab), where na denotes the n-fold additive multiple (0a=0, (n+1)a=na+a, and (−n)a=−(na), as for any abelian group, §3).

Proof.

(1) From 0=0+0 and distributivity, 0⋅a=(0+0)⋅a=0⋅a+0⋅a; adding −(0⋅a) to both sides leaves 0=0⋅a. The computation for a⋅0 is symmetric.

(2) By distributivity and (1), ab+(−a)b=(a+(−a))b=0⋅b=0, so (−a)b is the additive inverse of ab, that is, (−a)b=−(ab); likewise ab+a(−b)=a(b+(−b))=0 gives a(−b)=−(ab).

(3) Applying (2) twice, (−a)(−b)=−(a(−b))=−(−(ab))=ab, the last step because negation is an involution in the abelian group (R,+).

(4) First fix a,b and show a(nb)=n(ab) for n≥0 by induction: the case n=0 is (1), and a((n+1)b)=a(nb+b)=a(nb)+ab=n(ab)+ab=(n+1)(ab) by distributivity and the inductive hypothesis. For n<0 write n=−m with m>0; then a(nb)=a(−(mb))=−(a(mb))=−(m(ab))=n(ab) by (2). The same argument in the first factor gives (ma)c=m(ac) for all c, and combining,

(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. □

Remark 4.4 (The zero ring).

Nothing in 4.1 forces 1≠0. If 1=0 in a ring R, then every a∈R satisfies a=1⋅a=0⋅a=0 by 4.3(1), so R={0}: the zero ring (or trivial ring), a ring whose two operations are the only possible ones. Whenever the zero ring must be excluded we impose the assumption 1≠0 explicitly; the definition of a field below builds 1≠0 in as a standing assumption.

Example 4.5 (Basic rings).
  1. 1.

    The integers ℤ form the prototype commutative ring; much of ring theory consists of determining which properties of ℤ hold in general.

  2. 2.

    The rationals ℚ, the reals ℝ, and the complexes ℂ are commutative rings, and moreover fields in the sense of §4.4.

  3. 3.

    The residue classes ℤ/nℤ={0¯,1¯,…,n−1¯} for n≥1—in this section’s examples we abbreviate the class [a]n of Definition 2.22 to a¯ when the modulus is clear—under the induced operations form a commutative ring whose additive group is the cyclic group of order n (§3); this is 4.6 below. We write ℤ/nℤ, or ℤn when no ambiguity arises. The case n=1 gives the zero ring of 4.4.

  4. 4.

    The polynomial ring R[x] over a commutative ring R consists of the polynomials a0+a1x+⋯+adxd with coefficients ai∈R, added coefficient-wise and multiplied by expanding and collecting powers of x; it is a commutative ring with the same 0 and 1 as R (the constant polynomials). The theory of polynomials over a field is developed in its own section later in the volume.

  5. 5.

    The matrix ring Mn(R) of n×n matrices over a commutative ring R, n≥1, is a ring under matrix addition and multiplication. It is not commutative for n≥2 and R≠{0}, even when R is commutative: in M2(ℤ),

    (0100)⁢(0010)=(1000),but(0010)⁢(0100)=(0001).

    It is the basic noncommutative example.

  6. 6.

    The product ring R×S of two rings carries the componentwise operations, with zero (0,0) and identity (1,1); likewise any finite product R1×⋯×Rk.

  7. 7.

    The zero ring {0}.

Theorem 4.6.

Let n≥1. The operations

[a]n+[b]n:=[a+b]n,[a]n⋅[b]n:=[a⁢b]n

are well defined and make ℤ/nℤ a commutative ring with additive identity [0]n and multiplicative identity [1]n. It has exactly n elements.

Proof.

The right-hand sides are defined in terms of chosen representatives a,b, so we must check that different choices give the same class. This is exactly the compatibility half of Proposition 2.21: if a′≡a and b′≡b(modn), then a′+b′≡a+b and a′b′≡ab(modn), so [a′+b′]n=[a+b]n and [a′⁢b′]n=[a⁢b]n. The operations are therefore well defined on classes.

Every ring axiom is now inherited from the corresponding law of ℤ 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 [a+0]n=[a]n and [1⋅a]n=[a]n; and −[a]n=[−a]n because [a]n+[−a]n=[a+(−a)]n=[0]n.

Finally, by the division algorithm every integer is congruent modulo n to exactly one of 0,1,…,n−1 (the least nonnegative residues, Definition 2.22 and the discussion following it), so the classes [0]n,…,[n−1]n are distinct and exhaust ℤ/nℤ: the ring has exactly n elements. □

4.2 Units, zero divisors, and integral domains

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.

Definition 4.7 (Unit).

An element u of a ring R is a unit (or is invertible) if there exists v∈R with uv=vu=1. Such a v is unique: if uv=vu=1 and uv′=v′u=1, then v=v⋅1=v(uv′)=(vu)v′=1⋅v′=v′. It is called the inverse of u and written u−1. The set of units of R is denoted R×.

Proposition 4.8.

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.

Proof.

The identity 1 is a unit (it is its own inverse), so 1∈R×. For closure, let u,w∈R×; then

(u⁢w)⁢(w−1⁢u−1)=u⁢(w⁢w−1)⁢u−1=u⋅1⋅u−1=1,

and symmetrically (w−1u−1)(uw)=1, so uw is a unit with (u⁢w)−1=w−1u−1. Multiplication in R× is associative because it is associative in R. Finally each u−1 is itself a unit, its inverse being u; so every element of R× has an inverse in R×, and the group axioms are verified. □

Example 4.9 (Units).
  1. 1.

    The units of the integers are ℤ×={1,−1}: if uv=1 in ℤ then |u||v|=1 forces |u|=1.

  2. 2.

    In ℚ, ℝ, and ℂ every nonzero element is a unit: ℚ×=ℚ∖{0}, ℝ×=ℝ∖{0}, ℂ×=ℂ∖{0}. Commutative rings with 1≠0 in which every nonzero element is a unit are precisely the fields of §4.4; this is their defining feature. Both qualifiers are needed: the zero ring of 4.4 satisfies the unit condition vacuously, and noncommutative rings satisfying it—the division rings—exist but are not fields.

  3. 3.

    In ℤ/nℤ, the class a¯ is a unit if and only if gcd(a,n)=1, by Theorem 2.24; thus (ℤ/n⁢ℤ)× consists of the residue classes coprime to the modulus, and its order is Euler’s totient φ(n) (Definition 2.26).

  4. 4.

    In the matrix ring, Mn(R)× is the group of invertible n×n matrices. Over a field it is the general linear group GLn.

Definition 4.10 (Zero divisor).

A nonzero element a of a ring R is a left zero divisor if ab=0 for some nonzero b∈R, and a right zero divisor if ba=0 for some nonzero b. In a commutative ring the two notions coincide and we say zero divisor. A nonzero element that is neither is called regular (or cancellable).

The term “cancellable” is justified by the following equivalence.

Proposition 4.11.

A nonzero element a of a ring R is not a left zero divisor if and only if it is left-cancellable: ab=ac implies b=c for all b,c∈R.

Proof.

Suppose a is not a left zero divisor and ab=ac. Then a(b−c)=ab−ac=0, using 4.3(2) to expand a(b+(−c)); since a is nonzero and not a left zero divisor, the factor b−c must be 0, so b=c. Conversely, suppose a is a left zero divisor, say ab=0 with b≠0. Then ab=0=a⋅0 while b≠0: cancellation fails. □

Remark 4.12.

A unit is never a zero divisor: if u∈R× and ub=0, then b=1⋅b=(u−1u)b=u−1(ub)=u−1⋅0=0. The converse fails in general—in ℤ every nonzero element is a non-zero-divisor, yet only ±1 are units—but every nonzero non-zero-divisor is a unit in a finite commutative ring, by the injectivity-implies-surjectivity argument that proves 4.29 below.

Example 4.13 (Zero divisors).
  1. 1.

    In ℤ/6ℤ, 2¯⋅3¯=6¯=0¯, so 2¯ and 3¯ are zero divisors. In general a nonzero class a¯∈ℤ/nℤ is a zero divisor precisely when d:=gcd(a,n)>1: in that case a⋅(n/d)=(a/d)⋅n≡0(modn) while n/d¯≠0¯ (as 0<n/d<n); and when d=1 the class is a unit (Example 4.9(3)), hence no zero divisor by 4.12. Thus in ℤ/nℤ every nonzero element is either a unit or a zero divisor, a dichotomy revisited structurally by 4.29.

  2. 2.

    In a product ring R×S with both factors nonzero, (1,0)(0,1)=(0,0): product rings always have zero divisors.

  3. 3.

    In M2(ℝ), 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.

Definition 4.14 (Integral domain).

An integral domain (or simply domain) is a commutative ring R with 1≠0 and no zero divisors: ab=0 implies a=0 or b=0. Equivalently, by 4.11, a domain is a nonzero commutative ring in which every nonzero element is cancellable.

Proposition 4.15.

Let n≥2. The ring ℤ/nℤ has no zero divisors if and only if n is prime; that is, ℤ/nℤ is an integral domain if and only if n is prime.

Proof.

If n=ab is composite with 1<a,b<n, then [a]n[b]n=[n]n=[0]n with both factors nonzero (their representatives lie strictly between 0 and n), so ℤ/nℤ has zero divisors. Conversely let n=p be prime and suppose [a]p[b]p=[0]p, that is, p∣ab. Euclid’s lemma for primes (Lemma 2.17) gives p∣a or p∣b, that is, [a]p=[0]p or [b]p=[0]p. Since p≥2 we also have [1]p≠[0]p, so ℤ/pℤ is an integral domain. □

Example 4.16 (Integral domains).

The integers ℤ form an integral domain, the example from which the name derives. Every field is a domain (4.28 below). The ring ℤ/nℤ 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 fm and gn, the leading coefficients. In fg the coefficient of xm+n is ∑i+j=m+nfigj; every term with i>m or j>n has a vanishing factor, and i≤m, j≤n, i+j=m+n force i=m, j=n, so the coefficient equals fmgn, nonzero because R is a domain. Hence fg≠0. Non-domains include ℤ/6ℤ, product rings with two nonzero factors, and the matrix rings Mn(R) for n≥2 (Example 4.13).

4.3 Ideals and quotient rings

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 ℤ/nℤ as a quotient and to indicate the origin of the finite fields 𝔽q; the general theory belongs to commutative algebra and is omitted.

Definition 4.17 (Ideal).

Let R be a commutative ring. An ideal of R is a subset I⊆R such that

  1. 1.

    I is a subgroup of the additive group (R,+): 0∈I, and a−b∈I whenever a,b∈I; and

  2. 2.

    I absorbs multiplication by arbitrary ring elements: ra∈I whenever r∈R and a∈I.

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 1=u−1u∈I by absorption, so r=r⋅1∈I for every r∈R and I=R. Consequently a field has no ideals other than the two trivial ones, and hence no quotients other than a copy of itself and the zero ring.

Example 4.18 (Ideals).
  1. 1.

    In any commutative ring R, the subsets {0} and R are ideals—the trivial and improper ideals respectively.

  2. 2.

    For a∈R, the principal ideal generated by a is

    (a):=a⁢R={a⁢r:r∈R},

    the set of multiples of a; absorption holds because r′(ar)=a(r′r). In ℤ, the principal ideal (n)=nℤ is the set of multiples of n. Moreover every ideal of ℤ is principal: an ideal I≠{0} contains a nonzero element and hence (closing under negation) a positive one, so it contains a least positive element n by well-ordering; for any a∈I the division algorithm gives a=qn+r with 0≤r<n, whence r=a−qn∈I by absorption and subgroup closure, forcing r=0 by minimality; so I=nℤ. This sharpens the observation of Remark 2.12, where ideals of ℤ first appeared as the sets of Bézout combinations.

  3. 3.

    For a1,…,ak∈R, the ideal generated by a1,…,ak is (a1,…,ak)={r1a1+⋯+rkak:ri∈R}, the smallest ideal containing them all.

An integral domain in which every ideal is principal, as in (2), is called a principal ideal domain (PID).

Definition 4.19 (Quotient ring operations).

Let I be an ideal of a commutative ring R. Since I is a subgroup of the abelian group (R,+), the additive cosets a+I form the quotient group R/I under coset addition (a+I)+(b+I)=(a+b)+I (Proposition 3.35). Define a multiplication of cosets by

(a+I)⁢(b+I):=a⁢b+I.
Proposition 4.20.

With the operations of 4.19, the set R/I is a commutative ring—the quotient ring of R by I—with zero 0+I=I and identity 1+I. In particular the coset multiplication is well defined.

Proof.

Well-definedness is where absorption is needed. Let a′=a+s and b′=b+t be other representatives of the same cosets, with s,t∈I. Then

a′⁢b′=(a+s)⁢(b+t)=a⁢b+a⁢t+s⁢b+s⁢t,

and each of at, sb, st lies in I by the absorption property; hence a′b′−ab∈I and a′b′+I=ab+I. The product coset is therefore independent of the representatives chosen.

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 I=0+I is the additive identity, 1+I the multiplicative identity, and −(a+I)=(−a)+I. □

Ring homomorphisms, the maps preserving ring structure, make precise the sense in which the quotient construction generalises the passage from ℤ to ℤ/nℤ.

Definition 4.21 (Ring homomorphism).

A ring homomorphism between rings R and S is a map ϕ:R→S with

ϕ⁢(a+b)=ϕ⁢(a)+ϕ⁢(b),ϕ⁢(a⁢b)=ϕ⁢(a)⁢ϕ⁢(b),ϕ⁢(1)=1

for all a,b∈R. Its kernel is kerϕ={a∈R:ϕ(a)=0}.

The kernel of a ring homomorphism out of a commutative ring is always an ideal: it is a subgroup of (R,+) because ϕ is in particular a homomorphism of additive groups, and it absorbs because a∈kerϕ gives ϕ(ra)=ϕ(r)ϕ(a)=ϕ(r)⋅0=0.

Example 4.22.

Take R=ℤ and I=nℤ. The cosets a+nℤ are literally the residue classes [a]n of Definition 2.22, and the coset operations of 4.19 are exactly residue arithmetic: the quotient construction recovers the ring ℤ/nℤ of Example 4.5(3), so modular arithmetic is an instance of it. The same construction with a different ring produces the general finite fields: quotients 𝔽p[x]/(f) of a polynomial ring by the principal ideal of an irreducible polynomial f of degree k—irreducibility, the polynomial analogue of primality, is defined in §5—furnish the finite fields 𝔽q with q=pk elements. The construction is recorded here and developed in §6; the curves of Halo 2 and Orchard are defined over prime fields, so the prime case 𝔽p=ℤ/pℤ is the main case in what follows.

Remark 4.23.

The quotient map

π:ℤ→ℤ/n⁢ℤ,π⁢(a)=[a]n,

is a surjective ring homomorphism with kernel nℤ. 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; ℤ/nℤ and ℤn are used interchangeably; and ℤn always means this ring, never the n-adic integers (which do not appear in this series).

4.4 Fields

Definition 4.24 (Field).

A field is a commutative ring F with 1≠0 in which every nonzero element is a unit. Equivalently, a field is a set F with two operations + and ⋅ such that (F,+) is an abelian group with identity 0, the nonzero elements (F∖{0},⋅) form an abelian group with identity 1, and multiplication distributes over addition. Concretely, in a field one may add, subtract, multiply, and divide by any nonzero element, with a/b:=ab−1. The group F×=(F∖{0},⋅) is the multiplicative group of the field. (Two steps of the equivalence require an argument. Passing from the first formulation to the second, one must show F∖{0} is closed under multiplication; that is 4.28 below. Passing back, the ring axioms must be checked for products involving 0: distributivity forces 0⋅a=a⋅0=0 by the computation of 4.3(1), whereupon every product with a zero factor vanishes and the associativity, commutativity, and identity laws extend from F∖{0} to all of F; and 1≠0 holds because the group F∖{0} contains its identity 1.)

Definition 4.25 (Subfield and extension field).

A subset F⊆K of a field K is a subfield when it contains 0 and 1 and is itself a field under the operations of K restricted to F. When F is a subfield of K, the larger field K is called an extension field (or simply an extension) of F; the two phrases name the same relation. More generally, an injective ring homomorphism F↪K between fields exhibits K as an extension of the copy of F inside it; by the usual abuse of language we identify F with that copy.

The unit criterion of §2 identifies the residue rings that are fields.

Corollary 4.26.

If p is prime, then every nonzero class in ℤ/pℤ is a unit, so ℤ/pℤ is a field; it is denoted 𝔽p. More generally, ℤ/nℤ is a field if and only if n is prime.

Proof.

Let p be prime and [a]p≠[0]p, so that p∤a. The only positive divisors of p are 1 and p, so gcd(a,p)=1, and Theorem 2.24 makes [a]p a unit. Since [1]p≠[0]p for p≥2, the ring ℤ/pℤ is a field. Conversely, if n=ab is composite with 1<a,b<n, then [a]n≠[0]n but gcd(a,n)=a>1, so [a]n is not a unit (Theorem 2.24 again) and the ring is not a field; and n=1 gives the zero ring, which is not a field because a field has 1≠0 by definition. □

Example 4.27 (Fields).
  1. 1.

    The rationals ℚ, the reals ℝ, and the complexes ℂ are fields. The integers are not: 2 has no inverse in ℤ.

  2. 2.

    For p prime, 𝔽p:=ℤ/pℤ is a field (4.26; 4.29 below recovers the same fact abstractly). It is called the prime field of characteristic p—4.30 names the invariant—and underlies every later cryptographic construction in the series. Its finite extensions 𝔽q with q=pk elements exist for every prime power, arising from the quotient construction of Example 4.22, and are developed in §6.

  3. 3.

    The subset ℚ(i)={a+bi:a,b∈ℚ}⊆ℂ is a field: the inverse of a nonzero a+bi is (a−bi)/(a2+b2), which again has rational coordinates. More generally the number fields, obtained by adjoining to ℚ roots of polynomial equations with rational coefficients, are fields.

  4. 4.

    For any field F, the rational functions F(x)={f/g:f,g∈F[x],g≠0} form a field under the usual arithmetic of fractions—the field of fractions of the polynomial ring F[x].

Proposition 4.28.

Every field is an integral domain.

Proof.

Let F be a field. Commutativity and 1≠0 hold by definition. Suppose ab=0 with a≠0. Then a is a unit, and multiplying by its inverse,

b=1⋅b=(a−1⁢a)⁢b=a−1⁢(a⁢b)=a−1⋅0=0.

Hence F 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 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.

Theorem 4.29.

Every finite integral domain is a field.

Proof.

Let R be a finite integral domain and a∈R nonzero. Consider the multiplication map

μa:R→R,μa⁢(x)=a⁢x.

It is injective: if ax=ay, then a(x−y)=0, and since R is a domain and a≠0 this forces x−y=0, that is, x=y (equivalently, a is cancellable by 4.11). An injective map from a finite set to itself is surjective: the image μa(R) has |R| distinct elements and sits inside R, so it is all of R. In particular 1 lies in the image, so ab=1 for some b∈R; commutativity gives ba=1 as well, so b=a−1 and a is a unit. Since R is a domain, 1≠0, and every nonzero element has been shown invertible: R is a field. □

With 4.28, the theorem shows that a nonzero finite commutative ring is a field exactly when it has no zero divisors. Applied to ℤ/pℤ, 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(logp) division steps. Cryptography uses the existence statement in proofs and the algorithm in computation.

4.5 The characteristic

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.

Definition 4.30 (Characteristic).

Let R be a ring, and for n∈ℤ let n⋅1 denote the n-fold additive multiple of 1 (so n⋅1=1+⋯+1 with n summands for n>0, 0⋅1=0, and (−n)⋅1=−(n⋅1)). The characteristic char(R) is the least positive integer n with n⋅1=0, if such an n exists, and 0 otherwise.

The map

ι:ℤ→R,ι⁢(n)=n⋅1,

is a ring homomorphism: additivity is the bookkeeping of iterated multiples in the abelian group (R,+), multiplicativity is 4.3(4) with a=b=1—namely ι(m)ι(n)=(m⋅1)(n⋅1)=(mn)(1⋅1)=ι(mn)—and ι(1)=1. Its kernel is an ideal of ℤ, hence of the form nℤ for a unique n≥0 by Example 4.18(2), and char(R) is exactly this nonnegative generator: char(R)=0 precisely when ι is injective, so that a faithful copy of ℤ sits inside R, and char(R)=n>0 when the kernel is nℤ.

Example 4.31 (Characteristics).

The rings ℤ, ℚ, ℝ, and ℂ all have characteristic 0: no positive multiple of 1 vanishes. For the residue rings, char(ℤ/nℤ)=n: the multiple n⋅1¯=n¯=0¯ vanishes, and no smaller positive multiple does, since k⋅1¯=k¯≠0¯ for 0<k<n. In particular char(𝔽p)=p.

Theorem 4.32.

The characteristic of an integral domain—in particular, of a field—is either 0 or a prime number.

Proof.

Let R be an integral domain with char(R)=n>0; we show n is prime. First n≠1: otherwise 1⋅1=1=0, making R the zero ring (4.4) and contradicting 1≠0 in a domain. Suppose n=ab with 1<a,b<n. By 4.3(4),

0=n⋅1=(a⁢b)⁢(1⋅1)=(a⋅1)⁢(b⋅1),

so a⋅1=0 or b⋅1=0 since R is a domain. Either case exhibits a positive integer smaller than n whose multiple of 1 vanishes, contradicting the minimality of n=char(R). Hence n admits no such factorisation, and being greater than 1, it is prime. □

Remark 4.33 (The prime subfield).

Let F be a field. If char(F)=0, the homomorphism ι embeds a copy of ℤ in F, and dividing—possible in a field—a copy of ℚ as well. If char(F)=p, the image of ι is a copy of 𝔽p=ℤ/pℤ. The smallest subfield so obtained is called the prime subfield of F; every field is thus an extension of ℚ or of some 𝔽p. The fields 𝔽q underlying the cryptography treated in this series all have prime characteristic p. In characteristic p the “freshman’s dream” identity (a+b)p=ap+bp holds and gives rise to the Frobenius endomorphism; both are developed in the finite-fields section (6.14).