Past exam of the probability, statistics and options I course of the University of Oxford / 2007 / C / 1

Euler's theorem states that if $\gcd (a,m)=1$, then $a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$, where $\varphi$ is Euler's totient function. This includes Fermat's little theorem when $m$ is prime.

For each prime-power factor $p_i^{e_i}$, the integer $\varphi (p_i^{e_i})$ divides the defined least common multiple $\lambda (m)$. Euler's theorem modulo that prime power therefore givesThe prime powers are pairwise coprime, so their product divides $a^{\lambda (m)}-1$. Equivalently the Chinese remainder theorem givesFor the specified composite integer,Raising $a^{80}\equiv 1(\mathrm{mod}561)$ to the seventh power provesThus 561 is a Carmichael number. We use exactly the source's definition of $\lambda$ as the least common multiple of prime-power totients; its validity here does not require replacing it by a smaller exponent at powers of two.