Write squarefree $n=\prod p$. For each $p\mid n$, either $p\mid a$, when both sides vanish modulo $p$, or Fermat's theorem applies. Since $p-1\mid\phi(n)$ and $k\equiv1\pmod{\phi(n)}$, it gives $a^k\equiv a\pmod p$. The <Chinese remainder theorem> combines these congruences to give $a^k\equiv a\pmod n$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / ia / Paper 4 / 6E / e / Solution

 Solution (source code)