BMO 2017

Let $a_0,a_1,\dots ,a_n$ be integers to be chosen later, and consider the polynomial $P(x)=\frac{1}{n!}Q(x)$ where $$Q(x)=\sum _{k=0}^n(-1{)}^{n-k}(\genfrac{}{}{0ex}{}{n}{k})a_k\prod _{\begin{array}{c}0\le i\le n\\ i\ne k\end{array}}(x-i).$$ Observe that for $l\in \{0,1,\dots ,n\}$ we have $$\begin{array}{rl}P(l)& =\frac{1}{n!}(-1{)}^n(\genfrac{}{}{0ex}{}{n}{l})a_l\prod _{\begin{array}{c}0\le i\le n\\ i\ne l\end{array}}(l-i)\\ & =\frac{1}{n!}(-1{)}^{n-l}(\genfrac{}{}{0ex}{}{n}{l})a_{l}l!(-1{)}^{n-l}(n-l)!\\ & =a_l\end{array}$$ So $P(x)$ is the unique polynomial of degree at most $n$ such that $P(l)=a_l$. (Any two polynomials of degree at most $n$ agreeing on $n+1$ distinct values are equal.) Note in particular that $$\sum _{k=0}^n(-1{)}^{n-k}(\genfrac{}{}{0ex}{}{n}{k})\prod _{\begin{array}{c}0\le i\le n\\ i\ne k\end{array}}(x-i)=n!(\ast )$$ If $p$ is a prime dividing $n!$, we let $r_p$ be maximal such that $p^{r_p}$ divides $n!$. If $p$ divides $m$, then there is an integer $d_p$ such that $m^{d_p}\equiv 0(\mathrm{mod}{p}^{r_p})$, for example $d_p=r_p$ will do. If $p$ does not divide $m$, then there is an integer $d_p$ such that $m^{d_p}\equiv 1(\mathrm{mod}{p}^{r_p})$, for example, by Euler's theorem, $d_p=\phi (p^{r_p})$ will do. Let $d=d_1{d}_2\dots d_p$ and observe that for every positive integer $t$ we have $m^{td}\equiv 0(\mathrm{mod}{p}^{r_p})$ if $p\mid m$ and $m^{td}\equiv 1(\mathrm{mod}{p}^{r_p})$ if $p\nmid m$.

Now let $t_0,\dots ,t_n$ be positive integers to be chosen later and define $a_k=m^{t_{k}d}$. We will show that the polynomial $P(x)$ has integer coefficients. We will also show that there is an appropriate choice of $t_0,\dots ,t_n$ such that $P(x)$ has degree exactly equal to $n$.

To show that $P(x)$ has integer coefficients it is enough to show that for every $p$ dividing $n!$, all coefficients of $Q(x)$ are multiples of $p^{r_p}$. This is immediate if $p$ divides $m$ as all $a_k$'s are multiples of $p^{r_p}$. If $p$ does not divide $m$ then we have $a_k\equiv 1(\mathrm{mod}{p}^{r_p})$ for every $0\le k\le n$ and so by (*) $$Q(x)=\sum _{k=0}^n(-1{)}^{n-k}(\genfrac{}{}{0ex}{}{n}{k})\prod _{\begin{array}{c}0\le i\le n\\ i\ne k\end{array}}(x-i)\equiv n!(\mathrm{mod}{p}^{r_p}).$$ This shows that all coefficients of $Q(x)$ are indeed multiples of $p^{r_p}$. It remains to show that there is a choice of $t_0,\dots ,t_n$ guaranteeing that the degree of $P(x)$ is exactly equal to $n$. One such choice is $t_0=2$ and $t_1=\cdots =t_n=1$. This works because if $P(x)$ had degree less than $n$, then looking at the values $P(1),\dots ,P(n)$ we would get that $P(x)$ is constant. But this is impossible as $P(0)\ne P(1)$.