# Proof of lack of pure prime producing polynomials.

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?

-
Note, there is a multiple variable polynomial whose positive values are all the primes: en.wikipedia.org/wiki/Formula_for_primes (but it has some garbage negative values) –  user58512 Feb 14 '13 at 21:46
I'm almost certain this has been answered at least a couple times before, but I had no luck locating the prior posts. Anyone? –  Math Gems Feb 14 '13 at 23:07

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.

-

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.

-
Thanks for the answer! Only one thing to point out: when the leading coefficient is negative, we know that for $x$ sufficiently large, $P(x)<0$, which cannot be a prime. :) –  Bill Liu Oct 26 '14 at 12:32
You are elcome. Sometimes, particularly if one is algebraic number theory minded, something like $-13$ is considered prime. That's why at the beginning I said ithout loss of generality we can take the lead coefficient positive. –  André Nicolas Oct 26 '14 at 15:15