Solution (source code)

= Solution

If $(a,n)=1$, then $a^{\phi(n)}\equiv1\pmod n$.