Irreducibility criteria

One method of determining whether a given polynomial in $\mathbb{Z}[x]$ is irreducible over $\mathbb{Z}$ is the following test.

Theorem 2.12.3 (Eisenstein's criterion)   If all the coefficients (except the leading coefficient) are divisible by a prime $p$, and the constant term coefficient is not divisible by $p^2$, then the polynomial is irreducible over $\mathbb{Z}$.

proof: Let $f(x)=a_nx^n+...+a_1x+a_0\in \mathbb{Z}[x]$ satisfy the hypotheses of the theorem. By assumption, $p\vert a_i$ for $0\leq i <n$, $p\not\vert a_n$, and $p^2\not\vert a_0$.

Suppose, to get a contradiction, that $f(x)=g(x)h(x)$, where $g(x)=b_kx^k+...+b_1x+b_0\in \mathbb{Z}[x]$, $h(x)=c_mx^m+...+c_1x+c_0\in \mathbb{Z}[x]$. Let $b_i=0$ if $i>k$ and $c_j=0$ if $j>m$. In general, we have

$$a_t=b_tc_0+b_{t-1}c_1+...+b_1c_{t-1}+b_0c_t.$$ (2.2)

In particular, $a_0=b_0c_0$. Since $p\vert a_0$ but $p^2\not\vert a_0$, we may assume without loss of generality that $p\vert b_0$ and $p\not\vert c_0$. Let $t$ be the smallest index such that $p$ does not divide $b_t$. We know $t\not= 0$. But then $p$ divides all but the first term of the right-hand side of (2.2) and $p$ divides the left-hand side. This is a contradiction. $\Box$

Example 2.12.4   Let $p(x)=2x^3+3x^2+9x+12$. By the Eisenstein criterion, $p(x)$ is irreducible.

Another method of determining whether a given polynomial in $\mathbb{Z}[x]$ is irreducible over $\mathbb{Z}$ is to use the following test.

Theorem 2.12.5   Given is a polynomial $f(x)$ of degree $n$ in $\mathbb{Z}[x]$. If there are $2n+1$ integers $k$ such that $f(k)$ is a prime number then then $f(x)$ is irreducible over the integers.

proof: If $f(x)=g(x)h(x)$, where $g,h\in \mathbb{Z}[x]$, then $f(k)$ prime implies $g(k)=\pm 1$ or $h(k)=\pm 1$. By the fundamental theorem of algebra, there are at most $2$deg$(g(x))$ solutions to $g(x)=\pm 1$ and at most $2$deg$(h(x))$ solutions to $h(x)=\pm 1$. $\Box$

Example 2.12.6   This is easy to implement on in a computer algebra system. For example, if we want to test $p(x)=x^3+3x+9$ (which fails the Eisenstein criterion) then out of the integers $k=1,2,...,16$, there are $7$ $k$'s such that $p(k)$ is a prime ( $k=1,2,5,7,10,11,16$). By the previous test, $p(x)$ is irredecible over the integers.

In 1857 Bouniakowsky conjectured that if $p(x)$ is an irreducible polynomial in $\mathbb{Z}[x]$ such that no number greater than $1$ divides all the values of $p(i)$ for every integer $i$, then $p(i)$ is prime for infinitely many integers $i$.