# Polynomial irreducibility criterion

Given $f \in \mathbb{Z}[X]$ and $2\deg(f)+1$ distinct $a_i \in \mathbb{Z}$ such that $f(a_i)$ are prime numbers. Then $f$ is irreducible.

I'm trying to prove that and I am stuck. Any hints for a good starting point?

-
This is a classic theorem of Stackel $(1918).$ See my posts here for a hint, links, and more. – Bill Dubuque Jun 5 '12 at 22:29

Hint: Suppose $f=gh$ were a factorization where $g,h\in\mathbb{Z}[x]$ are not units (i.e. not equal to $\pm1$).
Because $f(a_i)=g(a_i)h(a_i)$ is a prime number for each $i$, we must have that either $g(a_i)=\pm1$ or $h(a_i)=\pm1$ for each $i$ (the signs might be different for different $i$).
Let $n=2\deg(f)+1$. WLOG, suppose $a_1,\ldots,a_k$ are the $a_i$ such that $g(a_i)=\pm1$, and $a_{k+1},\ldots,a_n$ are the $a_i$ such that $h(a_i)=\pm1$. Since $$2\deg(f)+1=2\deg(g)+2\deg(h)+1=n,$$ we have $$(2\deg(g)-k)+(2\deg(h)-(n-k))=-1$$ so that either $2\deg(g)< k$ or $2\deg(h)< n-k$.
Thanks!$\text{}$ – Zev Chonoles Jun 5 '12 at 21:34