2
$\begingroup$

This question already has an answer here:

There does not exist a polynomial $p(x)$ with integer coefficients which gives a prime number $\forall x\in \mathbb{Z}$

My attempt:

I defined a polynomial as $p(x)=a_0(x-a_1)(x-a_2)\ldots(x-a_n)$. So, whenever $x$ takes an integer value, the polynomial cannot generate a prime number unless the polynomial is a linear one. But I have serious doubts about this solution, suppose any factor is of the form $(x^2+x+1)$ which cannot be factorised into linear factors with integer coefficients. Please help. Thank you.

$\endgroup$

marked as duplicate by quid, Rory Daulton, Davide Giraudo, user2345215, user147263 Jan 31 '15 at 18:00

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.

8
$\begingroup$

Hint $\ $ If $\,f(n)\,$ is prime for all $\,n\,$ then $\,f(0) = p\,$ is prime, and since $\, p\mid f(pn)\,$ and $\,f(pn)\,$ is prime, then $\,f(pn) = p\,$ for all $\,n.\,$ Thus the polynomial $\,f(px)-p\,$ has infinitely many roots so is zero, i.e. $\,f(px) = p\,$ is constant, hence $\,f(x)\,$ is constant.

$\endgroup$
  • $\begingroup$ Just one doubt, if the polynomial is of the form $f(x)=ax+b$, then $p\nmid f(pn)$. $\endgroup$ – Swadhin Jan 31 '15 at 16:54
  • $\begingroup$ @Swadhin But we know $\,f(0) = p\ \ $ $\endgroup$ – Bill Dubuque Jan 31 '15 at 16:56
  • $\begingroup$ Yes, missed that, thank you very much, very elegant solution, thank you again. $\endgroup$ – Swadhin Jan 31 '15 at 16:59
2
$\begingroup$

Hint: If a polynomial, $p$ has integer coefficients, then for any integers $m,n$ with $m\ne n$, $n-m$ divides $p(n)-p(m)$.

Edit: (In response to comment):

One way to use this hint would be to note that for a polynomial that produces primes for all integers, we would have $p(0)=q$ for some prime $q$. But then $p(q)$ would be divisible by $q$, and so would $p(2q), p(3q),$ etc. But these values couldn't all be the prime $q$ since a polynomial takes any given value at most finitely many times. (I suppose the (trivial?) counterexample would be a constant polynomial whose constant value is a prime.)

$\endgroup$
  • $\begingroup$ I think you should say a bit more specifically how you can use that property here. $\endgroup$ – Bill Dubuque Jan 31 '15 at 16:57

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