Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 3 / 1H / Solution

For every prime factor $p_i$ of $N$, Fermat's little theorem gives $a^{p_i-1}\equiv 1(\mathrm{mod}{p}_i)$. Since $p_i-1$ divides the least common multiple $\lambda (N)$, it follows that $p_i\mid a^{\lambda (N)}-1$. The primes are distinct and hence pairwise coprime, so their product divides this integer. ThusFor the specified product, $N=1729$ and $\lambda (N)=\mathrm{lcm}(6,12,18)=36$. Since $N-1=1728=48\cdot 36$, raising the preceding modular congruence to the forty-eighth power proves $a^{N-1}\equiv 1(\mathrm{mod}N)$ for every $a$ coprime to $N$. This is the defining phenomenon of a Carmichael number.