3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you please clarify the periodic behaviour of $f \mod p$? I don't follow, but I find the idea elegant. $\endgroup$ – Alex M. Apr 18 '15 at 19:31
  • 1
    $\begingroup$ @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)$. $\endgroup$ – Jack M Apr 18 '15 at 19:43
  • $\begingroup$ 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. $\endgroup$ – Alex M. Apr 18 '15 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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