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?


marked as duplicate by Watson, Community Nov 26 '18 at 16:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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) $\endgroup$ – user58512 Feb 14 '13 at 21:46

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.

  • $\begingroup$ 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. :) $\endgroup$ – Zz'Rot Oct 26 '14 at 12:32
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Oct 26 '14 at 15:15
  • $\begingroup$ @AndréNicolas I have a similar question and I would be very thankful if you could help me. Let $f$ be a polynomial function, with integer coefficients, strictly increasing on $\Bbb N$ such that $f(0)=1$. Show that it doesn't exist any arithmetic progression of natural numbers with ratio $r>0$ such that the value of function $f$ in every term of the progression is a prime number. I managed to adapt my question to your answer, but I can't see how I could use de fact that $f(0)=1$. Thank you so much! $\endgroup$ – I. Stefan May 17 '16 at 16:34
  • $\begingroup$ I will be busy for quite a while today. I remember seeing your question and assumed it would be quickly answered. Will look it up and if it is unanswered I will try to answer it. I assume you mean common difference greater than $0$, not ratio, which is a term used for geometric progressions. The assumption that $f(0)=1$ is irrelevant, the result can be proved without it. $\endgroup$ – André Nicolas May 17 '16 at 16:46
  • $\begingroup$ I looked at your question, it has a good answer already. Let your AP be numbers $a+nr$. If $f$ were prime at all $a+nr$, then $g(x)=f(a+rx)$ would be prime for all positive integers. But my proof bove, or any other standard proof. shows that $g(x)$ must be composite for some (indeeded infinitely many) integers $x$. $\endgroup$ – André Nicolas May 17 '16 at 17:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.