If E has ¬nite dimension, say n, as an F -vector space, then any element ±

of E has a non-zero minimal polynomial. Indeed, the elements 1E , ±, . . . , ±n

must be linearly dependent (as must be any n + 1 vectors in a vector space

of dimension n), and hence there exist c0 , . . . , cn ∈ F , not all zero, such that

c0 1E + c1 ± + · · · + cn ±n = 0E ,

i

and therefore, the non-zero polynomial g := i ci X is zero at ±.

17.5 Polynomial quotient algebras 375

Example 17.8. The polynomial X2 + 1 is irreducible over R, since if it were

not, it would have a root in R (see Exercise 17.7), which is clearly impossible,

since ’1 is not the square of any real number. It follows immediately that

C = R[X]/(X2 + 1) is a ¬eld, without having to explicitly calculate a formula

for the inverse of a non-zero complex number. 2

Example 17.9. Consider the polynomial f := X4 +X3 +1 over Z2 . We claim

that f is irreducible. It su¬ces to show that f has no irreducible factors of

degree 1 or 2.

If f had a factor of degree 1, then it would have a root; however, f (0) =

0 + 0 + 1 = 1 and f (1) = 1 + 1 + 1 = 1. So f has no factors of degree 1.

Does f have a factor of degree 2? The polynomials of degree 2 are X2 ,

X2 + X, X2 + 1, and X2 + X + 1. The ¬rst and second of these polynomials

are divisible by X, and hence not irreducible, while the third has a 1 as a

root, and hence is also not irreducible. The last polynomial, X2 + X + 1, has

no roots, and hence is the only irreducible polynomial of degree 2 over Z2 .

So now we may conclude that if f were not irreducible, it would have to be

equal to

(X2 + X + 1)2 = X4 + 2X3 + 3X2 + 2X + 1 = X4 + X2 + 1,

which it is not.

Thus, E := Z2 [X]/(f ) is a ¬eld with 24 = 16 elements. We may think of

elements E as bit strings of length 4, where the rule for addition is bit-wise

“exclusive-or.” The rule for multiplication is more complicated: to multiply

two given bit strings, we interpret the bits as coe¬cients of polynomials

(with the left-most bit the coe¬cient of X3 ), multiply the polynomials, reduce

the product modulo f , and write down the bit string corresponding to the

reduced product polynomial. For example, to multiply 1001 and 0011, we

compute

(X3 + 1)(X + 1) = X4 + X3 + X + 1,

and

(X4 + X3 + X + 1) mod (X4 + X3 + 1) = X.

Hence, the product of 1001 and 0011 is 0010.

Theorem 9.16 says that E — is a cyclic group. Indeed, the element · :=

0010 (i.e., · = [X]f ) is a generator for E — , as the following table of powers

shows:

376 More rings

·i ·i

i i

1 8

0010 1110

2 9

0100 0101

3 10

1000 1010

4 11

1001 1101

5 12

1011 0011

6 13

1111 0110

7 14

0111 1100

15 0001

Such a table of powers is sometimes useful for computations in small

¬nite ¬elds such as this one. Given ±, β ∈ E — , we can compute ±β by

obtaining (by table lookup) i, j such that ± = · i and β = · j , computing

k := (i + j) mod 15, and then obtaining ±β = · k (again by table lookup).

2

Exercise 17.8. In the ¬eld E is Example 17.9, what is the minimal poly-

nomial of 1011 over Z2 ?

Exercise 17.9. Show that if the factorization of f over F [X] into irreducibles

e e

is as f = f1 1 · · · fr r , and if ± = [h]f ∈ F [X]/(f ), then the minimal polynomial

φ of ± over F is lcm(φ1 , . . . , φr ), where each φi is the minimal polynomial

of [h]f ei ∈ F [X]/(fiei ) over F .

i

17.6 General properties of extension ¬elds

We now discuss a few general notions related to extension ¬elds. These are

all quite simple applications of the theory developed so far. Recall that if F

and E are ¬elds, with F being a subring of E, then E is called an extension

¬eld of F . As usual, we shall blur the distinction between a subring and a

canonical embedding; that is, if „ : F ’ E is an canonical embedding, we

shall simply identify elements of F with their images in E under „ , and in

so doing, we may view E as an extension ¬eld of F . Usually, the map „

will be clear from context; for example, if E = F [X]/(φ) for some irreducible

polynomial φ ∈ F [X], then we shall simply say that E is an extension ¬eld of

F , although strictly speaking, F is embedded in E via the map that sends

a ∈ F to [a]φ ∈ E.

Let E be an extension ¬eld of a ¬eld F . Then E is an F -algebra, and in

particular, an F -vector space. If E is a ¬nite dimensional F -vector space,

then we say that E is a ¬nite extension of F , and dimF (E) is called the

17.6 General properties of extension ¬elds 377

degree of the extension, and is denoted (E : F ); otherwise, we say that E

is an in¬nite extension of F .

An element ± ∈ E is called algebraic over F if there exists a non-zero

polynomial f ∈ F [X] such that f (±) = 0; otherwise, ± is called transcen-

dental over F . If all elements of E are algebraic over F , then we call E an

algebraic extension of F . From the discussion on minimal polynomials

in §17.5, we may immediately state:

Theorem 17.18. If E is a ¬nite extension of F , then E is also an algebraic

extension of F .

Suppose ± ∈ E is algebraic over F . Let φ be its minimal polynomial,

so that F [X]/(φ) is isomorphic (as an F -algebra) to F [±]. Since F [±] is a

subring of a ¬eld, it must be an integral domain, which implies that φ is

irreducible, which in turn implies that F [±] is a sub¬eld of E. Moreover,

the degree (F [±] : F ) is equal to the degree of φ, and this number is called

the degree of ± (over F ). It is clear that if E is ¬nite dimensional, then

the degree of ± is at most (E : F ).

Suppose that ± ∈ E is transcendental over F . Consider the “rational

function evaluation map” that sends f /g ∈ F (X) to f (±)/g(±) ∈ E. Since

no non-zero polynomial over F vanishes at ±, it is easy to see that this map

is well de¬ned, and is in fact an injective F -algebra homomorphism from

F (X) into E. The image is denoted F (±), and this is clearly a sub¬eld of

E containing F and ±, and it is plain to see that it is the smallest such

sub¬eld. It is also clear that F (±) has in¬nite dimension over F , since it

contains an isomorphic copy of the in¬nite dimensional vector space F [X].

More generally, for any ± ∈ E, algebraic or transcendental, we can de¬ne

F (±) to be the set consisting of all elements of the form f (±)/g(±) ∈ E,

where f, g ∈ F [X] and g(±) = 0. It is clear that F (±) is a ¬eld, and indeed,

it is the smallest sub¬eld of E containing F and ±. If ± is algebraic, then

F (±) = F [±], and is isomorphic (as an F -algebra) to F [X]/(φ), where φ is

the minimal polynomial of ± over F ; otherwise, if ± is transcendental, then

F (±) is isomorphic (as an F -algebra) to the rational function ¬eld F (X).

Example 17.10. If f ∈ F [X] is monic and irreducible, E = F [X]/(f ), and

· := [X]f ∈ E, then · is algebraic over F , its minimal polynomial over F is

f , and its degree over F is equal to deg(f ). Also, we have E = F [·], and

any element ± ∈ E is algebraic of degree at most deg(f ). 2

Exercise 17.10. In the ¬eld E is Example 17.9, ¬nd all the elements of

degree 2 over Z2 .

378 More rings

Exercise 17.11. Show that if E is a ¬nite extension of F , with a basis

±1 , . . . , ±n over F , and K is a ¬nite extension of E, with a basis β1 , . . . , βm

over E, then

±i βj (i = 1, . . . , n; j = 1, . . . , m)

is a basis for K over F , and hence K is a ¬nite extension of F and

(K : F ) = (K : E)(E : F ).