Advanced book on Mathematics Olympiad

56 2 Algebra

2.2.5 Irreducible Polynomials...................................

A polynomial is irreducible if it cannot be written as a product of two polynomials in
a nontrivial manner. The question of irreducibility depends on the ring of coefficients.
When the coefficients are complex numbers, only linear polynomials are irreducible. For
real numbers some quadratic polynomials are irreducible as well. Both these cases are
rather dull. The interesting situations occur when the coefficients are rational or integer,
in which case there is an interplay between polynomials and arithmetic. The cases of
rational and integer coefficients are more or less equivalent, with minor differences such
as the fact that 2x+2 is irreducible overQ[x]but reducible overZ[x]. For matters of
elegance we focus on polynomials with integer coefficients. We will assume implicitly
from now on that for any polynomial with integer coefficients, the greatest common
divisor of its coefficients is 1.

Definition.A polynomialP(x)∈Z[x]is called irreducible overZ[x]if there do not

exist polynomialsQ(x), R(x)∈Z[x]different from±1 such thatP(x)=Q(x)R(x).

Otherwise,P(x)is called reducible.

We commence with an easy problem.

Example.LetP(x)be annth-degree polynomial with integer coefficients with the prop-

erty that|P(x)|is a prime number for 2n+1 distinct integer values of the variablex.

Prove thatP(x)is irreducible overZ[x].

Solution.Assume the contrary and letP(x)=Q(x)R(x)withQ(x), R(x) ∈Z[x],

Q(x), R(x) =±1. Letk=deg(Q(x)). ThenQ(x)=1 at mostktimes andQ(x)=

−1 at mostn−ktimes. Also,R(x)=1 at mostn−ktimes andR(x)=−1at

mostktimes. Consequently, the product|Q(x)R(x)|is composite except for at most

k+(n−k)+(n−k)+k= 2 nvalues ofx. This contradicts the hypothesis. Hence

P(x)is irreducible. 

The bound is sharp. For example,P(x)=(x+ 1 )(x+ 5 )has|P(− 2 )|=|P(− 4 )|=

3,P( 0 )=5, and|P(− 6 )|=7.

Probably the most beautiful criterion of irreducibility of polynomials is that discov-

ered independently by F.G.M. Eisenstein in 1850 and T. Schönemann in 1846. We present

it below.

Theorem.Given a polynomialP(x)=anxn+an− 1 xn−^1 +···+a 0 with integer coef-

ficients, suppose that there exists a prime numberpsuch thatanis not divisible byp,

akis divisible bypfork= 0 , 1 ,...,n− 1 , anda 0 is not divisible byp^2. ThenP(x)is

irreducible overZ[x].