# A computational criterion of irreducibility in $\mathbb Z[X]$?

If $$f\in\mathbb Z[X]$$ and there are $$x_1,\dots, x_n\in\mathbb Z_+$$, where $$n>\deg f$$, such that $$f(x_i)\in\mathbb P$$, $$i=1,\dots n$$, then $$f$$ is irreducible over $$\mathbb Z$$. Because, if $$\,f=g\cdot h$$ then either $$g(x_i)=1$$ or $$h(x_i)=1$$ which can't happen $$n>\deg g+\deg h$$ times.

But what about the opposite? Are there non constant, irreducible polynomials $$p\in\mathbb Z[X]$$ such that

$$x_1,\dots, x_n\in\mathbb Z_+$$ and $$p(x_i)\in\mathbb P$$ for all $$i=1,\dots,n$$ $$\:\implies\:$$ $$n\leq \deg p$$?

• I think this question is pleny interesting even without the $n \leq \deg p$ limitation. Just that there are only finitely many inputs that yield primes. – Arthur Dec 17 '18 at 9:13
• @Arthur: the limitation would be nice for an eventual computational test method. Else I agree. – Lehs Dec 17 '18 at 9:18
For example, if we take $$f(x)=x^3-x+3$$. It is an irreducible polynomial of degree $$3$$, and for each positive integer $$n$$, $$f(n)$$ is divided by $$3$$ ( By Fermat's little theorem). Since $$f(n)>3$$ when $$n>2$$, the only $$n$$ such that $$f(n)\in \mathbb{P}$$ is just $$1$$.
• I'm not sure, but it seems that the irreducibility of $f$ can be deduced from the method in en.wikipedia.org/wiki/Irreducible_polynomial#Over_the_integers as $f$ is irreducible over $\mathbb Z_2$. Is that correct? – Lehs Dec 17 '18 at 11:17