The 35th Japanese Mathematical Olympiad

Solution: We will show that $f(x)=(x-1{)}^m$ provides an answer. For $n\ge 2$ we have $f(n)=(n-1{)}^m>0$, thus the first condition is satisfied.

Lemma 1. Let $d,t,x$ be positive integers. If $x-1$ is a multiple of $d^t$, then $x^d-1$ is a multiple of $d^{t+1}$.

Proof. Since $x\equiv 1(\mathrm{mod}d)$, we have $x^{d-1}+\cdots +x+1\equiv 1+\cdots +1\equiv 0(\mathrm{mod}d)$. Thus $x^d-1=(x-1)(x^{d-1}+\cdots +x+1)$ is a multiple of $d^{t+1}$ as desired. $■$

Let $n\ge 2$. Since $n^{(n-1)0}-1=n-1$ is a multiple of $n-1$, an induction using Lemma 1 shows that $n^{(n-1)m}-1$ is a multiple of $(n-1{)}^{m+1}$ for $m\ge 0$. Thus, we conclude that $f(x)=(x-1{)}^m$ is an answer for $m\ge 0$.

Next we will show that no other answers exist. For integers $a,b$ with $b\ne 0$, we write $b\mid a$ to mean that $a$ is divisible by $b$.

Lemma 2. For a positive integer $n$ and integers $a$ and $b$, $a\equiv b(\mathrm{mod}n)$ implies $f(a)\equiv f(b)(\mathrm{mod}n)$.

Proof. Write $f(x)=a_0+a_{1}x+\cdots +a_d{x}^d$, where $d$ is a nonnegative integer and $a_0,a_1,\dots ,a_d$ are integers. Since $n\mid a-b$, $$f(a)-f(b)=\sum _{i=1}^d{a}_i(a^i-b^i)=(a-b)\sum _{i=1}^d{a}_i(a^{i-1}+a^{i-2}b+\cdots +a{b}^{i-2}+b^{i-1})$$ is divisible by $n$. $■$

We will show that, for an odd prime $p$ and an integer $n\ge 2$, $p\mid f(n)$ implies $p\mid n-1$. For a nonnegative integer $k$, Lemma 2 shows that $f(n+kp)\equiv f(n)\equiv 0(\mathrm{mod}p)$. Thus we have $$0\equiv (n+kp{)}^{f(n+kp)}-1\equiv n^{f(n+kp)}-1(\mathrm{mod}p)$$ Since $p$ and $p-1$ are coprime, we can take a nonnegative integer $k$ such that $p-1\mid n+kp$. Then $f(n+kp)\equiv f(p-1)(\mathrm{mod}p-1)$ holds and thus Fermat's little theorem shows that $$0\equiv n^{f(n+kp)}-1\equiv n^{f(p-1)}-1,(\mathrm{mod}p)$$ therefore we have $$n^{f(p-1)}\equiv 1.(\mathrm{mod}p)$$ Since $f(p-1)\mid (p-1{)}^{f(p-1)}-1$, $f(p-1)$ and $p-1$ are coprime. Thus, there exists a positive integer $r$ such that $f(p-1)r\equiv 1(\mathrm{mod}p-1)$. By Fermat's little theorem we have $$n\equiv n^{f(p-1)r}\equiv 1^r\equiv 1,(\mathrm{mod}p)$$ that is, $p\mid n-1$.

We have shown that, for an odd prime $p$ and an integer $n\ge 2$, $p\mid f(n)$ implies $p\mid n-1$. In particular, for an odd prime $p$, any prime factor of $f(p+1)$ is also a prime factor of $p+1-1=p$, which means that $f(p+1)$ is a power of $p$.

Write $f(x+1)=x^m(b_0+b_{1}x+\cdots +b_l{x}^l)$ where $l$ and $m$ are nonnegative integers and $b_0\ne 0,b_1,\dots ,b_l$ are integers. Let $p$ be an odd prime greater than $|b_0|$. Then $f(p+1)$ is a multiple of $p^m$, while $f(p+1)\equiv b_0{p}^m\ne 0(\mathrm{mod}{p}^{m+1})$. The argument above shows that $f(p+1)=p^m$.

Let $g(x)=f(x)-(x-1{)}^m$. Then there exist infinitely many integers $n$ such that $g(n)=0$. It follows that $g(x)=0$ as polynomials. We conclude that $f(x)=(x-1{)}^m$.