# Prove there exists $m > 2010$ such that $f(m)$ is not prime

Let $$f(x) = \sum_{i = 0}^n a_ix^i$$ be a polynomial with $a_i \in \mathbb Z, n > 0, a_n \neq 0$. Prove that there exists some natural number $m>2010$ such that $|f(m)|$ is not a prime number.

I tried to look at $f(m) \bmod m$, and I assumed $m$ is relatively prime to $a_0$, so $f(m)$ is reversible $\mod m$, but I didn't know how to continue to prove it is not a prime number.

I would like to get help with that. Thanks.

let $k=f(m)+m$ you can prove that : $$f(k)\equiv 0 \mod f(m)$$

In order to $f(k)$ to be prime we must have $f(k)=f(m)$ or $f(m)=1$, But $f(f(m)+m)-f(m)$ and $f(m)-1$ are two polynomials which have only finitely roots so there exists $x\geq A$ ($A$ any number you want) such that $f(k)\neq f(m)$ and $f(m)\neq 1$

Theorem 21 in Hardy and Wright's book on number theory reads

No polynomial $f(n)$ with integral coefficients, not a constant, can be prime for all $n$, or for all sufficiently large $n$.

The proof goes as follows. Replacing $f$ by $-f$ we may assume $f(n) \to \infty$ with $n$. So for some $N$, we know that $n > N$ implies $f(n) > 1$. Fix $x > N$. Then let $$y = f(x) = a_n x^n + \dotsb a_1 x + a_0.$$ Then $y > 1$. Now, for integral $r$, every value $f(x + ry)$ is bigger than one and divisible by $y$ by the binomial theorem. Since $x + ry$ grows arbitrarily large with $r$, you can find your $m > 2010$.

As pointed out in the other answers, the point is that there is no single-variable polynomial with integer coefficients which takes on only prime values - apart from constant polynomials. My preferred proof is:

Suppose $f(x)$ is prime for all positive integer $x$. Take any value of $f$, say $p=f(1)$. The behavior of $f$ modulo $p$ is periodic, so since $f(1)$ is zero modulo $p$, there are infinitely many $x$ such that $f(x)$ is zero modulo $p$. But they can't all be $p$ itself, since a polynomial can't take on the same value infinitely many times (for a couple of reasons - first because of growth rates, and second because $f(x)-p$ would be a polynomial with infinitely many roots).

Note that the simple statement that $f(x)$ is not prime for all $x$ is not enough to claim that it's not prime for all $x$ above a certain bound, but if you understand how the above proof works it's not hard to see that that's true as well.

• Could you please clarify the periodic behaviour of $f \mod p$? I don't follow, but I find the idea elegant. – Alex M. Apr 18 '15 at 19:31
• @AlexM. It's simply that modulo anything, congruence is compatible with addition and multiplication. So if $x\equiv y$, then $x^k\equiv y^k$, $a_kx^k\equiv a_ky^k$, and $f(x)\equiv f(y)$. – Jack M Apr 18 '15 at 19:43
• Oh, you mean that the period is $p$ itself? Then yes, it is trivial, I was expecting something complicated... It is obvious, I don't know why I haven't seen it. – Alex M. Apr 18 '15 at 19:46