# Integer Polynomials and Composite Numbers

Suppose $f(x)$ is an integer polynomial that can be factored as $f(x) = g(x)h(x)$ where $g(x)$ and $h(x)$ are both integer polynomials of positive degree. Prove that there exists an integer $n$ such that the integer $|f(n)|$ is composite.

We can see that $|f(x)| = |g(x)|\cdot|h(x)|$. Since $n \in \mathbb{N}$, $|g(n)|$ and $|h(n)|$ are integers.

But how can we show that $|g(n)|\cdot|h(n)|$ is not prime?

Hint: a non-constant polynomial can take any given value at most finitely many times.

Therefore $G = g^{-1}\left(\,\{-1,0,1\}\,\right)$ and $H = h^{-1}\left(\,\{-1,0,1\}\,\right)$ are both finite. Then, for any $n \in \mathbb{Z} \setminus (G \cup H)\,$ $f(n)$ will be a composite number (why?).

• im not entirely sure what you mean, could you elaborate a little further please – u123435 Mar 31 '17 at 3:14
• $g(n)$ is an integer, and $g(n) \ne 0,\pm 1$ since $n \not \in G\,$. Same goes for $h(n)\,$. Then $f(n)=g(n)h(n)$ is a product of two integers, neither of which is $0$ or $\pm 1$. – dxiv Mar 31 '17 at 3:16

Note $p > 0$ the degree of $g$ and $q > 0$ the degree of $h$. Suppose that for all $n$, $| f (n) |$ is prime. Since $| g (n) |$ and $| h (n) |$ divide $| f (n) |$, we have for all $n$, $| g (n) | = 1$ or $| h (n) | = 1$.

Let $G = \{ n \in \mathbb{Z} \mid | g (n) | = 1 \}$ and $H = \{ n \in \mathbb{Z} \mid | h (n) | = 1 \}$. From the above, one of these two sets must be infinite.

• Suppose that $G$ is infinite, and let $G^+$ (resp. $G^-$) be the subset of $G$ such that $g (n) = 1$ (resp. $g (n) = -1$). We have $G = G^+ \cup G^-$, so at least one of $G^+$ or $G^-$ must be infinite. From this we deduce that the polynomial $g$ has infinitely many (complex) roots, and is therefore constant. This is a contradiction with $p > 0$.

• If $G$ is finite, then $H$ must be infinite, and a similar reasoning leads to $h$ being constant, which contradicts $q > 0$.

Therefore our hypothesis that $| f (n) |$ is prime for all $n$ is false, and thus there exists some $n_0$ such that $| f (n_0) |$ is composite.