az ≡ b (mod n) and deg(z) < deg(n).

With this notation, we can simply write a’1 mod n to denote the unique

multiplicative inverse of a modulo n with deg(a) < deg(n).

Theorem 17.16. Let a, b, n ∈ F [X] with n = 0, and let d := gcd(a, n).

If d | b, then the congruence az ≡ b (mod n) has a solution z, and any

polynomial z is also a solution if and only if z ≡ z (mod n/d). If d b,

then the congruence az ≡ b (mod n) has no solution z.

372 More rings

Theorem 17.17 (Chinese remainder theorem). Let n1 , . . . , nk ∈ F [X]

be pairwise relatively prime, non-zero polynomials, and let a1 , . . . , ak ∈ F [X]

be arbitrary polynomials. Then there exists a polynomial z ∈ F [X] such that

z ≡ ai (mod ni ) (i = 1, . . . , k).

Moreover, any other polynomial z ∈ F [X] is also a solution of these congru-

ences if and only if z ≡ z (mod n), where n := k ni .

i=1

Note that the Chinese remainder theorem (with Theorem 17.12) implies

that there exists a unique solution z ∈ F [X] to the given congruences with

deg(z) < deg(n).

The Chinese remainder theorem also has a more algebraic interpreta-

tion. De¬ne quotient rings Ei := F [X]/(ni ) for i = 1, . . . , k, which we may

naturally view as F -algebras (see Example 17.4), along with the product

F -algebra E := E1 — · · · — Ek (see Example 17.2). The map ρ from F [X] to

E that sends z ∈ F [X] to ([z]n1 , . . . , [z]nk ) ∈ E is an F -algebra homomor-

phism. The Chinese remainder theorem says that ρ is surjective, and that

the kernel of ρ is the ideal of F [X] generated by n, giving rise to an F -algebra

isomorphism of F [X]/(n) with E.

Let us recall the formula for the solution z (see proof of Theorem 2.8).

We have

k

z := wi ai ,

i=1

where

wi := ni mi , ni := n/ni , mi := (ni )’1 mod ni (i = 1, . . . , k).

Now, let us consider the special case of the Chinese remainder theorem

where ai ∈ F and ni = (X ’ bi ) with bi ∈ F , for i = 1, . . . , k. The condition

that the ni are pairwise relatively prime is equivalent to the condition that

the bi are all distinct. A polynomial z satis¬es the system of congruences if

and only if z(bi ) = ai for i = 1, . . . , k. Moreover, we have ni = j=i (X ’ bj ),

and mi = 1/ j=i (bi ’ bj ) ∈ F . So we get

k

’ bj )

j=i (X

z= ai .

j=i (bi ’ bj )

i=1

The reader will recognize this as the usual Lagrange interpolation for-

mula. Thus, the Chinese remainder theorem for polynomials includes La-

grange interpolation as a special case.

17.4 Polynomial congruences 373

Let us consider this situation from the point of view of vector spaces.

Consider the map σ : F [X]<k ’ F —k that sends z ∈ F [X] of degree less than

k to (z(b1 ), . . . , z(bk )) ∈ F —k , where as above, b1 , . . . , bk are distinct elements

of F . We see that σ is an F -linear map, and by the Chinese remainder

theorem, it is bijective. Thus, σ is an F -vector space isomorphism of F [X]<k

with F —k .

We may encode elements of F [X]<k as row vectors in a natural way, encod-

ing the polynomial z = k’1 zi Xi as the row vector (z0 , . . . , zk’1 ) ∈ F 1—k .

i=0

With this encoding, we have

σ(z) = (z0 , . . . , zk’1 )V,

where V is the k — k matrix

«

1 1 1

b1 b2 bk

¬ ·

V := ¬ ·.

¬ ·

. . .

. . .

···

. . .

bk’1 bk’1 bk’1

···

1 2 k

The matrix V (well, actually its transpose) is known as a Vandermonde

matrix. Because σ is an isomorphism, it follows that the matrix V is

invertible.

More generally, consider any ¬xed elements b1 , . . . , b of F , where ¤ k,

and consider the F -linear map σ : F [X]<k ’ F — that sends z ∈ F [X]<k to

(z(b1 ), . . . , z(b )). If z = k’1 zi Xi , then

i=0

σ(z) = (z0 , . . . , zk’1 )W,

where W is the k — matrix

«

1 1 1

b1 b2 b

¬ ·

W := ¬ ·.

¬ ·

. . .

. . .

···

. . .

k’1

bk’1 bk’1

···

b1 2

Now, if bi = bj for some i = j, then the columns of W are linearly dependent,

and hence the column rank of W is less than . Since the column rank of

W is equal to its row rank, the dimension of the row space of W is less

than , and hence, σ is not surjective. Conversely, if the bi are all distinct,

then since the submatrix of W consisting of its ¬rst rows is an invertible

Vandermonde matrix, we see that the rank of W is equal to , and hence σ

is surjective.

374 More rings

17.5 Polynomial quotient algebras

Throughout this section, F denotes a ¬eld.

Let f ∈ F [X] be a monic polynomial, and consider the quotient ring

E := F [X]/(f ). As discussed in Example 17.4, we may naturally view E

as an F -algebra via the map „ that sends c ∈ R to [c]f ∈ E. Moreover,

if deg(f ) > 0, then „ is an embedding of F in F [X]/(f ), and otherwise, if

f = 1, then E is the trivial ring, and „ maps everything to zero.

Suppose that := deg(f ) > 0. Let · := [X]f ∈ E. Then E = F [·], and as

an F -vector space, E has dimension , with 1, ·, . . . , · ’1 being a basis (see

Examples 9.34, 9.43, 14.3, and 14.22). That is, every element of E can be

expressed uniquely as g(·) for g ∈ F [X] of degree less than .

Now, if f is irreducible, then every polynomial a ≡ 0 (mod f ) is relatively

prime to f , and hence invertible modulo f ; therefore, it follows that E is a

¬eld. Conversely, if f is not irreducible, then E cannot be a ¬eld ” indeed,

if g is a non-trivial factor of f , then g(·) is a zero divisor.

If F = Zp for a prime number p, and f is irreducible, then we see that E

is a ¬nite ¬eld of cardinality p . In the next chapter, we shall see how one

can perform arithmetic in such ¬elds e¬ciently, and later, we shall also see

how to e¬ciently construct irreducible polynomials of any given degree over

a ¬nite ¬eld.

Minimal polynomials. Now suppose that E is any F -algebra, and let ±

be an element of E. Consider the polynomial evaluation map ρ : F [X] ’ E

that sends g ∈ F [X] to g(±). The kernel of ρ is an ideal of F [X], and since

every ideal of F [X] is principal, it follows that there exists a polynomial

φ ∈ F [X] such that ker(ρ) is the ideal of F [X] generated by φ; moreover,

we can make the choice of φ unique by insisting that it is monic or zero.

The polynomial φ is called the minimal polynomial of ± (over F ). If

φ = 0, then ρ is injective, and hence the image F [±] of ρ is isomorphic (as

an F -algebra) to F [X]. Otherwise, F [±] is isomorphic (as an F -algebra) to

F [X]/(φ); moreover, since any polynomial that is zero at ± is a polynomial

multiple of φ, we see that φ is the unique monic polynomial of smallest