A Prime-Generating Polynomial

Solution

Suppose such polynomial exists, with degreen n > 0:

P(x) = a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀

with P(k) prime for all k = 0, 1, 2, ...

Now a_n = P(0), so it's a prime; let it be p.

Now observer that P(ip) is a multiple of p for every i = 0, 1, 2, ... since p divides each term of the polynomial.

But these numbers P(ip) for i = 0, 1, 2, ... are also primes. The only way that they can be prime and a multipe of p is for them to equal p. Thus P(ip) = p for i = 0, 1, 2...

Now consider the polynomial Q(x) = P(px) - p. Q(x) is also of degree n, and has infinitely many roots (it has a root at every non-negative integer x = 0, 1, 2, ...). But this is a contradiction: a polynomial of degreen n has at most n roots. Hence there can't be a polynomial P(x) for which P(k) is prime for all k = 0, 1, 2, ...