45th Mongolian Mathematical Olympiad

Lemma. Let $f(x)$ be a polynomial of degree greater than or equal to $1$. $${\mathbb{P}}^{\prime }(f(x))=|\{p\in \mathbb{P}\mid p|f(x),\exists x\in \mathbb{Z}\}|=\infty$$ Proof of lemma: Assume $f(x)=b_k{x}^k+\cdots +b_0$, $k\ge 1$. Suppose the contrary, ${\mathbb{P}}^{\prime }(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+\cdots +1)$$ and there exists $p$-prime number such that $$p|b_k\cdot b_0^{k-1}(t{p}_1\dots p_s{)}^k+\cdots +1,(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^{\prime })=1$. Hence there exist $g,h\in \mathbb{Z}[x]$ such that $$f(x)\cdot g(x)+f^{\prime }(x)\cdot h(x)=a,0\ne a\in \mathbb{Z}.(1)$$ Now we will show it is enough that there exists $x_0\in \mathbb{Z}$ such that for arbitrary $p\in {\mathbb{P}}^{\prime }(f(x))$, and $p>|a|:{\mathrm{ord}}_p(f(x_0))=k$. If $p\in {\mathbb{P}}^{\prime }(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^{\prime }\in \mathbb{Z}$ such that $p^{\alpha +1}|f(x_0^{\prime })$. Also $p>|a|$ from here, we can see that $(f^{\prime }(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(\mathrm{mod}{p}^{\alpha +1})$$ Thus $f(p^{\alpha }\cdot t+x_0)\equiv t{p}^{\alpha }{f}^{\prime }(x_0)+f(x_0)(\mathrm{mod}{p}^{\alpha +1})$; here we have $(p,f^{\prime }(x_0))=1$. Therefore there exists $t\in \mathbb{Z}$ such that $$p|t\cdot f^{\prime }(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}^{\prime }(x_0)+f(x_0).$$ Otherwise, that is ${\mathrm{ord}}_p(f(x_0+p^k))=k$.