# polynomial of degree at least 1

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?

-

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

-

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.

-

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

-

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.

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

-
This fails when $c=1$. –  dinoboy Jan 24 '13 at 17:26