1
$\begingroup$

The problem is as follows:

Prove that there is no non-constant polynomial $P(x)$ with integer coefficients such that $P(n)$ is a prime number for all positive integers $n$.

I cannot solve it. I can't even find the exact definition of a non-constant polynomial. Any help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ Non-constant means it is not of the form $a_0$. It must have at least one term in $x$ or higher power. $\endgroup$ – almagest Apr 8 '16 at 10:20
  • 1
    $\begingroup$ Assume $P(x)=a_nx^n+\dots+a_0$. The only tricky case is $a_0=\pm1$. $\endgroup$ – almagest Apr 8 '16 at 10:23
  • $\begingroup$ @almagest Okay. So how do you suggest should I approach the proof? $\endgroup$ – SinTan1729 Apr 8 '16 at 10:24
7
$\begingroup$

There are still some gaps, but I'd suggest something like the following. There must be quite a few other approaches, I'd expect, and I hope others will provide some of these.

Suppose a formula exists that produces primes for all positive integers, then $P(1)$ is prime, say $p$. Moreover, $P(1+np)\equiv 0 (\text{mod } p)$ for all natural numbers $n$. Since these values must all be prime, $P(1+np) = p$. There are infinitely many positive integers $n$ and therefore this is only possible if $P(n) = p$ for all $n\in\mathbb{N}$, which is a constant polynomial.

$\endgroup$
  • $\begingroup$ I think this is pretty much sufficient. $\endgroup$ – SinTan1729 Apr 8 '16 at 10:38
  • 1
    $\begingroup$ Are negative primes $-p$ also considered to be prime? In that case, we could also have $P(1 + np) = p$ for certain values of $n$ and $P(1 + np) = -p$ for other values of $n$. Still, at least one of these situations will occur infinitely often, so the rest of the proof still works. (Perhaps it is assumed by OP that $P(x)$ is positive for every natural number $x$?) $\endgroup$ – Josse van Dobben de Bruyn Apr 16 '16 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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