# Primes and Polynomials: Elementary Number Theory Problem

Show that there does not exist any non-constant polynomial $p(x)$ with integer coefficients such that $p(x)$ is a prime number for all natural numbers $x$.

I'm not sure how to go about proving this.

• Can you find some relation between $f(x)$ and $f(x+q)$ for a prime $q$? – Daniel Fischer Sep 28 '16 at 13:06
• Please tell me if I'm on the right track here. If there did exist such a $p(x)$, then the final term (the constant term) in the polynomial would have to be prime. Say this term is $q$. But then $p(q)$ = $anq^{n} + .... + a1q + q$. We can factor out the $q$ and show that $q$ divides $p(q)$ and hence that $p(q)$ is not prime. – Wilson Brians Sep 28 '16 at 13:27
• Right track, but not quite complete yet. It can be that $q = p(0) = p(q) = p(2q) = \dotsc = p(kq)$, but since $p$ is not constant only for finitely many steps. Another point would be the definition of "natural numbers". If the definition with $0 \notin \mathbb{N}$ is used, we can't start with $p(0)$. Then start with $p(42)$ or $p(1)$ or whatever and look at $p(42 + m\cdot q)$ where $q = p(42)$. – Daniel Fischer Sep 28 '16 at 13:35
• There are some details to mop up, but you've got the right idea. – B. Goddard Sep 28 '16 at 13:35

If $a,b$ are two distinct integer numbers and $n\in\mathbb{N}$, we have $$(a-b)\mid (a^n-b^n)\tag{1}$$ hence it follows that for every polynomial $q(x)\in\mathbb{Z}[x]$, $$(a-b) \mid (q(a)-q(b))\tag{2}.$$ Assume that a polynomial $q(x)$ with degree $d$ takes a prime value, $p$, at $x=0$.
$(2)$ implies that $p$ is a divisor of $q(p),q(2p),q(3p),\ldots,q((2d+1)p)$. Assuming all these integers are primes, they all have to be $\pm p$, hence the polynomial $q(x)$ takes the same value ($+p$ or $-p$) at $d+1$ distinct points, and it is a constant polynomial. It follows that the only polynomials in $\mathbb{Z}[x]$ taking prime values for any $x\in\mathbb{Z}$ are the constant polynomials.
• @WilsonBrians: by the above argument, we have that any non-constant polynomial takes some composite value somewhere. However, that does not mean that any non-constant polynomial takes only a finite amount of prime values: just consider the case $q(x)=x$. – Jack D'Aurizio Sep 28 '16 at 15:27
• We have to consider that with the above assumptions we have $(2d+2)$ points, given by $0,p,2p,\ldots,(2d+1)p$, where our polynomial may take only values in $\{-p,+p\}$. It follows that our polynomial takes the same value, say $v$, in at least $d+1$ distinct points, so $q(x)-v$ is a polynomial with degree $d$ with $d+1$ distinct zeroes. It follows that $q(x)-v\equiv 0$, hence $q(x)$ is constant. – Jack D'Aurizio Sep 28 '16 at 15:30