# A polynomial with prime values at $2n+1$ integers is irreducible

Suppose $f(x)$ is a polynomial with integer coefficients and degree $n\geq2$, and suppose $|f(x_i)|$ is prime for at least $2n+1$ integers $x_i$. Show that $f(x)$ is irreducible.

I have no idea.

Thanks.

## 2 Answers

Assume $f(x)=g(x)h(x)$, where $g(x),h(x)$ are polynomials of degree $m$ and $k$ respectively $\geq1$ with integer coefficients and $m+k =n$. Now the polynomials $g(x)+1,g(x)-1,h(x)+1$ and $h(x)-1$ can have atmost $m,m,k,k$ distinct integer roots, respectively. So there are at most $m + m + k + k = 2n$ $x_i$'s for which $|g(x_i)|$ or $|h(x_i)|=1$. Thus, if $f(x)$ is reducible, $|f(x)|$ will be prime for at most $2n$ integers $x_i$.

• WOW! nice solution, well put. +1. – user83461 Aug 18 '13 at 10:30

Suppose towards contradiction that $f$ is not irreducible, and write it as $f = g \cdot h$. Then $\deg(g) + \deg(h) = n$. Let $A = \{x : |h(x)| = 1\}$, and $B = \{x : |g(x)| = 1 \}$. Then $|A| \leq 2 \deg(h)$ and $|B| \leq 2 \deg(g)$, and hence $|A \cup B| \leq 2n$. Therefore, for any $2n+1$ integers, at least one of them is not in $A \cup B$, and for this value it holds that $|f(x)| = |g(x)h(x)|$ not prime. This contradicts the assumption that there are $2n+1$ integers $x_i$ such that $|f(x_i)|$ is prime.