# Proof that no polynomial with integer coefficients can only produce primes [duplicate]

Doing a discrete math review and am trying to solve problem 1.6 in the text found here: http://courses.csail.mit.edu/6.042/fall13/ch1-to-3.pdf - I believe I've gotten parts (a) and (b) correctly, but (c) is a bit tricky for me. Would appreciate a review of a/b and a hint for c if possible. Restatement here:

For n = 40, the value of polynomial $p(n)::=n^2 + n + 41$ is not prime, as noted in Section 1.1. But we could have predicted based on general principles that no nonconstant polynomial can generate only prime numbers.

In particular, let $q(n)$ be a polynomial with integer coefﬁcients, and let $c::=q(0)$ be the constant term of q.

(a) Verify that $q(cm)$ is a multiple of c for all $m \in Z$

Proof: Since q is a polynomial, it will be of the form: $q(x) = a_nx^n+a_{n-1}x^{n-1} + ... + a_1x + c$

If $x = cm$, then notice that cm will be inside every term of the polynomial, and since the final term is c, c can be factored out of every term. Hence, q(cm) is a multiple of c for all $m \in Z$.

b) Show that if q is nonconstant and c > 1, then as n ranges over the nonnegative integers, $N$, there are infinitely many $q(n) \in Z$ that are not primes.

Proof: Continuing from the result found in (a), it is easy to see that for all $m \in Z$, there will be an infinite number of multiples of c that will be generated by q. Since c > 1, these multiples are guaranteed not to be prime.

c) Conclude that for every nonconstant polynomial, q, there must be an $n \in N$ such that $q(n)$ is not prime. Hint: Only one easy case remains.

c = 0 is trivially easy to prove using the (b) above.

I assume the "easy" case is referring to c = 1, but in this case I'm not sure how to continue, since the result of (a) and (b) don't apply: I can't use them since adding 1 to any even number may make it prime. If the result of the terms not including c is odd, then adding 1 to that result makes it even and it is not prime. However, if the terms add up to an even number, I don't see a way of using the knowledge I have so far to prove conclusively that that number + 1 will NOT in fact be prime.

## marked as duplicate by user147263, graydad, Peter Woolfitt, Lord_Farin, André Nicolas polynomials StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 20 '15 at 17:12

• For $c=1$, consider $n=0$. $q(0)=1$ which is not a prime. – peterwhy Jun 1 '14 at 14:47
• @peterwhy I think it is being assumed that $n\ne 0$. – user142299 Jun 1 '14 at 14:50
• @NotNotLogical In part (b), $N$ is defined by "then as $n$ ranges over the nonnegative integers, $N$", and $0$ is a nonnegative integer. – peterwhy Jun 1 '14 at 14:51
• @peterwhy I always thought 1 was a prime number. Today I stand corrected. I assume that's why the text said it was the "easy" case... – DavidN Jun 1 '14 at 15:47
• @DavidN I am not really sure whether what I "proved" above is intended, and anyway there are some good proofs below. Just to complete my "proof", since a necessary condition for $x$ to be a prime number is $x>1$, for any polynomial $p(n)$ with $c\in\{1,0,-1,-2,\cdots\}$, $p(0) = c \le1$, which makes $p(0)$ not a prime. – peterwhy Jun 1 '14 at 16:04

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

• "If q(n) is prime for all n then q(0) = p is prime" - this I understand, but how does this imply your next statement? "and since p ∣ q(pn) and q(pn) is prime" - When have we established that p | q(pn)? Above, I was only able to establish that for c > 1. – DavidN Jun 1 '14 at 16:13
• @DavidN You proved that in part (a). – Bill Dubuque Jun 1 '14 at 16:19
• You're right. Nice proof by contradiction. – DavidN Jun 1 '14 at 21:19

I would argue differently, even allowing for the fact that $p(0) = \pm 1.$ First of all, if $p(x)$ is not a constant , then $p(n) \to \pm \infty$ as $n \to \infty,$ for if $p$ has degree $d$, say $p(x) = a_{d}x^{d} + \ldots + a_{1}x+ a_{0},$ then $\frac{p(x)}{x^{d}}$ tends to $a_{d}$ as $x \to \infty.$ Suppose that $p(n)$ is either $\pm 1$ or $0$, or $\pm$ (some prime) for every integer $n.$ Let $h$ be the smallest positive integer such that $p(h) \not \in \{-1,0,1 \}.$ There is such an integer $h$ by the earlier remark. Suppose that that $p(h) = \pm q$ for some prime $q.$ Then for every positive integer $t,$ we see easily that $p(h+qt)$ is divisible by $q.$ But for large enough $t,$ we see that $p(h+tq) \not \in \{,-q,0,q \},$ so that $p(h+tq)$ is not prime (and is not $\pm 1$ either).

• +1. I understand this answer as: for $p(n)$, find $p(h)$ such that $|p(h)|>1$ for some $h\ge0$ (and there must be some), shift the polynomial to $r(n):=p(n+h)$. $r(n)$ would still be a polynomial with integer coefficients, have a constant term $r(0)>1$, so there exists $r(n)$ that is not prime from part (b). And all values of $r(n)$ appear in $p(n)$... – peterwhy Jun 1 '14 at 15:51
• Almost, but not quite, what I meant: I set $r(n) = p(h+nq)$ in your terminology. – Geoff Robinson Jun 1 '14 at 16:07
• Right, and so using my interpretation and OP's result in part (a) "Verify that $r[r(0)\cdot m]$ is a multiple of $r(0)$ for all $m\in \mathbb Z$", I arrive at your form $r'(n):=r[r(0)\cdot n]=p(h+nq)$. – peterwhy Jun 1 '14 at 16:24
• Interesting answer - don't fully grok your argument yet but will go over it when I can. Thanks! – DavidN Jun 1 '14 at 21:21
• @DavidN: The key is that if we add a multiple of $q$ to $h,$ then we get the same image for $p(h+tq)$ in $\mathbb{Z}/q \mathbb{Z}$ as we do for $p(h).$ – Geoff Robinson Jun 1 '14 at 22:01