Prove that there is no polynomial $P(x) = a_n x^n + a_{n-1} x^{n-1} + \ldots + a_0 $ [duplicate]

From Putnam and Beyond. My question is, how does this proof work? I'd like to know more about the intuition behind its mechanics.

Prove that there is no polynomial $P(x) = a_n x^n + a_{n-1} x^{n-1} + \ldots + a_0 $, with integer coefficients and of degree at least 1 with the property that $P(0), P(1), P(2), \ldots ,$ are all prime numbers.

Solution:

Assume the contrary.
Let $P(0) = p$ with $p$ prime.
Then $a_0 = p$.
And $P(kp)$ is divisible by $p$ for all $k \geq 1$.
Because we assumed that all these numbers are prime, it follows that $P(kp) = p$ for $k \geq 1$.
Therefore, $P(x)$ takes the same value infinitely many times, a contradiction.
Hence the conclusion.

Solution 1:

Notice that since $a_0=p$ we have that

$$P(kp)=a_nk^n\cdot p^n+a_{n-1}k^{n-1}\cdot p^{n-1}+\dots + p$$

In other words, for each $k \in \mathbb{N}$, $P(kp)$ is a (finite) sum of multiples of $p$ (notice the powers of $p$ on each term). Hence, $P(kp)$ is divisible by $p$ for all $k \in \mathbb{N}$.

However, by hypothesis $P(kp)$ is prime for all $k \in \mathbb{N}$ (because $kp \in \mathbb{N}$ for all $k \in \mathbb{N}$).

In other words, we have that, for each $k \in \mathbb{N}$, $P(kp)$ is a prime that is divisible by $p$ (which is itself a prime). This means $P(kp)=p$ for all $k \in \mathbb{N}$, so $P$ takes the same value (the value $p$) infinitely many times.

Do you understand why this last bit (taking a value infinitely many times, for a polynomial) is a contradiction?

Solution 2:

There is an alternative proof provided by Hardy in his book "An Introduction To The Theory Of Numbers", Theorem 21, page 18