I had the following question:
Does there exist a nonzero polynomial $P(x)$ with integer coefficients satisfying both of the following conditions?
- $P(x)$ has no rational root;
- For every positive integer $n$, there exist an integer $m$ such that $n$ divides $P(m)$.
I created a proof showing that there was no polynomial satisfying both of these conditions:
Suppose that we have a nonzero polynomial with integer coefficients $P(x)=\sum_i c_i x^i$ without a rational root, and for all positive integer $n$, we have an integer $m_n$ such that $n|P(m_n)$. This would imply $P(m_n)\equiv0\pmod n\Rightarrow \sum_i c_i m_n^i\equiv0$. By Freshman's Dream we have $P(m_n+an)=\sum_i c_i(m_n+an)^i\equiv\sum_i c_im_n^i+c_ia^in^i\equiv\sum_ic_im_n^i=P(m_n)\equiv0\pmod n$ for some integer $a$. Therefore if $b\equiv m_n\pmod n$ then $P(b)\equiv P(m_n)\equiv0\pmod n$.
Now the above conditions and findings imply for all prime $p$, we have a number $m_p$ such that $p|P(m_p)$, and that if $b\equiv m_p\pmod p$ then $P(b)\equiv 0\pmod p$. Consider the set of the smallest $n$ primes $\{p_1,p_2,p_3,\cdots,p_n\}$. By Chinese Reamainder Theorem there exists an integer $b$ such that $b\equiv m_{p_1}\pmod{p_1},b\equiv m_{p_2}\pmod{p_2},b\equiv m_{p_3}\pmod{p_3},\cdots,b\equiv m_{p_n}\pmod{p_n}$ by Chinese Remainder Theorem. Then $p_1,p_2,p_3\cdots,p_n|P(b)\Rightarrow p_1p_2p_3\cdots p_n|P(b)$. As $n$ approaches infinity (as there are infinitely many primes), $p_1,p_2,p_3\cdots,p_n$ approaches infinity. Therefore either $P(b)=\infty$ or $P(b)=0$. Since for finite $b$ and integer coefficients $P(b)$ must be finite, then $P(b)=0$. However as $a$ is an integer, this implies $P$ has a rational root, a contradiction.
I'm not sure if my proof is correct, and my main concern is that I am incorrectly using Chinese Remainder Theorem since I am not sure if I can apply it to infinitely many divisors.
Is this proof correct, and if not, how do I solve this question?
EDIT: It appears not only is my proof incorrect (as$b$ does not converge) as Paul Sinclair has shown, but that according to Jaap Scherphuis there are examples of polynomials that satisfy the conditions. Therefore, my question now is how one can prove the existence of these polynomials while using elementary methods (as this is an IMO selection test problem).
Best Answer
Consider the polynomial
$$ P(x) = (x^2 - 13)(x^2 - 17)(x^2 - 221) $$
Clearly this has no rational solutions. We wish to show that the congruence $P(x) \equiv 0 \bmod{m}$ is solvable for all integers $m$. By the chinese remainder theorem, this is the same as showing $P(x) \equiv 0 \bmod{p^k}$ is solvable for all prime powers $p^k$.
Notice that if either $13$, $17$, or $221$ is a quadratic residue modulo $p^k$, then one of the quadratic terms in $P$ is a difference of squares modulo $p^k$ and factors into linear terms and we are done. We show this is always the case.
For odd $p \neq 13,17$, not all of $13$, $17$, $221$ can be quadratic non-residues modulo $p^k$, otherwise we would have the following contradiction
$$ -1 = \left( \frac{221}{p^k}\right) = \left( \frac{13}{p^k}\right)\left( \frac{17}{p^k}\right)=(-1) (-1)=1 $$
If $p = 13$ then 17 is a quadratic residue modulo $p^k$ because by quadratic reciprocity we have
$$ \begin{eqnarray} \left( \frac{17}{13^k}\right) &=& \left( \frac{13^k}{17}\right) (-1)^{\frac{13^k -1}{2} \frac{17 -1}{2}} \\ &=& \left( \frac{13}{17}\right)^k (-1)^{\frac{13^k -1}{2} \frac{17 -1}{2}} \\ &=& 1 \end{eqnarray} $$
If $p=17$ a similar argument applies.
For $p=2$ we can use Hensel's lemma to show that for any odd $a$, $x^2 \equiv a \bmod{2^k}$ is solvable for all $k$ if and only if $a \equiv 1 \bmod{8}$. Therefore $17$ is a quadratic residue modulo $2^k$ for all $k$.