uniquely as b(·) for some b ∈ R[X] of degree less than , and more generally,

for arbitrary a, b ∈ R[X], we have a(·) = b(·) if and only if a ≡ b (mod f ).

2

Example 9.44. As a special case of Example 9.43, let f := X2 + 1 ∈ R[X],

and consider the quotient ring R[X]/(f ). If we set i := [X]f ∈ R[X]/(f ), then

every element of R[X]/(f ) can be expressed uniquely as a+bi, where a, b ∈ R.

Moreover, we have i2 = ’1, and more generally, for a, b, a , b ∈ R, we have

(a + bi) + (a + b i) = (a + a ) + (b + b )i

and

(a + bi) · (a + b i) = (aa ’ bb ) + (ab + a b)i.

Thus, the rules for arithmetic in R[X]/(f ) are precisely the familiar rules of

complex arithmetic, and so C and R[X]/(f ) are essentially the same, as rings.

Indeed, the “algebraically correct” way of de¬ning the complex numbers C

is simply to de¬ne them to be the quotient ring R[X]/(f ) in the ¬rst place.

This will be our point of view from now on. 2

Example 9.45. Consider the polynomial evaluation map ρ : R[X] ’ C =

R[X]/(X2 + 1) that sends g ∈ R[X] to g(’i). For any g ∈ R[X], we may write

g = (X2 + 1)q + a + bX, where q ∈ R[X] and a, b ∈ R. Since (’i)2 + 1 =

i2 + 1 = 0, we have g(’i) = ((’i)2 + 1)q(’i) + a ’ bi = a ’ bi. Clearly,

then, ρ is surjective and the kernel of ρ is the ideal of R[X] generated by the

polynomial X2 + 1. By Theorem 9.26, we therefore get a ring automorphism

ρ on C that sends a + bi ∈ C to a ’ bi. In fact, ρ it is none other than the

¯ ¯

complex conjugation map. Indeed, this is the “algebraically correct” way of

de¬ning complex conjugation in the ¬rst place. 2

Example 9.46. We de¬ned the ring Z[i] of Gaussian integers in Exam-

ple 9.22 as a subring of C. Let us verify that the notation Z[i] introduced in

Example 9.22 is consistent with that introduced in Example 9.39. Consider

the polynomial evaluation map ρ : Z[X] ’ C that sends g ∈ Z[X] to g(i) ∈ C.

9.4 Ring homomorphisms and isomorphisms 241

For any g ∈ Z[X], we may write g = (X2 + 1)q + a + bX, where q ∈ Z[X] and

a, b ∈ Z. Since i2 + 1 = 0, we have g(i) = (i2 + 1)q(i) + a + bi = a + bi.

Clearly, then, the image of ρ is the set {a + bi : a, b ∈ Z}, and the kernel of

ρ is the ideal of Z[X] generated by the polynomial X2 + 1. This shows that

Z[i] in Example 9.22 is the same as Z[i] in Example 9.39, and moreover,

Theorem 9.26 implies that Z[i] is isomorphic to Z[X]/(X2 + 1).

Thus, we can directly construct the Gaussian integers as the quotient ring

Z[X]/(X2 + 1). Likewise the ¬eld Q[i] (see Exercise 9.8) can be constructed

directly as Q[X]/(X2 + 1). Such direct constructions are appealing in that

they are purely “elementary,” as they do not appeal to anything so “sophis-

ticated” as the real numbers. 2

Example 9.47. Let p be a prime, and consider the quotient ring E :=

Zp [X]/(X2 + 1). If we set i := [X]X2 +1 ∈ E, then E = Zp [i] = {a + bi : a, b ∈

Zp }. In particular, E is a ring of cardinality p2 . Moreover, the rules for

addition and multiplication in E look exactly the same as they do in C: for

a, b, a , b ∈ Zp , we have

(a + bi) + (a + b i) = (a + a ) + (b + b )i

and

(a + bi) · (a + b i) = (aa ’ bb ) + (ab + a b)i.

Note that E may or may not be a ¬eld.

On the one hand, suppose that c2 = ’1 for some c ∈ Zp (for example,

p = 2, p = 5, p = 13). Then (c + i)(c ’ i) = c2 + 1 = 0, and so E is not an

integral domain.

On the other hand, suppose there is no c ∈ Zp such that c2 = ’1 (for

example, p = 3, p = 7). Then for any a, b ∈ Zp , not both zero, we must have

a2 + b2 = 0; indeed, suppose that a2 + b2 = 0, and that, say, b = 0; then

we would have (a/b)2 = ’1, contradicting the assumption that ’1 has no

square root in Zp . Since Zp is a ¬eld, it follows that the same formula for

multiplicative inverses in C applies in E, namely,

a ’ bi

(a + bi)’1 = .

a2 + b2

This construction provides us with more examples of ¬nite ¬elds whose

cardinality is not prime. 2

Example 9.48. If ρ : R ’ R is a ring homomorphism, then we can extend

ρ in a natural way to a ring homomorphism from R[X] to R [X], by de¬ning

ρ( i ai Xi ) := i ρ(ai )Xi . We leave it to the reader to verify that this indeed

is a ring homomorphism. 2

242 Rings

Exercise 9.34. Verify that the “is isomorphic to” relation on rings is an

equivalence relation; that is, for all rings R1 , R2 , R3 , we have:

(a) R1 ∼ R1 ;

=

(b) R1 ∼ R2 implies R2 ∼ R1 ;

= =

(c) R1 ∼ R2 and R2 ∼ R3 implies R1 ∼ R3 .

= = =

Exercise 9.35. Let R1 , R2 be rings, and let ρ : R1 — R2 ’ R1 be the map

that sends (a1 , a2 ) ∈ R1 — R2 to a1 ∈ R1 . Show that ρ is a surjective ring

homomorphism whose kernel is {0R1 } — R2 .

Exercise 9.36. Let ρ be a ring homomorphism from R into R . Show that

the ideals of R containing ker(ρ) are in one-to-one correspondence with the

ideals of img(ρ), where the ideal I of R containing ker(ρ) corresponds to the

ideal ρ(I) of img(ρ).

Exercise 9.37. Let ρ : R ’ S be a ring homomorphism. Show that

ρ(R— ) ⊆ S — , and that the restriction of ρ to R— yields a group homomorphism

ρ— : R— ’ S — whose kernel is (1R + ker(ρ)) © R— .

Exercise 9.38. Show that if F is a ¬eld, then the only ideals of F are {0F }

and F . From this, conclude the following: if ρ : F ’ R is a ring homomor-

phism from F into a non-trivial ring R, then ρ must be an embedding.

Exercise 9.39. Let n be a positive integer.

(a) Show that the rings Z[X]/(n) and Zn [X] are isomorphic.

(b) Assuming that n = pq, where p and q are distinct primes, show that

the rings Zn [X] and Zp [X] — Zq [X] are isomorphic.

Exercise 9.40. Let n be a positive integer, let f ∈ Z[X] be a monic poly-

¯ ¯

nomial, and let f be the image of f in Zn [X] (i.e., f is obtained by applying

the natural map from Z to Zn coe¬cient-wise to f ). Show that the rings

¯

Z[X]/(n, f ) and Zn [X]/(f ) are isomorphic.

Exercise 9.41. Let R be a ring, and let ±1 , . . . , ±n be elements of R. Show

that the rings R and R[X1 , . . . , Xn ]/(X1 ’ ±1 , . . . , Xn ’ ±n ) are isomorphic.

Exercise 9.42. Let ρ : R ’ R be a ring homomorphism, and suppose

that we extend ρ, as in Example 9.48, to a ring homomorphism from R[X]

to R [X]. Show that for any a ∈ R[X], we have D(ρ(a)) = ρ(D(a)), where

D(·) denotes the formal derivative.

Exercise 9.43. This exercise and the next generalize the Chinese remainder

theorem to arbitrary rings. Suppose I and J are two ideals of a ring R such

9.4 Ring homomorphisms and isomorphisms 243

that I + J = R. Show that the map ρ : R ’ R/I — R/J that sends a ∈ R

to ([a]I , [a]J ) is a surjective ring homomorphism with kernel I · J. Conclude

that R/(I · J) is isomorphic to R/I — R/J.

Exercise 9.44. Generalize the previous exercise, showing that R/(I1 · · · Ik )

is isomorphic to R/I1 — · · · — R/Ik , where R is a ring, and I1 , . . . , Ik are

ideals of R, provided Ii + Ij = R for all i, j such that i = j.

Exercise 9.45. Let F be a ¬eld and let d be an element of F that is not a

perfect square (i.e., there does not exist e ∈ F such that e2 = d). Let E :=

F [X]/(X2 ’ d), and let · := [X]X2 ’d , so that E = F [·] = {a + b· : a, b ∈ F }.

(a) Show that the quotient ring E is a ¬eld, and write down the formula

for the inverse of a + b· ∈ E.

(b) Show that the map that sends a + b· ∈ E to a ’ b· is a ring auto-

morphism on E.

Exercise 9.46. Let Q(m) be the subring of Q de¬ned in Example 9.23. Let

us de¬ne the map ρ : Q(m) ’ Zm as follows. For a/b ∈ Q with b relatively

prime to m, ρ(a/b) := [a]m ([b]m )’1 . Show that ρ is unambiguously de¬ned,

and is a surjective ring homomorphism. Also, describe the kernel of ρ.

Exercise 9.47. Let ρ : R ’ R be a map from a ring R to a ring R that

satis¬es all the requirements of a ring homomorphism, except that we do

not require that ρ(1R ) = 1R .

(a) Give a concrete example of such a map ρ, such that ρ(1R ) = 1R and

ρ(1R ) = 0R .

(b) Show that img(ρ) is a ring in which ρ(1R ) plays the role of the mul-

tiplicative identity.

(c) Show that if R is an integral domain, and ρ(1R ) = 0R , then ρ(1R ) =

1R , and hence ρ satis¬es our de¬nition of a ring homomorphism.

(d) Show that if ρ is surjective, then ρ(1R ) = 1R , and hence ρ satis¬es

our de¬nition of a ring homomorphism.

10

Probabilistic primality testing