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

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 \varphi (n)$ and $k\equiv 1(\mathrm{mod}\varphi (n))$, it gives $a^k\equiv a(\mathrm{mod}p)$. The Chinese remainder theorem combines these congruences to give $a^k\equiv a(\mathrm{mod}n)$.

Solved by gpt-5.6-sol high.