# A problem regarding polynomials with prime values

The problem is as follows:

Prove that there is no non-constant polynomial $P(x)$ with integer coefficients such that $P(n)$ is a prime number for all positive integers $n$.

I cannot solve it. I can't even find the exact definition of a non-constant polynomial. Any help would be appreciated.

• Non-constant means it is not of the form $a_0$. It must have at least one term in $x$ or higher power. Apr 8 '16 at 10:20
• Assume $P(x)=a_nx^n+\dots+a_0$. The only tricky case is $a_0=\pm1$. Apr 8 '16 at 10:23
• @almagest Okay. So how do you suggest should I approach the proof? Apr 8 '16 at 10:24

Suppose a formula exists that produces primes for all positive integers, then $P(1)$ is prime, say $p$. Moreover, $P(1+np)\equiv 0 (\text{mod } p)$ for all natural numbers $n$. Since these values must all be prime, $P(1+np) = p$. There are infinitely many positive integers $n$ and therefore this is only possible if $P(n) = p$ for all $n\in\mathbb{N}$, which is a constant polynomial.
• Are negative primes $-p$ also considered to be prime? In that case, we could also have $P(1 + np) = p$ for certain values of $n$ and $P(1 + np) = -p$ for other values of $n$. Still, at least one of these situations will occur infinitely often, so the rest of the proof still works. (Perhaps it is assumed by OP that $P(x)$ is positive for every natural number $x$?) Apr 16 '16 at 22:07