In the situation discussed in this result, the following names are often used. We refer to the

process of ¬nding q(X) and r(X) as long division of f (X) by d(X). Also,

f (X) = the dividend , d(X) = the divisor , q(X) = the quotient, r(X) = the remainder .

Example 1.26. If k = Q, ¬nd the quotient and remainder when the long division of f (X) =

6X 4 ’ 6X 3 + 3X 2 ’ 3X + 1 by d(X) = 2X 2 + 1 is performed.

Solution. In the usual notation we have the following calculation.

3X 2 ’ 3X

2X 2 + 1 | 6X 4 ’ 6X 3 + 3X 2 ’ 3X + 1

6X 4 + 0X 3 + 3X 2 + 0X + 0

’ 6X 3 + 0X 2 ’ 3X + 1

’ 6X 3 + 0X 2 ’ 3X + 0

1

Hence

6X 4 ’ 6X 3 + 3X 2 ’ 3X + 1 = (3X 2 ’ 3X)(2X 2 + 1) + 1,

giving q(X) = 3X 2 ’ 3X and r(X) = 1.

Example 1.27. If k = F5 , ¬nd the quotient and remainder when long division of f (X) =

10X 5 + 6X 4 ’ 6X 3 + 3X 2 ’ 3X + 1 by d(X) = 2X 2 + 1 is performed.

Solution. First notice that working modulo 5 we have

f (X) = 10X 5 + 6X 4 ’ 6X 3 + 3X 2 ’ 3X + 1 ≡ X 4 + 4X 3 + 3X 2 + 2X + 1 (mod 5).

Notice also that multiplicative inverses in F5 are given by

2’1 ≡ 3 (mod 5), 3’1 ≡ 2 (mod 5), 4’1 ≡ 4 (mod 5).

8 1. INTEGRAL DOMAINS, FIELDS AND POLYNOMIAL RINGS

We have the following calculation.

3X 2 + 2X

2X 2 + 1| 6X 4 + 4X 3 + 3X 2 + 2X + 1

6X 4 + 0X 3 + 3X 2 + 0X + 0

4X 3 + 0X 2 + 2X + 1

4X 3 + 0X 2 + 2X + 0

1

Hence

6X 4 ’ 6X 3 + 3X 2 ’ 3X + 1 ≡ (3X 2 + 2X)(2X 2 + 1) + 1 (mod 5),

giving q(X) = 3X 2 + 2X and r(X) = 1.

An important consequence of Theorem 1.25 is the following which makes use of the Euclidean

Algorithm.

Corollary 1.28. Let k be a ¬eld and X an indeterminate. Let f (X), g(X) ∈ k[X] be

non-zero. Then there are a(X), b(X) ∈ k[X] such that

a(X)f (X) + b(X)g(X) = gcd(f (X), g(X)).

Here the greatest common divisor gcd(f (X), g(X)) of f (X), g(X) is the monic polynomial

of greatest degree which divides both of f (X), g(X).

Proposition 1.29. Let k be a ¬eld and X an indeterminate. Then a non-constant polyno-

mial p(X) ∈ k[X] is an irreducible if and only if it is a prime.

™

Proof. By Lemma 1.14 we already know that p(X) is irreducible if it is prime. So

™™¦

™

suppose that p(X) is irreducible and that p(X) | u(X)v(X) for u(X), v(X) ∈ k[X]. Then by

Corollary 1.28, there are a(X), b(X) ∈ k[X] such that

a(X)p(X) + b(X)u(X) = gcd(p(X), u(X)).

But since p(X) is irreducible, gcd(p(X), u(X)) = 1, hence

a(X)p(X) + b(X)u(X) = 1.

Multiplying through by v(X) gives

a(X)p(X)v(X) + b(X)u(X)v(X) = v(X)

and so p(X) | v(X). This shows that p(X) | u(X) or p(X) | v(X) and so p(X) is prime.

Theorem 1.30. Let k be a ¬eld and X an indeterminate.

(i) Every ideal I k[X] is principal, i.e., I = (h(X)) for some h(X) ∈ k[X].

(ii) The ideal (p(X)) k[X] is prime if and only if p(X) = 0 or p(X) is irreducible in k[X].

(iii) The quotient ring k[X]/(p(X)) is an integral domain if and only if p(X) = 0 or p(X)

is irreducible in k[X].

(iv) The quotient ring k[X]/(p(X)) is a ¬eld if and only if p(X) is an irreducible in k[X].

™

Proof. (i) Let I k[X] and assume that I = (0). Then there must be at least

™™¦

™

one element of I with positive degree and so we can choose h(X) ∈ I of minimal degree, say

d = deg h(X).

Now let p(X) ∈ I. By Long Division, there are q(X), r(X) ∈ k[X] such that

p(X) = q(X)h(X) + r(X) and deg r(X) < d or r(X) = 0.

Since p(X) and h(X) are in the ideal I, we also have

r(X) = p(X) ’ q(X)h(X) ∈ I.

1.2. POLYNOMIAL RINGS 9

If r(X) = 0 this would contradict the minimality of d, so we must have r(X) = 0, showing that

p(X) = q(X)h(X). Thus I ⊆ (p(X)) ⊆ I and therefore I = (p(X)).

(ii) This follows from Proposition 1.29.

(iii) This follows from Proposition 1.7(i).

(iv) Since k[X] is an integral domain and not a ¬eld, it is follows that if k[X]/(p(X)) is a ¬eld

then because it is an integral domain, p(X) is an irreducible by (iii).

Suppose that p(X) is irreducible (and hence is non-zero). Then for any q(X) ∈ k[X] with

q(X) ∈ (p(X)) we can use the Euclidean Algorithm of Corollary 1.28 to write

/

a(X)p(X) + b(X)q(X) = gcd(p(X), q(X)).

But gcd(p(X), q(X)) = 1 since p(X) is irreducible, so

a(X)p(X) + b(X)q(X) = 1.

This shows that in the quotient ring k[X]/(p(X)) the residue class of q(X) has the residue class

of b(X) as its inverse.

Remark 1.31. In connection with Theorem 1.30(i), notice that if p(X) ∈ k[X], then pro-

vided d = deg p(X) > 0, we have for some pd = 0,

p(X) = p0 + p1 X + · · · + pd X d = pd q(X),

where

q(X) = p’1 p0 + p’1 p1 X + · · · + p’1 pd’1 X d’1 + X d .

d d d

This easily implies that as ideals of k[X], (p(X)) = (q(X)). So we can always ¬nd a monic

polynomial as the generator of a given ideal, and this monic polynomial is unique.

Proposition 1.32 (Unique Factorization Property). Every non-constant polynomial f (x) ∈

k[X] has a factorization

f (x) = cp1 (X) · · · pk (X),

where c ∈ k, and p1 (X), . . . , pk (X) ∈ k[X] are irreducible monic polynomials. Moreover, c is

unique and the sequence of polynomials p1 (X), . . . , pk (X) is unique apart from the order of the

terms.

™

Proof. (Sketch)

™™¦

™

Existence is proved by induction on the degree of f (X) and begins with the obvious case

deg f (X) = 1. If deg f (X) > 1, then either f (X) is already irreducible, or f (X) = f1 (X)f2 (X)

with both factors of positive degree, and therefore deg fj (X) < deg f (X). This gives the

inductive step.

To prove uniqueness, suppose that

p1 (X) · · · pk (X) = q1 (X) · · · q (X)

where pi (X), qj (X) ∈ k[X] are irreducible monic polynomials. Then by Proposition 1.29, each

pi (X) is prime, hence divides one of the qj (X), hence must equal it. By reordering we can

assume that pi (X) = qi (X) and k . After cancelling common factors we obtain

qk+1 (X) · · · q (X) = 1,

and so we see that k = .

Corollary 1.33. Suppose that f (X) ∈ k[X] factors into linear factors

f (X) = c(X ’ u1 ) · · · (X ’ ud ),

where u1 , . . . , ud ∈ k. Then the sequence of roots u1 , . . . , ud is unique apart from the order. In

particular, if v1 , . . . , vr are the distinct roots, then

f (X) = c(X ’ v1 )m1 · · · (X ’ vr )mr ,

where mi > 0 and this factorization is unique apart from the order of the pairs (vi , mi ).

10 1. INTEGRAL DOMAINS, FIELDS AND POLYNOMIAL RINGS

Corollary 1.34. The number of distinct roots of the non-constant polynomial f (X) ∈ k[X]

is at most deg f (X).

Definition 1.35. If k is a ¬eld and X an indeterminate, then the ring of rational functions

k(X) is the fraction ¬eld of k[X]. The elements of k(X) are fractions

a0 + a1 X + · · · + am X m

b0 + b1 X + · · · + bn X n

with ai , bj ∈ k.

1.3. Identifying irreducible polynomials

We will need some e¬ective methods for identifying when a polynomial is irreducible in a

polynomial ring k[X] where k is a ¬eld.

Let us consider factorisation of polynomials over Q. If f (X) ∈ Z[X] then we can also consider

f (X) as an element of Q[X]. If R = Z or Q, we say that f (X) has a proper factorisation over

R if f (X) = g(X)h(X) for some g(X), h(X) ∈ R[X] with deg g(X) > 0 and deg h(X) > 0.

Proposition 1.36 (Gauss™s Lemma). Let f (X) ∈ Z[X]. Then f (X) has a proper factori-

sation over Z if and only it has a proper factorisation over Q.

So to ¬nd factors of f (X) it is su¬cient to look for factors in Z[X]. The next result is a

special case of the Eisenstein Irreducibility Test. Our version is slightly more general than the

usual one which corresponds to taking s = 0.

Proposition 1.37 (Eisenstein Test). Let f (X) ∈ Z[X] and s ∈ Z. Choose ai ∈ Z so that

f (X) = a0 + a1 (X ’ s) + · · · + ad’1 (X ’ s)d’1 + ad (X ’ s)d ,

where d = deg f (X). Suppose that p > 0 is a prime in Z for which the following conditions

hold:

• ak ≡ 0 (mod p) for k = 0, . . . , d ’ 1;

• a0 ≡ 0 (mod p2 );

• ad ≡ 0 (mod p).

Then f (X) is irreducible in Q[X] and hence also in Z[X].

Example 1.38. Let p 2 be a prime. Then the polynomial

¦p (X) = 1 + X + · · · + X p’1 ∈ Z[X]

is irreducible in Q[X] and hence also in Z[X].

Proof. Working in Z[X],

¦p (X)(X ’ 1) = (1 + X + · · · + X p’1 )(X ’ 1)

= Xp ’ 1

= (1 + (X ’ 1))p ’ 1

p

p

(X ’ 1)k

=

k

k=1

≡ (X ’ 1)p (mod p),

since by (1.1a), p divides

p p!

=

k k! (p ’ k)!

when k = 1, . . . , p ’ 1. Hence

¦p (X) ≡ (X ’ 1)p’1 (mod p)

Also,

p

= p ≡ 0 (mod p2 ),

1

1.3. IDENTIFYING IRREDUCIBLE POLYNOMIALS 11

giving

¦p (X) = (X ’ 1)p’1 + cp’2 (X ’ 1)p’2 + · · · + c1 (X ’ 1) + c0

(1.3)

with cr ≡ 0 (mod p) and c0 = p. So the Eisenstein Test can be applied here with s = 1 to show

that ¦p (X) is irreducible in Z[X].

Example 1.39. As examples we have the irreducible polynomials

¦2 (X) = 1 + X,

¦3 (X) = 1 + X + X 2 ,

¦5 (X) = 1 + X + X 2 + X 3 + X 4 ,

¦7 (X) = 1 + X + X 2 + X 3 + X 4 + X 5 + X 6 ,

¦11 (X) = 1 + X + X 2 + X 3 + X 4 + X 5 + X 6 + X 7 + X 8 + X 9 + X 10 .

These are examples of the cyclotomic polynomials ¦n (X) ∈ Z[X] which are de¬ned for all

n 1 by

Xn ’ 1 =

(1.4a) ¦d (X),

d|n

where the product is taken over all the positive divisors of n. For example,

X 2 ’ 1 = (X ’ 1)(X + 1) = ¦1 (X)¦2 (X),

X 3 ’ 1 = (X ’ 1)(X 2 + X + 1) = ¦1 (X)¦3 (X),

X 4 ’ 1 = (X ’ 1)(X + 1)(X 2 + 1) = ¦1 (X)¦2 (X)¦4 (X),

X 5 ’ 1 = (X ’ 1)(X 4 + X 3 + X + 1) = ¦1 (X)¦5 (X),

X 6 ’ 1 = (X ’ 1)(X + 1)(X 2 + X + 1)(X 2 ’ X + 1) = ¦1 (X)¦2 (X)¦3 (X)¦6 (X),

X 12 ’ 1 = (X ’ 1)(X + 1)(X 2 + X + 1)(X 2 + 1)(X 2 ’ X + 1)(X 4 ’ X 2 + 1)

= ¦1 (X)¦2 (X)¦3 (X)¦4 (X)¦6 (X)¦12 (X).

Cyclotomic polynomials can be computed recursively using Equation (1.4a). If we know ¦k (X)

for k < n, then

Xn ’ 1

(1.4b) ¦n (X) = .

¦d (X)

d|n

d<n

The degree of ¦n (X) involves a function of n probably familiar from elementary Number Theory.

Definition 1.40. The Euler function • : N ’’ N is de¬ned by

•(n) = number of k = 1, . . . , n for which gcd(n, k) = 1

= |(Z/n)— | = number of units in Z/n

= number of generators of the cyclic group Z/n.

In particular, if p 2 is a prime then •(p) = p ’ 1. Of course, •(1) = 1.

It can be shown that for each natural number n,

(1.5) •(d) = n.

d|n

Notice that we can inductively determine •(n) using this equation. For example, if p and q are

distinct primes, then

•(pq) = pq ’ (•(p) + •(q) + •(1)) = pq ’ (p ’ 1) ’ (q ’ 1) ’ 1 = (p ’ 1)(q ’ 1).

It is also true that whenever m, n are coprime, i.e., when gcd(m, n) = 1,

(1.6) •(mn) = •(m)•(n).

12 1. INTEGRAL DOMAINS, FIELDS AND POLYNOMIAL RINGS

Thus if n = pr1 · · · prs where p1 < p2 < · · · < ps are the prime factors of n and rj > 0, then

s

1

•(n) = •(pr1 ) · · · •(prs ).

(1.7) s

1

Furthermore, if p is a prime and r > 0, then

•(pr ) = (p ’ 1)pr’1 .

(1.8)

Notice that as a result, •(n) is even when n > 2.

Remark 1.41. For those who know about the M¨bius function µ (which takes values 0, ±1)

o

and M¨bius inversion, the latter can be used to solve Equation (1.5) for •, giving

o

n

(1.9) •(n) = µ(d) .

d

d|n

Similarly, the formul¦ of (1.4) lead to

(X n/d ’ 1)µ(d) .

(1.10) ¦n (X) =

d|n

So for example, if p, q are distinct primes, then using standard properties of µ,

¦pq (X) = (X pq ’ 1)µ(1) (X pq/p ’ 1)µ(p) (X pq/q ’ 1)µ(q) (X pq/pq ’ 1)µ(pq)

(X pq ’ 1)(X ’ 1)

pq q ’1 p ’1

= (X ’ 1)(X ’ 1) (X ’ 1) (X ’ 1) = .

(X q ’ 1)(X p ’ 1)

Recall that an element ζ of a ¬eld K is a primitive n-th root of unity if

k and ζ k = 1} = n.

min{k : 1

We think of ζn = e2πi/n as the standard complex primitive n-th root of unity. Then every

complex n-th root of unity has the form ζn = e2πik/n for k = 0, 1, . . . , n ’ 1.

k

Theorem 1.42. For each n 1, the cyclotomic polynomial ¦n (X) is irreducible in Q[X]

and hence in Z[X]. The complex roots of ¦n (X) are the primitive n-th roots of unity,

ζn = e2πik/n

k

(0 k n ’ 1, gcd(k, n) = 1).

and the number of these is deg ¦n (X) = •(n). Hence,