Japan Mathematical Olympiad

If, for a pair of integers $a,b$ and a positive integer $m$, $a-b$ is divisible by $m$, we write $a-b\equiv 0(\mathrm{mod}m)$. We will show that the numbers $n$ we seek are those of the form $kp$, where $k$ is a positive integer. Let us first show that if $n$ satisfies the condition of the problem, then $n$ must be a multiple of $p$. To see this let $x=p+1$. Then from $x^n-1\equiv 1^n-1\equiv 0(\mathrm{mod}p)$, we get the fact that $x^n-1$ is divisible by $p$, and hence by the condition of the problem, is divisible by $p^2$ as well. By using the binomial expansion we get $(p+1{)}^n\equiv np+1(\mathrm{mod}{p}^2)$, and therefore, $x^n-1\equiv np(\mathrm{mod}{p}^2)$. This implies that $np$ is a multiple of $p^2$, and therefore, $n$ must be a multiple of $p$.

Conversely, we will show that if $n=kp$ for a positive integer $k$, then it satisfies the condition of the problem. First we note that $x^n=(x^k{)}^p\equiv x^k(\mathrm{mod}p)$ holds by Fermat's Little Theorem. This shows that if $x^n-1$ is a multiple of $p$, then so is $x^k-1$. Now we have $$\frac{x^n-1}{x^k-1}=1+x^k+x^{2k}+\cdots +x^{(p-1)k}\equiv \underset{p}{\underbrace{1+1+\cdots +1}}\equiv 0(\mathrm{mod}p),$$ from which we conclude that $x^n-1=(x^k-1)\times \frac{x^n-1}{x^k-1}$ is a multiple of $p^2$. Thus, we see that $n=kp$ satisfies the condition of the problem.