Taiwan IMO Selection Camp

(Note that the possible $f(x)$ is not unique.) We now prove that
$$f(x) = (x^2 + 1)(x^2 + 2)(x^2 - 2)(x^2 + 7)$$
satisfies the conditions. It is easy to see that $f(x) = 0$ has no rational real root.

1. First we prove: for every power of an odd prime $p^\alpha$, there exists an integer $m_{p^\alpha}$ such that
$$p^{\alpha}|f(m_{p^{\alpha}}).$$
In fact, we can prove the following lemma by induction:

Lemma 1. For every odd prime $p$, there exists $r_p \in \{-1, -2, 2\}$, such that for all $\alpha \ge 1$, there must exist $m_{p^\alpha} \in \mathbb{Z}$ such that $p^\alpha|m_p^2 - r_p$.

a. First, for $\alpha = 1$, note that:
- If $p = 4k + 1$, then $-1$ is a quadratic residue modulo $p$;
- If $p = 8k + 3$, then $-2$ is a quadratic residue modulo $p$;
- If $p = 8k + 7$, then $2$ is a quadratic residue modulo $p$.

Combining the above, there must exist $m_p \in \mathbb{Z}$ and $r_p \in \{-1, -2, 2\}$, such that $p|m_p^2 - r_p$.

b. Suppose the proposition holds for $\alpha = k$. When $\alpha = k+1$, take $m_{p^{k+1}} = m_{p^k} + tp^k$, where $t$ is to be determined. Note that we have
$$\begin{aligned} m_{p^{k+1}}^2 - r_p &= (m_{p^k} + tp^k)^2 - r_p \\ &\equiv (m_{p^k}^2 - r_p) + 2m_{p^k}tp^k \pmod{p^{k+1}}. \end{aligned}$$
By the induction hypothesis, $p^k|m_{p^k}^2 - r_p$, so it suffices to take
$$t \equiv - \frac{m_{p^k}^2 - r_p}{p^k} (2m_{p^k})^{-1} \pmod{p},$$
to make $p^{k+1}|m_{p^{k+1}}^2 - r_p$ hold (Note: clearly $p$ does not divide $m_{p^k}$, so $(2m_{p^k})^{-1}$ exists.)

Combining the above, Lemma 1 is proved, and hence the original proposition holds when $n$ is a power of an odd prime.

2. Next we prove: for every power of $2$, $2^\alpha$, there exists an integer $m_{2^\alpha}$ such that $2^\alpha|f(m_{2^\alpha})$.
In fact, we can prove the following lemma by induction:

Lemma 2. For all $\alpha \ge 1$, there must exist $m_{2^\alpha} \in \mathbb{Z}$ such that $2^\alpha|m_p^2 + 7$.

a. First, for $\alpha \ge 3$, take $m_{2^\alpha} = 1$.

b. Suppose the proposition holds for $\alpha = k \ge 3$. When $\alpha = k + 1$, take
$$m_{2^{k+1}} = m_{2^k} + t2^{k-1},$$
where $t$ is to be determined. Note that we have
$$\begin{aligned} m_{2^{k+1}}^2 + 7 &= (m_{2^k} + t2^{k-1})^2 + 7 \\ &\equiv (m_{2^k}^2 + 7) + m_{2^k}t2^k \pmod{2^{k+1}}. \end{aligned}$$
By the induction hypothesis, $2^k|m_{2^k}^2 + 7$, so it suffices to take
$$t \equiv \frac{m_{2^k}^2 + 7}{2^k} \pmod{2},$$
to make $2^{k+1}|m_{2^{k+1}}^2 + 7$ hold.

Combining the above, Lemma 2 is proved, and hence the original proposition holds when $n$ is a power of $2$.

- From the two lemmas above, we know that for all $1 \le i \le s$ there exists an integer $m_{p_i^{\alpha_i}}$ such that $p_i^{\alpha_i} \mid f(m_{p_i^{\alpha_i}})$.
- Also, for any polynomial $f(x)$ with integer coefficients, and any two distinct integers $u, v$, it must be that
$$u - v \mid f(u) - f(v).$$
Hence, as long as we let $m$ satisfy the system of congruences
$$m \equiv m_{p_i^{\alpha_i}} (\text{mod } p_i^{\alpha_i}) \quad \forall i = 1, 2, \dots, s$$
we then have
$$\begin{aligned} f(m) &= [f(m) - f(m_{p_i^{\alpha_i}})] + f(m_{p_i^{\alpha_i}}) \\ &\equiv [m - m_{p_i^{\alpha_i}}] + 0 \equiv 0 \pmod{p_i^{\alpha_i}} \end{aligned}$$
holding for all $i = 1, 2, \dots, s$; in other words, $n \mid f(m)$.

Combining the above, we know that $f(x)$ satisfies the requirements of the problem.