Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was told to assume $f(x)$ is a polynomial with degree $d\geq 1$ with integer coefficients and positive leading coefficient.

(i) I need to show that there are infinitely many $x$ such that $f(x)$ isn't prime.

(ii) I also need to show that if $f(x_0) = m$, where $m>0$, then $f(x) \equiv 0 \pmod m$ whenever $x\equiv x_0 \pmod m$.

I tried (ii) and so far I have
If $f(x_0) = m \neq 0 \pmod m$, we have $x \equiv x_0 \pmod m$ so then $f(x) \equiv 0 \pmod m$.

For (i) I am not sure where to start can someone give me an idea?

share|cite|improve this question

For (i), prove first that there is an $N$ such that $f(x)$ is increasing in the interval $(N,\infty)$, and greater than $1$. Now suppose $a\gt N$ and $f(a)=m$. Then $f(a+m)\gt m$, and $f(a+m)$ is divisible by $m$.

Note that we used the fact (ii) that you were asked to prove. For the proof of (ii), use the fact that if $a\equiv a'$ and $b\equiv b'$ (both modulo $m$) that $a+b\equiv a'+b'$ and $ab\equiv a'b'$.

share|cite|improve this answer

OK, so we have the useful lemma that for integers $a,b$ we have $(a-b)|(f(a) - f(b))$. This follows essentially from the fact that $(a-b)|(a^n - b^n)$ for any $n$. This is why $f(x) \equiv 0 \pmod{m}$ whenever $x \equiv x_0 \pmod{m}$.

Now, how does this help with part i)? Suppose the conclusion is false, so for some $M$ we have $x > M \implies f(x)$ is prime. Remark that for all $x \equiv M+1 \pmod{f(M+1)}$, we have $f(M+1)|f(x)$ so for $x > M, x \equiv M+1 \pmod{f(M+1)}$ we have $f(x) = f(M+1)$. But then for infinitely many values $f$ is the same value, which is a contradiction if $f$ is nonconstant so we are done.

share|cite|improve this answer

For (ii) note that $(x_0+km)^n=x_0^n+{n\choose 1}x_0^{n-1}m+{n\choose 2}x_0^{n-2}m^2+\ldots +m^n = x_0^n+m\cdot(\ldots)$, therefore in general $f(x_0+km)\equiv f(x_0)\pmod m$.

There are at most finitely many $x$ with $f(x)=0$, so we can pick $x_0$ such that $m:=f(x_0)\ne 0$. Among the infinitely many $x=x_0+km$, for which we already know $f(x+km)\equiv 0\pmod m$, there are at most finitely many with $f(x)=0$, finitely many with $f(x)=m$, $f(x)=-m$. Therefore, we find $x_1$ with $m-1:=f(x_1)$ a multiple of $m$ $\notin\{-m,0,m\}$. Especially, $|m_1|\ge 2$. From there, we similarly find a number $x_2=x_1+km_1$ for some $k$, such that $f(x_2)\equiv 0\pmod {m_1}$ and $m_2:=f(x_2)\notin\{-m_1,0,m_1\}$. Therefore $m_2$ is composite ($m_1$ is a nontrivial factor - nontrivial because neither $|m_1|=1$ nor $|m_1|=|m_2|$). Now $f(x_2+km_2)$ is a multiple of $m_2$ (and hence not prime) for all $k$. In summary: I repeatedly used facts about infinitely many $x$ to find a function value that is nonzero, then not a unit, then not prime, ...

share|cite|improve this answer

Hint $\ $ For some $\,x_0\,$ we have $\,f(x_0)= m\ne \pm1\: $ (see the note below for one proof).

It follows that $\,m\mid f(mn+x_0)\,$ since $\,{\rm mod\ } m\!:\ f(mn+x_0)\equiv f(x_0)\equiv m \equiv 0.\:$

Note $\ $ If $\,f(x) = \pm 1\,$ for all $\,x\in \Bbb Z\,$ then $\,f\!-\!1\,$ or $\,f\!+\!1\,$ would have infinitely many roots, impossible for a nonzero polynomial over a domain. Thus we do not need to use any order properties to deduce that $\,f\,$ takes a nonunit value.

share|cite|improve this answer
This is obviously false... – dinoboy Jan 24 '13 at 17:30
@dinoboy Typo fixed. – Math Gems Jan 24 '13 at 17:34

$f(kc)$ where $k\in \mathbb{N}$ and $c$ is the constant term of the polynomial is nonprime. Not sure what to do if $c=1$ or $c=-1$ though.

share|cite|improve this answer
This fails when $c=1$. – dinoboy Jan 24 '13 at 17:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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