# Congruent solution implies an integer solution.

Let us consider a polynomial $p\in \mathbb{Q}[x]$ with $p(\mathbb{Z})\subseteq \mathbb{Z}$, such that for each $a\in \mathbb{N},\,p(n)\equiv 0 \,(\text{ mod } a\,)$ has a solution for some $n\in \mathbb{Z}.$

Does this imply $p(n)=0$ for some $n\in \mathbb{Z}$ ?

Thanks in advance for any help.

I claim that $f(x) = (x^3-3)(x^2-2)(x^2+2)(x^2+1)$ is a counterexample: for any nonzero integer $a$, we have $a \mid f(n)$ for some $n \in \mathbb{Z}$. However, it is clear that $f(n) \ne 0$ for all $n \in \mathbb{Z}$.
First, by the Chinese Remainder Theorem, it suffices to prove this in cases where $a$ is a prime power. Now, if $a = p$ is an odd prime, then at least one of $-1, 2, -2$ must be a quadratic residue $\pmod{p}$ since $-2 = (-1) \cdot 2$. Then, for example, if $n^2 \equiv -2 \pmod{p}$, then $p \mid n^2+2$ so $p \mid f(n)$; and similarly for the other cases. Now for example if $n^2 + 2 \equiv 0 \pmod{p}$, then in particular since $p$ is odd we have $2n \not\equiv 0 \pmod{p}$; therefore, by Hensel's lemma, for each $m > 0$ that implies that there exists $n' \equiv n \pmod{p}$ such that $(n')^2 + 2 \equiv 0 \pmod{p^m}$. This proves what we wanted in cases where $a$ is an odd prime power.
All that remains is to show the case $a = 2^m$. However, here the $x^3-3$ factor comes into play: set $g(x) = x^3 - 3$. Then since $g(1) = -2 \equiv 0 \pmod{2}$ and $g'(1) = 3 \not\equiv 0 \pmod{2}$, again by Hensel's lemma we get that for each $m$, there exists $n' \equiv 1 \pmod{2}$ such that $g(n') \equiv 0 \pmod{2^m}$, finishing the proof.
• Come to think of it, $(2x-1)(3x-1)$ should also work: if $a$ is a prime power, then at least one of 2 or 3 has a multiplicative inverse $\pmod{a}$. The initial example has the advantages of being monic and of not even having any rational roots, though. – Daniel Schepler Jul 27 '18 at 17:01
• Hi, Daniel. Sorry to be late. Thanks for yours answer. But, I didn't get one part, i,e; how does it suffices to prove the result in case where $a$ is a prime power. Please allow me to explain. If $a \in \mathbb{N}$, then by UFT, $a=a_1 a_2 ...a_m$ for some $m \in \mathbb{N}$, where each $a_i$'s are prime power and coprime to each other. Now by CRT, if we have $f(n) \equiv 0 (\text{ mod } a_i)$ has solution for some $n \in \mathbb{N}$, then there exists some integer $x$ such that $x \equiv 0 (\text{ mod } a)$. But my confusion is that how can we say that $x$ is of the form $f(n)$? – Surajit Aug 1 '18 at 19:06
• Choose $n_1$ such that $f(n_1) \equiv 0 \pmod{a_1}$, and choose $n_2$ such that $f(n_2) \equiv 0 \pmod{a_2}$, etc. Now, choose $n$ such that $n \equiv n_1 \pmod{a_1}$, $n \equiv n_2 \pmod{a_2}$, etc. Then $f(n) \equiv f(n_1) \equiv 0 \pmod{a_1}$, $f(n) \equiv f(n_2) \equiv 0 \pmod{a_2}$, etc. – Daniel Schepler Aug 1 '18 at 19:13