Nonexistence of a Prime-valued Non-constant Polynomial With Integer Coefficients

Consider the following polynomial:

\[q(x) = x^2 + x + 41.\]

It is easy to see that $q(x)$ is prime for each integer $x \in \{-40, -39, \ldots, -1, 0, 1, \ldots, 39, 40\}$.

Motivated by this observation, we can ask the following question:

Does there exist a polynomial $q(x)$ with integer coefficients whose values are primes for every integer $x$ ?

The answer is: YES!

In fact, we can take the polynomial $q(x) = p$, where $p$ is a prime.

Let us modify the above question slightly:

Does there exist a non-constant polynomial $q(x)$ with integer coefficients whose values are primes for every integer $x$ ?

This time, the answer is: NO!

Why ?

Let us prove this.

Assume that $q(x)$ is a non-constant polynomial and is prime for every integer $x$. Then $q(0)$ is prime. Let $q(0) = p$. Now there are infinitely many integers $a$ such that $a \equiv 0 \pmod p$. Then by the theory of congruences, $q(a) \equiv q(0) \pmod p$ which says that $q(a) \equiv 0 \pmod p$. Hence $p | q(a)$. Since $q(a)$ is a prime, it follows that $q(a) = p$. Thus the polynomial $f(x) = q(x) - p$ has infinitely many roots which is impossible, since a non-constant polynomial $f(x)$ with degree $n$ can have at most $n$ roots. Therefore, the polynomial $q(x)$ with the desired properties cannot exist.