# Proof of Cohn's Irreducibility Criterion

I was looking for an elementary (or involving introductory level abstract algebra/analysis) proof of Cohn's Irreduciblity Criterion:

If $$a_0, a_1, \dots, a_n \in \Bbb{Z}$$ and $$0 \le a_i \le t$$ and $$a_0 + a_1t + a_2t^2 +\cdots + a_nt^n \in \{ \text{Primes} \}$$ then the polynomial $$a_0 + a_1 x + a_2 x^2 +\cdots+ a_nx^n$$ is irreducible.

I began to plot out a proof. Assume that we have a polynomial that does evaluate to a prime for some $t$ satisfying the inequalities above. Then it follows, that if this polynomial is factorable, it would be factored into

$$(b_0 + b_1x + b_2x^2 + \cdots+ b_rx^r )(c_0 + c_1x + c_2x^2 + \cdots+ c_jx^j)$$

Whereas Without loss of generality we can assume

$$c_0 + c_1t + c_2t^2 + \cdots+ c_jt^j = \pm P$$

(the prime in question is $P$)

$$b_0 + b_1t + b_2t^2 + \cdots+ b_rt^r = \pm 1$$

From here I am not clear how to proceed.

## Another Idea:

We can try to do something with induction. Lets start with the base case of the polynomial $b_0 + b_1x +\cdots$ being linear

$$b_0 + b_1 t = 1$$

Tells us that $$t = \frac{1 - b_0}{b_1}$$

But since $b_0 \ge 0, b_1 \ge 0 , t \ge 0$ it follows that $b_0 = 0$ (but then the value P never could have been prime since it would be divisible by t)

So we conclude that the polynomial has no linear factors that way. On the flip side it could be that

$$b_0 + b_1 t = -1$$

$$t = \frac{-1-b_0}{b_1}$$

Theres no $b_0 > 0$ that can make this expression greater than 0. So this case is covered.

Thus we conclude there are NO linear factors.

But I have no idea how to generalize this technique in a way that knocks out other polynomials too. especially given that from degree $5$ onwards there isn't even an algebraic formula for me to work with, expressing $t$.

• The proof from this paper seems fairly elementary.
– A.P.
Jul 27, 2015 at 15:25
• How about this polynomial $p(x)=x^3-8x^2+26x-33$, $p(4) =7$ and $p(x) = (x-3)(x^2 -5x+11)$. It is a counter example Jul 27, 2015 at 15:25
• $t$ is $10$ not an arbitrary number... Jul 27, 2015 at 15:27
• @AmerYR It was shown that t need not be 10. As long as t is greater than all the coefficients and coefficients greater than 0. Your example has 2 negative numbers (not allowed). And needs to be evaluated for $t >26$ Jul 27, 2015 at 15:29
• sorry my bad .hehe Jul 27, 2015 at 15:31

I suggest the following solution:

But first, we need the following lemma:

Lemma 1

For all polynomial $$P(x)=a_nx^n+a_{n-1}x^{n-1} + \cdots + a_1x+a_0 \in \mathbb{C[x]}$$, if $$z$$ is a solution of the polynomial then \begin{align} |z| \le 1+ \max\{\frac{a_i}{a_n}|i\in\{0,1,2,\cdots,n\}\} \end{align}

I will leave this as an exercise for whoever reading this.

Now back to the problem

Solution

If $$P(x)$$ is reducible over $$\mathbb{Q[x]}$$, then it is reducible over $$\mathbb{Z[x]}$$, according to Gauss lemma.

hence, $$P(x)=H(x) \times Q(x)$$

Thus $$P(10)=H(10)Q(10) \in \mathbb{P}$$

So either $$|H(10)|=1$$ or $$|Q(10)|=1$$. Assume it's $$H(x)$$.

Denote $$z_1,z_2, \cdots, z_k$$ be the solutions of $$H(x)$$. Then,

$$\begin{cases} |z_i| \le 1+\frac92 \\ H(10)=\alpha (10-x_1)(10-x_2)\cdots(10-x_k) \end{cases}$$

But then $$|H(10)|\ge\alpha\times(\frac{11}{2})^k >1$$, a contradiction.

Hence we have QED. $$\square$$.

This is the base t expansion of a number, which is of course unique. Now if the polynomial factors it must factor as P*1.
Since 1 has a unique base t expansion it must be that one of the polynomials is 1, hence the other is our given polynomial. So our polynomial does not factor. -M

• Why is it that the factors need to be expansions? I agree that the polynomial itself is a unique expansion, but how do I know that the factors themselves won't have negative terms and other funky business making -1 a possible factor Jul 27, 2015 at 16:24
• If -1 is a factor then the other factor is -P. Jul 27, 2015 at 17:05
• Okay so you can divide out -1 from both factors (which cancels), so we only need to check a polynomial = 1. But that still doesn't fix the problem. We don't have any reason to believe that the polynomial factors themselves will be base t expansions. Meaning given that we wish to check Jul 27, 2015 at 17:10
• $$a_0 + a_1 x + ... a_nx^n$$ where $0 \le a_i \le t$. And if it factors we assume it factors into $$b_0 + b_1x +... b_rx^r \times c_0 + c_1x + ... + c_jx^j$$ why should I believe that $0 \le b_i \le t$ and $0 \le c_i \le t$. That is not immediately clear to me. Jul 27, 2015 at 17:11
• @frogeyedpeas Indeed, in general it doesn't happen. For example $x^3 + 1$ factors as $(x^2 - x + 1) (x + 1)$.
– A.P.
Jul 27, 2015 at 18:13