a) Show that $\displaystyle 16^{560} \equiv 1 \pmod{561}$ even though 561 is not prime. (This shows that the converse of Fermat's Theorem is false.)

b) (Harder) Show that $\displaystyle a^{561} \equiv a \pmod{561}$ for all integers $\displaystyle a$.

a) $\displaystyle \phi(561) = 320$ and $\displaystyle gcd(16, 561) = 1$, then according to Euler's Theorem $\displaystyle 16^{560} = 16^{320} 16^{240} = 16^{240} \pmod{561}$. I do not know what to do next.