5
$\begingroup$

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?

$\endgroup$

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
3
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\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.