# Show that no non-constant polynomial can generate only prime numbers

This problem is taken from "Mathematics for Computer Science" (Lehman, Leighton, Meyer, 2018).

# Problem

For $$n = 40$$, the value of the 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 non-constant polynomial can generate only prime numbers.

In particular, let $$q(n)$$ be a polynomial with integer coefficients, 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 \mathbb{Z}$$.

(b) Show that if $$q$$ is nonconstant and $$c > 1$$, then as $$n$$ ranges over the nonnegative integers $$\mathbb{N}$$ there are infinitely many $$q(n) \in \mathbb{Z}$$ that are not primes. Hint: You may assume the familiar fact that the magnitude of any nonconstant polynomial $$q(n)$$ grows unboundedly as $$n$$ grows.

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

# Solution attempt

(a) The polynomial can be expressed as $$q(n) = c + a_1n + a_2n^2 + \cdots + a_kn^k$$. So, $$q(cm) = c + a_1cm + a_2c^2m^2 + ... + a_kc^km^k$$. Since all terms of $$q(cm)$$ are divisible by $$c$$, $$q(cm)$$ is a multiple of $$c$$ for all $$m \in \mathbb{Z}$$.

(b) As $$n$$ ranges over the nonnegative integers, it will range over infinitely many values of the form $$n=cm$$ ($$m \in \mathbb{Z}$$). As shown in (a), for each $$n=cm$$, $$q(cm)$$ is a multiple of $$c$$. Therefore, assuming that the magnitude of $$q(n)$$ grows unboundedly as $$n$$ grows, this means that $$q(n)$$ will take infinitely many non-prime values.

(c) Item (b) covered the cases where $$c > 1$$. For nonconstant $$q$$, two cases remain: $$c < -1$$ and $$-1 \leq c \leq 1$$.

• For $$c < -1$$, a similar argument to (b) applies: as $$n$$ ranges over the negative integers, it will range over infinitely many values of the form $$n=cm$$ (where $$m$$ is a negative integer). For each of these values, $$q(n)$$ is a multiple of $$c$$. Therefore, assuming that the magnitude of $$q(n)$$ grows unboundedly as $$n$$ grows, this means that $$q(n)$$ will take infinitely many non-prime values.

• For $$c -1 \leq c \leq 1$$, $$q(0) = c$$ is an example of root that is not prime.

Therefore, for every nonconstant polynomial $$q$$, there must be an $$n \in \mathbb{N}$$ such that $$q(n)$$ is not prime.

Is this proof correct?

• You handle the cases $c=\pm 1$ by arguing that $\pm 1 =p(0)$ is not prime. That's ok, but in discussing this result it is more common to prove that $p(n)$ takes on infinitely many composite values. After all, a polynomial that took on only prime values for sufficiently large $n$ would be almost as useful as one which only took on prime values. You've almost done that, but you still have to show this in the case $c=\pm 1$.
– lulu
Commented Feb 19, 2020 at 12:58
• this duplicate and others you can easily find by searching might give you ideas if you get stuck on that last detail.
– lulu
Commented Feb 19, 2020 at 13:00
• A different approach. If $q(x)$ produces only prime numbers then $q(x+1)$, which can be written $q(x+1)=xp(x)+q(1)$ for some $p(x)$, produces only prime numbers. Compute $q(nq(1)+1)$ and use the fact that $q(1)$ is a prime to conclude. Commented Feb 19, 2020 at 16:43
• @lulu isn't it mentioned in part C that n belongs to only set of natural numbers? How can we put n=0 there?
– Alex
Commented Aug 20, 2021 at 6:17
• @Alex Many people, including (apparently) the OP, say that $0\in \mathbb N$. But, really, the important point here is that the goal is to show that $p(n)$ is composite for infinitely many natural numbers...not to just find a single composite $p(n)$.
– lulu
Commented Aug 20, 2021 at 10:44