Mongolian Mathematical Olympiad

Lemma. Let $f(x)$ be a polynomial of degree greater than or equal to $1$.
$$\mathbb{P}'(f(x)) = |\{p \in \mathbb{P} \mid p|f(x), \exists x \in \mathbb{Z}\}| = \infty$$
Proof of lemma: Assume $f(x) = b_kx^k + \dots + b_0$, $k \ge 1$. Suppose the contrary, $\mathbb{P}'(f(x)) < \infty$; we have above prime numbers finite $p_1, \dots, p_s$. Now substituting $x = b_0 t p_1 \dots p_s$, we get
$$f(x) = b_0 (b_k \cdot b_0^{k-1}(t p_1 \dots p_s)^k + \dots + 1)$$
and there exists $p$-prime number such that
$$p|b_k \cdot b_0^{k-1}(t p_1 \dots p_s)^k + \dots + 1, \quad (p, p_1 \dots p_s) = 1.$$
This leads to a contradiction.

Now let us solve the problem. From the given condition we have $(f, f') = 1$. Hence there exist $g, h \in \mathbb{Z}[x]$ such that
$$f(x) \cdot g(x) + f'(x) \cdot h(x) = a, \quad 0 \neq a \in \mathbb{Z}. \qquad (1)$$
Now we will show it is enough that there exists $x_0 \in \mathbb{Z}$ such that for arbitrary $p \in \mathbb{P}'(f(x))$, and $p > |a| : \mathrm{ord}_p(f(x_0)) = k$. If $p \in \mathbb{P}'(f(x))$ then there exists $x_0 \in \mathbb{Z}$ such that $p|f(x_0)$.

Moreover, if $p^\alpha|f(x_0)$ then there is a $x'_0 \in \mathbb{Z}$ such that $p^{\alpha+1}|f(x'_0)$. Also $p > |a|$ from here, we can see that $(f'(x_0), p) = 1$.

If we put $x = p^\alpha \cdot t + x_0$, here $s \ge 1$:
$$(p^\alpha t + x_0)^s \equiv s \cdot (t p^\alpha) \cdot x_0^{s-1} + x_0^s \pmod{p^{\alpha+1}}$$
Thus $f(p^\alpha \cdot t + x_0) \equiv t p^\alpha f'(x_0) + f(x_0) \pmod{p^{\alpha+1}}$; here we have $(p, f'(x_0)) = 1$. Therefore there exists $t \in \mathbb{Z}$ such that
$$p|t \cdot f'(x_0) + \frac{f(x_0)}{p^\alpha}.$$
Now assume that $p^{k+1}|f(x_0)$. Thus substituting
$$x = p^k + x_0 : f(p^k + x_0) \equiv p^k f'(x_0) + f(x_0).$$
Otherwise, that is $\mathrm{ord}_p(f(x_0 + p^k)) = k$.