Proof of lack of pure prime producing polynomials. [duplicate]

I recently encountered this following proposition:

For every polynomial, there is some positive integer for which it is composite.

What is the most elementary proof of this?

Solution 1:

Not quite true, look at the polynomial $17$. And the usual theorem specifies that the polynomial has integer coefficients.

Let $P(x)$ be a non-constant polynomial with integer coefficients. Without loss of generality we can assume that its lead coefficient is positive.

It is not hard to show that there is a positive integer $N$ such that for all $n\ge N$, we have $P(n)\gt 1$, and such that $P(x)$ is increasing for $x\ge N$. (For large enough $x$, the derivative $P'(x)$ is positive.)

Let $P(N)=q$. Then $P(N+q)$ is divisible by $q$. But since $P(x)$ is increasing in $[N,\infty)$, we have $P(N+q)\gt q$. Thus $P(N+q)$ is divisible by $q$ and greater than $q$, so must be composite.

Remark: One can remove the "size" part of the argument. For any $b$, the polynomial equation $P(x)=b$ has at most $d$ solutions, where $d$ is the degree of $P(x)$. So for almost all integers $n$, $P(n)$ is not equal to $0$, $1$, or $-1$.

Let $N$ be a positive integer such that $P(n)$ is different from $0$, $1$, or $-1$ for all $n\ge N$. Let $P(N)=q$. Consider the numbers $P(N+kq)$, where $k$ ranges over the non-negative integers. All the $P(N+kq)$ are divisible by $q$. But since the equations $P(n)=\pm q$ have only finitely many solutions, there is a $k$ (indeed there are infinitely many $k$) such that $P(N+kq)$ is not equal to $\pm q$, but divisible by $q$. Such a $P(N+kq)$ cannot be prime.

I prefer using considerations of size.

Solution 2:

Suppose $P$ is a polynomial, then it is periodic mod $m$: I mean $P(a) = P(a+m) \pmod m$.

Suppose it takes on different prime values like $p$ and $q$.

Then $P(x) \equiv 0 \pmod p$ for some $x$, and $P(y) \equiv 0 \pmod q$ for some $y$. By periodicity we can find a $z$ such that $pq|P(z)$ using periodicity.