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 \pmod{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 \pmod{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 \pmod{p^2}$, and therefore, $x^n - 1 \equiv np \pmod{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 \pmod{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} + \dots + x^{(p-1)k} \equiv \underbrace{1+1+\dots+1}_{p} \equiv 0 \pmod{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.