By the fundamental theorem of algebra, polynomials with complex coefficients always factor into linear factors in $\mathbb{C}[x].$ From this it follows that real polynomials factor into at most quadratic factors in $\mathbb{R}[x]$. However, in $\mathbb{Q}[x]$ and $\mathbb{Z}[x]$, irreducibility is much more interesting. By Gauss' lemma, irreducibility in both of them is the same thing, so we consider only $\mathbb{Z}[x]$ (every polynomial in $\mathbb{Q}[x]$ becomes a polynomial with integer coefficients when multiplied by a suitable integer).
In what follows, by polynomials we mean polynomials with integer coefficients in one variable and irreducibility is considered in $\mathbb{Z}[x]$, unless otherwise noted. In this post, we present a few methods to determine whether a polynomial is irreducible. For some reason, it seems that the Eisenstein criterion is almost the only irreducibility criterion that is truly well-known, even though it fails for many polynomials.
Polynomials producing too many small values
Let $f$ be a polynomial with integer coefficients having no integer zeros (so that there is a chance that $f$ is irreducible). Assume that $f(x)=g(x)h(x)$, where $g$ and $h$ are nonconstant polynomials. Then $|f(x)|$ can be smaller than a bound $M$, only when both $|g(x)|$ and $|h(x)|$ are smaller than $M$, and still there is no guarantee that $|f(x)|<M$. Therefore, intuition tells that if $f$ is small in too ''many'' integer points, it must be irreducible (unless it has integer roots). The definitions of ''small'' and ''many'' should of course depend at least on $\deg f$. This intuition can be formulated as several theorems. Natural examples of polynomials that are often small are $(x-a_1)...(x-a_n)\pm 1$, where $a_i$ are distinct integers; these polynomials are equal to $1$ or $-1$ in $n$ points. We start by showing that these are irreducible except in a few small cases.
Theorem 1. Let $a_1,...,a_n$ be distinct integers. Then the polynomials
\[f_1(x)=(x-a_1)...(x-a_n)-1\]
and
\[f_2(x)=(x-a_1)...(x-a_n)+1\]
are irreducible in $\mathbb{Z}[x]$, except $f_2$ is reducible if $n=2$ and $|a_1-a_2|=1$.
Proof. Suppose that $(x-a_1)...(x-a_n)\pm 1=g(x)h(x)$, where $g$ and $h$ are nonconstant. Without loss of generality, let $\deg g \leq \deg h$. We must have $g(a_i)=\pm 1$ for all $i=1,2,...,n$. We can say that $g(a_i)=1$ for $i\leq k$ and $g(a_i)=-1$ for $i>k$. We have $k<n$ as $\deg g<n.$ However, at least one of the equations $g(x)=\pm 1$ has no more than three solutions. To see this, suppose for example that $g(a_i)=1$ for $i\leq 4$. Then $g(x)=(x-a_1)(x-a_2)(x-a_3)(x-a_4)Q(x)+1$, and if this were equal to $-1$, we would obtain
\[(x-a_1)(x-a_2)(x-a_3)(x-a_4)Q(x)=-2.\]
The integers $x-a_i$ are ditinct, so this is a representation of $-2$ as a product of integers, at least four of which are distinct; this is absurd. Hence one of the equations $g(x)=\pm 1$ has at least $n-3$ solutions. The number of solutions is bounded by $\deg g$, so $n-3\leq \frac{n}{2}$, which implies $n\leq 6$.
Next assume $n=5$ or $n=6$. Then at least one of the equations $g(x)=\pm 1$ has at least three solutions. The other equation has at least two solutions as well; otherwise one of them has at least four solutions, and by the previous argument this means that one of the equations $g(x)=\pm 1$ has no solution $x=a_i$, a contradiction. Without loss of generality, write $g(x)=(x-a_1)(x-a_2)(x-a_3)Q(x)+1$. The equation $g(x)=-1$ must also have some integer solution, but then
\[(x-a_1)(x-a_2)(x-a_3)Q(x)=-2.\]
If we impose the ordering $a_1<a_2<a_3$, this happens only when $x-a_1=-1,x-a_2=1,x-a_3=2$. Therefore, the solution is unique, but there were supposed to be two of them; a contradiction.
The case $n=1$ is trivial, so we are left with the cases $n=2,3,4$. If $n=3$, then the polynomial $(x-a_1)(x-a_2)(x-a_3)\pm 1$ must have an integer root in order to be reducible, but this is impossible as $\pm 1$ is not the product of three distinct integers. If $n=2$, again $(x-a_1)(x-a_2)-1$ should have an integer root, but then $1$ is a product of two distinct integers, a contradiction. In the case of the polynomial $(x-a_1)(x-a_2)+1$, an integer root can occur, but only when $x-a_1=-1$, $x-a_2=1$ assuming $a_1<a_2$. Therefore $a_1=a_2+1$, and this was the exceptional case.
Finally, let $n=4$. By the argument for $n=3$, there cannot be linear factors, so $\deg g=2$ and we may assume $g(a_1)=g(a_2)=1, g(a_3)=g(a_4)=-1$ (but then we can no longer suppose an order for $a_i$). As $g$ is monic, we have $g(x)=(x-a_1)(x-a_2)+1$, and now
\[(a_3-a_1)(a_3-a_2)=-2, \quad (a_4-a_1)(a_4-a_2)=-2.\]
The $a_i$ are distinct, so $|a_i-a_j|\geq 4$ for some $i$ and $j$. By the equalities above, the only possibilities are $|a_2-a_1|\geq 4$ and $|a_4-a_3|\geq 4$. One of the numbers $|a_4-a_1|,|a_2-a_4|$ is $1$ and the other one is $2$, so by the triangle inequality $|a_2-a_1|\leq 1+2=3$, so the second case $|a_4-a_3|\geq 4$ must hold. The equalities above now have the form $AB=-2,(A+m)(B+m)=-2$, where $m=|a_4-a_3|\geq 4$. This implies $m(A+B)+m^2=0$, that is $A+B=-m$, but this cannot hold since one of $|A|,|B|$ is $1$ and the other one is $2$. ■
In the above proof, the usefullness of the abundance of small values taken by $f_1$ and $f_2$ is clearly visible, and as soon as $n$ is small (that is, there are ''not enough many'' points at whch $f_1$ or $f_2$ is small), the proof becomes a rather tedious case check. Pólya was able to define a notion of smallness for any polynomial such that small polynomials are irreducible. We follow Pólya's original paper Verschiedene Bemerkungen zur Zahlentheorie.
Theorem 2. Let $f$ be a polynomial of degree $n$ with integer coefficients. Let $m= \left\lfloor\frac{n+1}{2}\right\rfloor$. If there exist distinct integers $a_1,...,a_n$ with $0<|f(a_i)|<\frac{m!}{2^m}$ for all $i$, then $f$ is irreducible.
The proof is rather ingenious but elementary. The seemingly strange bound $\frac{m!}{2^m}$ actually arises naturally from the proof. We first need a lemma.
Lemma 3. Let $g(x)$ be a nonconstant real polynomial of degree $n$. If there exist $n+1$ distinct integers $b_0,...,b_{n}$ such that $|g(b_i)|<\frac{n!}{2^n}$ for all $i$, then $g(x)\not \in \mathbb{Z}[x].$
Proof. Let $g(b_i)=c_i$ for $i=0,...,n$. We may write $g$ in terms of these values using the Lagrange interpolation polynomial:
\[g(x)=\sum_{k=0}^{n}c_i\frac{\prod_{i\neq k}(x-b_i)}{\prod_{i\neq k}(b_k-b_i)}.\]
The leading coefficient of $g$ is
\[a=\sum_{k=0}^{n}c_i\frac{1}{\prod_{i\neq k}(b_k-b_i)}.\]
The numbers $\prod_{i\neq k}(b_k-b_i)$ are $n+1$ nonzero products of $n$ integers. As they are distinct, the largest one of them is at least $n!$ (since one of them has a number with absolute value at least $n$ as a term), the second largest is at least $1\cdot (n-1)!$, the third largest is at least $2(n-2)!$, and generally the $r$th largest is at least $r!(n-r)!$ since one of the terms in the product has absolute value at least $\max\{r,n-r\}$. Thus, by the assumption on the sizes of $c_i$, the leading coefficient of $g$ is bounded by
\[|a|<\sum_{r=0}^{n}\frac{1}{2^n}\frac{n!}{r!(n-r)!}=\frac{1}{2^n}\sum_{r=0}^n \binom{n}{r}=1,\]
so $g(x)\not \in \mathbb{Z}[x]$. ■
Proof of Theorem 2. Suppose $f$ is as in the theorem and that $f(x)=g(x)h(x)$ where $g$ and $h$ are nonconstant. Without loss of generality, let $\deg g\geq \deg h$. Then $\deg g\geq m=\left\lfloor\frac{n+1}{2}\right\rfloor.$ Since $0<|f(a_i)|<\frac{m!}{2^m}$ for all $i=1,...,n$, also $|g(a_i)|<\frac{m!}{2^m}$ for all $i=1,...,\deg g$. This means that the condition of the previous lemma is fulfilled, so $g(x)\not \in \mathbb{Z}[x]$, which is a contradiction. ■
As an application of Pólya's irreducibility criterion, consider the polynomials $a(x-a_1)...(x-a_n)+b$ where $a,b,a_i$ are integers and $a_i$ are pairwise distinct. By the criterion, this polynomial is irreducible whenever $|b|<\frac{m!}{2^m},$ where $m$ is as before. Since $m!\geq m^me^{-m}$, this holds if $|b|<\left(\frac{n}{2e}\right)^{\frac{n}{2}}$, which is a rather large range. Theorem 1 is also implied by Pólya's criterion for $n>6$.
Polynomials producing many or large primes
Next we consider another general principle for testing irreducibility. The principle simply states that if $f$ is a polynomial with integer coefficients that produces ''many'' primes (compared to the degree), then $f$ is irreducible. Similarly, if $f$ produces a ''large'' prime (in terms of its coefficients), $f$ is irreducible. We denote by $P(f)$ the number of distinct integers $x$ such that $f(x)$ is a prime or the negative of a prime. Then we have
Theorem 4. Let $f$ be a polynomial with integer coefficients of degree $n$. If $P(f)>n+4$, then $f$ is irreducible. On the other hand, for every $n>1$ there exists a reducible polynomial $f$ of degree $n$ with $P(f)\geq n$.
Proof. Assume $f(x)=g(x)h(x)$ where $g$ and $h$ are nonconstant. Let $a_1,a_2,...,a_{n+5}$ be such that $|f(a_i)|$ is prime. We may assume that $g(a_i)=\pm 1$ for $i\leq k$ and $h(a_i)=\pm 1$ for $k<i\leq n+5$.
An integer polynomial $Q$ of degree $d$ can have the values $\pm 1$ in at most $d+2$ points. Indeed, arguments in the proof of Theorem 1 have shown that if one of the equations $Q(x)=\pm 1$ has at least three solutions, then the other equation has no solutions. This means that either only one of the equations $Q(x)=\pm 1$ has solutions, in which case they have at most $d$ solutions in total, or both have, in which case one of them has at most $2$ and the other has at most $d$, giving the bound $d+2$.
Now we deduce $k\leq \deg g+2$ and $n+5-k\leq \deg h+2$, as $g(x)=\pm 1$ holds in $k$ points and $h(x)=\pm 1$ holds in $n-k$ points. Summing the inequalities, we get $n+5\leq \deg g +\deg h+4=n+4$, which is the desired contradiction.
We are left with proving that $P(f)\geq n$ for some reducible polynomial of degree $n$. We choose $f(x)=xh(x)$, where $h(x)=k(x-p_1)...(x-p_{n-1})+1$ with $p_1,...,p_{n-1}$ being distinct primes and $k$ being a suitable nonzero integer. We clearly have $f(p_i)=p_i$ for $i=1,2,...,n-1$. In addition, we choose $k$ in such a way that $k(1-p_1)...(1-p_{n-1})+1$ is prime (this is possible by Dirichlet's theorem, and we only need the special case that was proved using cyclotomic polynomials in this post). Then also $f(1)$ is prime, and we are done. ■
The result in Theorem 4 can be improved; it was proved by O. Ore in 1934 that $P(f)\geq n+3$ implies that $f$ is irreducible. The proof is still elementary but longer. It has been conjectured by Y. G. Chen, G. Kun, G. Pete, I. Z. Ruzsa and A. Timar that for any $n$ there is a reducible polynomial $f$ with $P(f)=n+2$, so Ore's criterion cannot be improved according to the conjecture.
Theorem 4 above can actually be used to prove the irreducibility of any irreducible polynomial in finite time if we assume the famous Bunyakovski's conjecture.
Conjecture (Bunyakovski). Let $f$ be an irreducible integer polynomial with positive leading coefficient such that there is no fixed prime dividing all the numbers $f(1),f(2),...$. Then $f(x)$ generates infinitely many primes as $x$ ranges through the positive integers.
In other words, the conjecture says that any polynomial that could potentially produce infinitely many primes does so. Testing whether $f(1),f(2),...$ have a fixed prime divisor is easy; for example, compute the gcd of $f(1)$ and $f(2)$, and if $d$ is this gcd, check whether any prime divisor of $d$ is a fixed divisor using modular arithmetic. Assuming the conjecture, we can prove the irreducibility of any irreducible polynomial $f$ of degree $n$ by computing $\tilde{f}(1),\tilde{f}(2),...$ ($\tilde{f}$ is $f$ divided by the greatest fixed divsor of $f(1),f(2),...$) until $n+5$ primes have been found in this list. Bunyakovski's conjecture tells that $n+5$ primes will eventually be found if $f$ is irreducible. In practice however, these prime values may be enormous and the theorems above do not tell how soon $n+5$ primes will be found. Also this test never proves the reducibility of a polynomial in finite time, but certainly the easiest way to do that is to determine a nontrivial factor for the polynomial.
There are also other ways to prove irreducibility with the help of primes. The following theorem is a beautiful way to construct irreducible polynomials.
Theorem 5. Let $p$ be a prime number and $b\geq 2$. Let $p=a_nb^n+...+a_1b+a_0$, $a_n\geq 1,a_{n-1}\geq 0, |a_i|\leq b-1$. Then the polynomial $a_nx^n+...+a_1x+a_0$ is irreducible.
For $b=10$, the theorem is due to A. Cohen (with nonnegative $a_i$), and J. Brillhart, M. Filaseta and A. Odlyzko proved the general case. The following simplified proof is due to M. Ram Murty. We will prove the cases $b>2$ as $b=2$ is more technical. We need a lemma on the location of zeros of an integer polynomial in the complex plane. In the end, it wíll be clear how this lemma helps in proving the theorem.
Lemma 6 (M. Ram Murty). Let $f(x)=a_nx^n+...+a_0$ be an integer polynomial with $a_n\neq 1, a_{n-1}\geq 0$ and $|a_i|\leq M$ for all $i$. Then if $\alpha$ is a zero of $f$, we have $\Re(\alpha)\leq 0$ or $|\alpha|<\frac{1+\sqrt{1+4M}}{2}$.
Proof. If $|\alpha|\leq 1$, then $|\alpha|<\frac{1+\sqrt{1+4M}}{2}$ holds automatically. If $a_{n-1}=0$, then
\[\begin{eqnarray}|f(x)|&=&|a_nx^n+a_{n-2}x^{n-2}+...+a_0|\geq |x|^n-M(1+|x|+...+|x|^{n-2})\\&>&|x|^n-\frac{|x|^{n-1}}{|x|-1}>0\end{eqnarray}\]
when $|x|\geq \frac{M}{|x|-1}$, and this is equivalent to $|x|\geq \frac{1+\sqrt{1+4M}}{2}$. If $a_{n-1}\geq 1$, then
\[\begin{eqnarray}|f(x)|&\geq& |a_nx^n+a_{n-1}x^{n-1}|-|a_{n-2}x^{n-2}+...+a_0|\\&>& |x|^n\Re(a_n+\frac{a_{n-1}}{x})-M\frac{|x|^{n-1}}{|x|-1}.\end{eqnarray}\]
When $Re(x)\geq 0$, also $\Re(x^{-1})\geq 0$ and
\[\begin{eqnarray}|f(x)|&>&|x|^n(1+\frac{1}{|x|})-M\frac{|x|^{n-1}}{|x|-1}\geq 0\end{eqnarray}\]
if $(1+\frac{1}{|x|})\geq M\frac{1}{|x|(|x|-1)}$, which holds if $1\geq \frac{M}{|x|(|x|-1)}$. This latter condition is equivalent to $|x|\geq \frac{1+\sqrt{1+4M}}{2}$, so we are done.
Proof of Theorem 5. Let $p$ be a prime, $b\geq 3$, $p=a_nb^n+...+a_0$, and let $f(x)=a_nx^n+...+a_0$, . Let $\alpha_1,...,\alpha_n$ be the complex roots of $f$, and suppose $f(x)=g(x)h(x)$ where $g$ and $h$ are nonconstant and $g$ is monic. Since $f(b)=p$, either $g(b)=\pm 1$ or $h(b)=\pm 1$. We may assume $g(b)=\pm 1$. Let $\alpha_1,...,\alpha_k$ be the complex roots of $g$. Now
\[g(b)=\prod_{j=1}^k(b-\alpha_j).\]
If $\Re(\alpha_j)\leq 0$, then $|b-\alpha_j|\geq b>1$. Otherwise, Lemma 6 with $M=b-1$ tells that $|\alpha_j|< \frac{1+\sqrt{4b-3}}{2}$, and this expression is at most $b-1$ for $b\geq 3$. Therefore, $|b-\alpha_j|>1$ in any case, so $|g(b)|>1$, which is a contradiction. ■
Theorem 5 also gives a method that will prove any irreducible polynomial to be irreducible in finite time, assuming Bunyakovski's conjecture. Indeed, let $f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0$, where we may assume $a_n>0$. We consider the polynomial $f_1(x)=Nf(x-\frac{a_n}{n})$, where $N$ is chosen so that the polynomial has integer coefficients. Clearly $f_1$ is irreducible iff $f$ is. The second highest coefficient of this polynomial is $0$. By dividing out the greatest common divisor of $f_1(1),f_1(2),...$, we get a polynomial $f_2$. If its coefficients are bounded by $M$, we compute $f(M+1),f(M+2),...$ until we find a prime. Bunyakovski's conjecture guarantees that a prime will be found, and Theorem 5 tells that this prime proves the irreducibility of $f$. However, again we have no bound on the size of this prime.
Irreducible polynomials in finite fields
An polynomial $f(x)\in \mathbb{Z}_p[x]$ is said to be irreducible $\pmod p$, where $p$ is a prime, if there is no representation $f(x)= g(x)h(x)$ with $g(x),h(x)\in \mathbb{Z}_p[[x]$. If $P$ and $Q$ are polynomials in $\mathbb{Z}_p[x]$, the equality $P=Q$ means that all the coefficients of $P$ and $Q$ agree $\pmod p$. The assumption that $p$ is a prime makes factoring polynomials unique in $\mathbb{Z}_p[x]$. It is good to remember that in $\mathbb{Z}_p[x]$ polynomials with the same values are not necessarily equal; for instance $x$ is irreducible in $\mathbb{Z}_p[x]$ although $x\equiv x\cdot x^{p-1}\pmod p$ for every $x\in \mathbb{Z}$ because the coefficients of degree $p$ are different for these polynomials $\pmod p$. Irreducibility $\pmod p$ can always be checked in finite time (If $f(x)\in \mathbb{Z}_p[x]$ is not irreducible, it is divisible by some polynomial in $\mathbb{Z}_p[x]$ with degree less than $\deg f$, and there are $p^{\deg f}$ such polynomials. There are of course more efficient methods, as we will see). Moreover, if $f$ is monic and reducible in $\mathbb{Z}[x]$, then it must be reducible in every $\mathbb{Z}_p[x]$, which is why reduction $\pmod p$ can be very helpful in proving irreducibility in $\mathbb{Z}[x]$.
Example. We show that $x^5+11x^2+15$ is irreducible in $\mathbb{Z}[x]$. Notice that in $\mathbb{Z}_2[x]$ this polynomial becomes $x^5+x^2+1$, so it suffices to show that this is irreducible. If it was not irreducible, it would have a linear or quadratic irreducible factor. It has no linear factor since it has no root $\pmod 2$; its values are always $1\pmod 2$. The only irreducible polynomial of degree $2$ in $\mathbb{Z}_2[x]$ is $x^2+x+1$. To see this, notice that there are $4$ polynomials of degree $2$, and those whose constant coefficient is $0$ are automatically reducible. Hence there are two possible irreducible polynomials, $x^2+1$ and $x^2+x+1$. We have $x^2+1=(x+1)^2$ in $\mathbb{Z}_2[x]$, while $x^2+x+1$ is divisible by neither $x$ nor $x+1$. We have $x^2+x+1\nmid x^5+x^2+1$ in $\mathbb{Z}_2[x]$ since $x^5+x^2+1=(x^2+x+1)(x^3+x^2)+1$ in $\mathbb{Z}_2[x]$.
The example above illustrates well how easy it is to prove irreducibility in $\mathbb{Z}_p[x]$ ; the example above shows that for a polynomial in $\mathbb{Z}_2[x]$ of degree at most $5$ it is enough to check if it has a root $\pmod 2$ or if it is divisible by $x^2+x+1$. Reduction $\pmod p$ also gives the well-known Eisenstein's irreducibility criterion.
Theorem 7 (Eisenstein). Let $f(x)=a_nx^n+...+a_1x+a_0$ be an integer polynomial. Assume that there is a prime $p$ such that $p\mid a_i$ for $i<n$, $p\nmid a_n$ and $p^2\nmid a_0$. Then $f$ is irreducible in $\mathbb{Z}[x].$
Proof. Assume $f(x)=g(x)h(x)$. Then in $\mathbb{Z}_p[x]$ we have $a_nx^n=\tilde{g}(x)\tilde{h}(x)$, where $\tilde{g},\tilde{h}$ are $g$ and $h$ with coefficients reduced $\pmod p$. By unique factorization in $\mathbb{Z}_p[x]$, we deduce $\tilde{g}(x)=bx^m, \tilde{h}(x)=cx^{n-m}$ for some $b,c,m$. In particular, $g(0)\equiv h(0)\equiv 0\pmod p$. However, then $p^2\mid a_0$, contrary to the assumption. ■
When Eisenstein's criterion works, it gives a simple way to prove irreducibility. For example, we applied in this post to the polynomials $\frac{x^p-1}{x-1}$ where $p$ is prime. In many cases, Eisenstein's criterion does not apply to $f(x)$ but to $f(x+a)$ instead for some $a$. However, there are many polynomials for which Eisenstein's criterion fails for all $a$ ad $p$. For example, the polynomial $x^4+8$ is irreducible in $\mathbb{Z}[x]$ as it has no linear factors or factors of the form $x^2+ax\pm 1$ or $x^2+ax\pm 2$, but $f(x+a)=x^4+4ax^3+6a^2x^2+4a^3x+a^4+8$, and the only prime that can divide both $a^4+8$ and $4a^3$ is $2$, but then $2\mid a$ and $2^2\mid a^4+8$, so Eisenstein's criterion does not work.
It may also be that $f(x)$ is irreducible in $\mathbb{Z}[x]$ but reducible in every $\mathbb{Z}_p[x]$. For example, if $f(x)=x^4+1$, then $f(x)=(x^2+1)^2$ in $\mathbb{Z}_2[x]$, and if $p$ is an odd prime, one of $-1,2$ and $-2$ is a quadratic redsidue $\pmod p$ (since $-1$ is a qudratic resdiue when $p\equiv 1 \pmod 4$, $2$ is a quadratic residue when $p\equiv \pm 1 \pmod 8$ and $-2$ is a quadratic residue when $p\equiv 1, 3\pmod p$). If $-1\equiv a^2\pmod p$, then $x^4+1=(x^2+a)(x^2-a)$ in $\mathbb{Z}_p[x]$. If $2\equiv a^2\pmod p$, then $x^4+x+1=(x^2+ax+1)(x^2-ax+1)$ in $\mathbb{Z}_p[x]$. If $-2\equiv a^2\pmod p$, then $x^4+1=(x^2+ax-1)(x^2-ax-1)$ in $\mathbb{Z}_p[x]$. In conclusion, $f$ is always reducible in $\mathbb{Z}_p[x]$.
Irreducibility of special polynomials
Of course, there are numerous principles in addition to the ones discussed above that can be used to prove irreducibility. To illustrate this, we prove that certain special classes of polynomials are irreducible.
Theorem 8. Let $p$ be a prime and $f(x)=a_nx^n+...+a_1x+p$ and integer polynomial with $p>|a_1|+...+|a_n|.$ Then $f$ is irreducible in $\mathbb{Z}[x]$.
Proof. Assume $f(x)=g(x)h(x)$ where $g$ and $h$ are nonconstant. Then $g(0)h(0)=p$, so without loss of generality $|g(0)|=1$. This means that the product of the complex roots of $g$ is $\pm 1$. In particular, $g(\alpha)=0$ for some $\alpha$ with $|\alpha|\leq 1$. However, by the triangle inequality, $|f(\alpha)|\geq p-|a_1|-...-|a_n|>0$, a contradiction. ■
The proof above contains the rather surprising idea of considering the complex roots of a polynomial, when we are actually interested in $\mathbb{Z}[x]$.
Theorem 9. Let $n>m>1$ be integers. Then $x^n+x^m+1$ is irreducible unless there exists $q$ such that $3m\equiv q \pmod{3q}, 3n\equiv -q\pmod{3q}$ or vice versa.
Proof. The idea of considering reciprocal polynomials is due to W. Ljunggren from this paper.
For a polynomial $f(x)=a_nx^n+...+a_1x+a_0$ (where $a_n\neq 0$), define its reciprocal as $\tilde{f}(x)=x^nf(x^{-1})=a_0x^n+a_1x^{n-1}+...+a_n$. Clearly $\tilde{fg}=\tilde{f}\tilde{g}$, and $\deg f=\deg \tilde{f}$ if $f(0)\neq 0$. We show that if $f(x)\in \mathbb{Z}[x]$ is reducible and $f(x)$ and $\tilde{f}(x)$ have no common roots, then there exists an integer polynomial $Q$ such that $f\tilde{f}=Q\tilde{Q}$ and $Q\neq \pm f, Q\neq \pm \tilde{f}$. In addition, if $f$ is monic and $f(0)=\pm 1$, we can take $Q$ to be monic. Assume $f(x)=g(x)h(x)$. Let $Q(x)=\pm g(x)\tilde{h}(x)$. Then $Q(x)\tilde{Q}(x)=g(x)\tilde{h}(x)\tilde{g}(x)h(x)=f(x)\tilde{f}(x)$. Since $f$ and $\hat{f}$ have no common roots, also $h$ and $\tilde{h}$ have no common roots, so $Q$ has a root that is not a root of $f$. Similarly, $Q$ has a root that is not a root of $\tilde{f}$. Thus $Q\neq \pm f, Q\neq \pm \tilde{f}$. If $f$ is monic, then $g$ and $h$ are also monic, and if $f(0)=\pm 1$, then $\pm g\tilde{h}$ is monic for either choice of sign.
Now let $f(x)=x^n+x^m+1$. Then $\tilde{f}(x)=x^n+x^{n-m}+1.$ These polynomials obviously have no common root, unless both have a root $\zeta$ such that $\zeta^{n-2m}=1$. Now $\zeta^n+\zeta^m=-1\in \mathbb{R}$, so $\zeta^n$ and $\zeta^m$ are conjugates (if $|v|=|w|=1,$ then the argument of $v+w$ is $\frac{\arg(v)+\arg(w)}{2}$). Now if $\zeta$ is a primitive $q$th root of unity, then $n\equiv -m\pmod q$. Since $n\equiv 2m\pmod{|n-2m|}$ and $q\mid |n-2m|$, we get $q\mid 3m$. We cannot have $q\mid m$, since then we would have $\zeta^n+2=0$, which is impossible. Now $\zeta^n+\zeta^m+1=\zeta^n+\omega+1,$ where $\omega$ is a nontrivial cube root of unity. Thus $\zeta^n=\omega^2$, so $n\equiv \pm \frac{q}{3} \pmod{q}$, and hence $3n\equiv \pm q \pmod{3q}$. If these conditions hold, then indeed $x^n+x+1$ is divisible by the minimal polynomial of $\zeta$ (which is the cyclotomic polynomial $\Phi_q(x)$, as $\Phi_q$ was shown to be irreducible in this post).
We may then assume that $f$ and $\tilde{f}$ have no common roots. If $f(x)$ were irreducible, we would have $f(x)\tilde{f}(x)=Q(x)\tilde{Q}(x)$ where $Q\neq \pm f, Q\neq \pm \tilde{f}$. Write $Q(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0$. Now the coefficient of $x^n$ in $Q(x)\tilde{Q}(x)$ is $\sum_{i=1}^n a_i^2$. The coefficient of $x^n$ in $f(x)\tilde{f}(x)$ is $3$. Thus $\sum_{i=1}^n a_i^2=3$, and as $a_n=1$, we must have $Q(x)=x^n+x^a+1$ ($Q(x)$ is not divisible by $x$ since $f(x)\tilde{f}(x)$ is not). Hence
\[(x^n+x^m+1)(x^n+x^{n-m}+1)=(x^n+x^a+1)(x^n+x^{n-a}+1).\]
By symmetry, we ay assume $a\leq n-a$. If $a<\frac{n}{2}$, comparing the coefficients, we see that $a=m$ or $a=n-m$, which is a contradiction. Therefore $a=\frac{n}{2}$, and then $2x^n=x^{m}+x^{n-m}$, so $m=\frac{n}{2}$, and again we have a contradiction. ■
The polynomials $x^n+x^m+1$ are a particular case of 0,1 polynomials, which have all their coefficients equal to $0$ or $1$. They are interesting because of their simple form, but yet nontrivial properties. For example, it has been conjectured that almost all 0,1 polynomials are irreducible, but this is an open problem. In the next example, reduction $\pmod p$ will be crucial in the proof.
Theorem 10. Let $p$ be a prime and $a$ and integer with $p\nmid a$. Then $x^p-x+a$ is irreducible.
Proof. These polynomials are the famous Artin Schreier polynomials which are the basis of an entire theory. We show that $f(x)=x^p-x+a$ is actually irreducible in $\mathbb{Z}_p[x]$. Let $F$ be an extension field of $\mathbb{Z}_p$ in which $f$ splits into linear factors. It is well-known that $F$ is a finite field in which $px=0$ for all $x\in F$. Let $\alpha$ be a root of $f$. Then $(\alpha+1)^p-(\alpha+1)+a=0$ by Fermat's little theorem, so the roots of $f$ are $\alpha+k,$ $k=0,1,...,p-1$. We have $\alpha \not \in \mathbb{Z}_p$, since otherwise $\alpha^p-\alpha+a=a$ in $\mathbb{Z}_p$. Now suppose $f(x)=g(x)h(x)$ in $\mathbb{Z}_p[x]$ where $g(x),h(x)\in \mathbb{Z}_p[x]$ are nonconstant. We may assume that $g$ is monic, so
\[g(x)=\prod_{k\in S}(x-\alpha-k),\]
where $S\subset \mathbb{Z}_p$. However, the coefficient of $x^{|S|-1}$ in $g(x)$ is $-\sum_{k\in S}(\alpha+k)$. This should be in $\mathbb{Z}_p,$ so $|S|=p$, which means that $h$ is constant, a contradiction. ■
