China Hong Kong Mathematical Olympiad

We will prove the assertion when $\ell = k!$ by induction on $k$. The base case $k = 1$ is obvious.

If $k > 1$, then $\varphi(k) < k$. Suppose $m$ and $n$ are positive integers relatively prime to $\ell$ such that $m^m \equiv n^n \pmod{k}$. This clearly implies $m^m \equiv n^n \pmod{\varphi(k)!}$. By the induction hypothesis, we know that $m \equiv n \pmod{\varphi(k)}$. Thus, there exists a positive integer $a$ such that $am \equiv an \equiv 1 \pmod{\varphi(k)}$. Now, by the Euler-Fermat theorem, we have
$$m \equiv m^{am} \equiv n^{an} \equiv n \pmod{k}.$$
The proof is complete by induction.