# Irreducibility

Polynomial \( P(x) \) with integer coefficients is said to be *
irreducible* over \( \mathbb{Z}[x] \) if it cannot be written as a
product of two nonconstant polynomials with integer coefficients.

** Example **

Every quadratic or cubic polynomial with no rational roots is
irreducible over \( \mathbb{Z} \). Such are e.g. \( x^2-x-1 \) and
\( 2x^3-4x+1 \).

One analogously defines (ir)reducibility over the sets of
polynomials with e.g. rational, real or complex coefficients.
However, of the mentioned, only reducibility over \( \mathbb{Z}[x] \)
is of interest. Gauss’ Lemma below claims that the reducibility
over \( \mathbb{Q}[x] \) is equivalent to the reducibility over
\( \mathbb{Z}[x] \). In addition, we have already shown that a real
polynomial is always reducible into linear and quadratic factors
over \( \mathbb{R}[x] \), while a complex polynomial is always reducible
into linear factors over \( \mathbb{C}[x] \).

** Theorem 4.1 (Gauss’ Lemma) **

If a polynomial \( P(x) \) with integer
coefficients is reducible over \( \mathbb{Q}[x] \), then it is reducible
over \( \mathbb{Z}[x] \), also.

Suppose that \( P(x)=a_nx^n+\cdots+a_0=
Q(x)R(x)\in\mathbb{Z}[x] \), where \( Q(x) \) and \( R(x) \) nonconstant
polynomials with rational coefficients. Let \( q \) and \( r \) be the
smallest natural numbers such that the polynomials \( qQ(x)=q_kx^k+
\cdots+q_0 \) and \( rR(x)=r_mx^m+\cdots+r_0 \) have integer coefficients.
Then \( qrP(x)=qQ(x)\cdot rR(x) \) is a factorization of the polynomial
\( qrP(x) \) into two polynomials from \( \mathbb{Z}[x] \). Based on this,
we shall construct such a factorization for \( P(x) \).

Let \( p \) be an arbitrary prime divisor of \( q \). All coefficients of
\( qrP(x) \) are divisible by \( p \). Let \( i \) be such that \( p\mid q_0,q_1,
\dots,q_{i-1} \), but \( p\nmid q_i \). We have \( p\mid qra_i=q_0r_i+\cdots+
q_ir_0\equiv q_ir_0 \) (mod \( p \)), which implies that \( p\mid r_0 \).
Furthermore, \( p\mid qr a_{i+1}=q_0r_{i+1}+\cdots+q_ir_1+q_{i+1}r_0
\equiv q_ir_1 \) (mod \( p \)), so \( p\mid r_1 \). Continuing in this way, we
deduce that \( p\mid r_j \) for all \( j \). Hence \( rR(x)/p \) has integer
coefficients. We have thus obtained a factorization of
\( \frac{rq}pP(x) \) into two polynomials from \( \mathbb{Z}[x] \).
Continuing this procedure and taking other values for \( p \) we shall
eventually end up with a factorization of \( P(x) \) itself.

From now on, unless otherwise specified, by *irreducibility* we
mean irreducibility over \( \mathbb{Z}[x] \).

** Problem 9 **

If \( a_1 \), \( a_2 \), \( \dots \), \( a_n \) are integers, prove that the polynomial
\( P(x)=(x-a_1)(x-a_2)\cdots(x-a_n)-1 \) is irreducible.

Suppose that \( P(x)=Q(x)R(x) \) for some nonconstant polynomials
\( Q,R\in\mathbb{Z}[x] \). Since \( Q(a_i)R(a_i) =-1 \) for \( i=1,\dots,n \),
we have \( Q(a_i)=1 \) and \( R(a_i)=-1 \) or \( Q(a_i)=-1 \) and \( R(a_i)=1 \);
either way, we have \( Q(a_i)+R(a_i)=0 \). It follows that the
polynomial \( Q(x)+R(x) \) (which is obviously nonzero) has \( n \) zeros
\( a_1,\dots,a_n \) which is impossible for its degree is less than \( n \).

** Theorem 4.2 (Extended Eisenstein’s Criterion) **

Let \( P(x)=
a_nx^n+\dots+a_1x+a_0 \) be a polynomial with integer coefficients. If
there exist a prime number \( p \) and an integer \( k\in\{0,1,\dots,
n-1\} \) such that
\[ p\mid a_0,a_1,\dots,a_k,\;\;p\nmid a_{k+1}\;\;\mbox{and}\;\;p^2
\nmid a_0,\] then \( P(x) \) has an irreducible factor of a degree
greater than \( k \).

In particular, if \( p \) can be taken so that \( k=n-1 \), then \( P(x) \) is
irreducible.

Like in the proof of Gauss’ Lemma, suppose that
\( P(x)=Q(x)R(x) \), where \( Q(x)=q_kx^k+\cdots+q_0 \) and \( R(x)=r_mx^m
+\cdots+r_0 \) are polynomials from \( \mathbb{Z}[x] \). Since
\( a_0=q_0r_0 \) is divisible by \( p \) and not by \( p^2 \), exactly one of
\( q_0,r_0 \) is a multiple of \( p \). Assume that \( p\mid q_0 \) and \( p\nmid
r_0 \). Further, \( p\mid a_1=q_0r_1+q_1r_0 \), implying that \( p\mid
q_1r_0 \), i.e. \( p\mid q_1 \), and so on. We conclude that all
coefficients \( q_0,q_1,\dots,q_k \) are divisible by \( p \), but \( p\nmid
q_{k+1} \). It follows that \( \deg Q \geq k+1 \).

** Problem 10 (IMO93.1) **

Given an integer \( n> 1 \), consider the polynomial \( f(x)=x^n+5x^{n-1}
+3 \). Prove that there are no nonconstant polynomials \( g(x),h(x) \)
with integer coefficients such that \( f(x)=g(x)h(x) \).

By the (extended) Eisenstein
criterion, \( f \) has an irreducible factor of degree at least \( n-1 \).
Since \( f \) has no integer zeros, it must be irreducible.

** Problem 11 **

If \( p \) is a prime number, prove that the polynomial
\( \Phi_p(x)=x^{p-1}+\cdots+x+1 \) is irreducible.

Instead of \( \Phi_p(x) \), we shall consider \( \Phi_p(x+1) \) and show
that it is irreducible, which will clearly imply that so is
\( \Phi_p \). We have
\[ \Phi_p(x+1)=\frac{(x+1)^p-1}x=x^{p-1}+\binom p{p-1}x^{p-2}
+\cdots+\binom p2x+p.\] This polynomial satisfies all the
assumptions of Eisenstein’s criterion, based on which it is
irreducible.

In investigating reducibility of a polynomial, it can be useful to
investigate its zeros and their modules. The following problems
provide us an illustration.

** Problem 12 **

Prove that the polynomial \( P(x)=x^n+4 \) is irreducible over
\( \mathbb{Z}[x] \) if and only if \( n \) is a multiple of 4.

All zeros of polynomial \( P \) have the modulus equal to \( 2^{2/n} \). If
\( Q \) and \( R \) are polynomials from \( \mathbb{Z}[x] \) and \( \deg Q=k \),
then \( |Q(0)| \) is the product of the modules of the zeros of \( Q \) and
equals \( 2^{2k/n} \); since this should be an integer, we deduce that
\( n=2k \).

If \( k \) is odd, polynomial \( Q \) has a real zero, which is impossible
since \( P(x) \) has none. Therefore, \( 2\mid k \) and \( 4\mid n \).

If the zeros cannot be exactly determined, one should find a good
enough bound. Estimating complex zeros of a polynomial is not always
simple. Our main tool is the triangle inequality for complex
numbers: \[ |x|-|y|\leq|x+y|\leq|x|+|y|.\]

Consider a polynomial \( P(x)=a_nx^n+a_{n-k}x{n-k}+\cdots+a_1x+a_0 \)
with complex coefficients (\( a_n\neq0 \)). Let \( \alpha \) be its zero. If
\( M \) is a real number such that \( |a_i|< M|a_n| \) for all \( i \), it holds
that \[ 0=|P(\alpha)|\geq|a_n||\alpha|^n-M|a_n|
(|\alpha|^{n-k}+\cdots+|\alpha|+1)> |a_n||\alpha|^n \left(1-\frac
M{|\alpha|^{k-1}(|\alpha|-1)}\right),\] which yields
\( |\alpha|^{k-1}(|\alpha|-1)< M \). We thus come to the following
estimate:

** Theorem 4.3 **

Let \( P(x)=a_nx^n+\cdots+a_0 \) be a complex polynomial
with \( a_n\neq0 \) and \( \displaystyle M=\max_{0\leq k< n}\left|\frac{a_k}{a_n}
\right| \). If \( a_{n-1}=\cdots=a_{n-k+1}=0 \), then all roots of the
polynomial \( P \) are less than \( 1+\sqrt[k]M \) in modulus.

In particular, for \( k=1 \), each zero of \( P(x) \) is of modulus less
than \( M+1 \).

** Problem 13 (Balkan Mathematical Olympiad 1989) **

If \( \overline{a_n\dots a_1a_0} \) is a decimal representation of a
prime number and \( a_n> 1 \), prove that the polynomial \( P(x)=a_nx^n+
\cdots+a_1x+a_0 \) is irreducible.

Suppose that \( Q \) and \( R \) are nonconstant polynomials from
\( \mathbb{Z}[x] \) with \( Q(x)R(x)=P(x) \). Let \( x_1,\dots,x_k \) be the
zeros of \( Q \) and \( x_{k+1},\dots,x_n \) be the zeros of \( R \). The
condition of the problem means that \( P(10)=Q(10)R(10) \) is a prime,
so we can assume w.l.o.g. that
\[ |Q(10)|=(10-x_1)(10-x_2)\cdots(10-x_k)= 1.\] On the other hand,
by the estimate in \ref{T.4.3}, each zero \( x_i \) has a modulus less than
\( 1+9/2=11/2< 9 \); hence \( |10-x_i|> 1 \) for all \( i \), contradicting the
above inequality.

** Problem 14 **

Let \( p> 2 \) be a prime number and \( P(x)=x^p-x+p \).

**(a)**
Prove that all zeros of polynomial \( P \) are less than
\( \displaystyle p^{\frac1{p-1}} \) in modulus.
**(b)** Prove that the polynomial \( P(x) \) is irreducible.

**(a)**
Let \( y \) be a zero of \( P \). Then \( |y|^p-|y|\leq|y^p-y|=p \). If we
assume that \( |y|\geq\displaystyle p^{\frac1{p-1}} \), we obtain
\[ |y|^p-|y|\geq(p-1)p^{\frac1{p-1}}> p,\] a contradiction. Here we
used the inequality \( p^{\frac1{p-1}}> \frac p{p-1} \) which follows for
example from the binomial expansion of \( p^{p-1}=((p-1)+1)^{p-1} \).
**(b)**
Suppose that \( P(x) \) is the product of two nonconstant
polynomials \( Q(x) \) and \( R(x) \) with integer coefficients. One of
these two polynomials, say \( Q \), has the constant term equal to \( \pm
p \). On the other hand, the zeros \( x_1,\dots,x_k \) of \( Q \) satisfy
\( |x_1|,\dots,|x_k|< \displaystyle p^{\frac1{p-1}} \) by part (a), and \( x_1\cdots
x_k=\pm p \), so we conclude that \( k\geq p \), which is impossible.