= Solution
{c}
<Euler's theorem> states that if $\gcd(a,m)=1$, then $a^{\phi(m)}\equiv1\pmod m$, where $\phi$ 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 $\phi(p_i^{e_i})$ divides the defined <least common multiple> $\lambda(m)$. <Euler's theorem> modulo that prime power therefore gives
$$
a^{\lambda(m)}
=\left(a^{\phi(p_i^{e_i})}\right)^{\lambda(m)/\phi(p_i^{e_i})}
\equiv1\pmod{p_i^{e_i}}.
$$
The prime powers are pairwise coprime, so their product divides $a^{\lambda(m)}-1$. Equivalently the <Chinese remainder theorem> gives
$$
\boxed{a^{\lambda(m)}\equiv1\pmod m.}
$$
For the specified composite integer,
$$
\lambda(561)=\operatorname{lcm}(2,10,16)=80,
\qquad560=7\cdot80.
$$
Raising $a^{80}\equiv1\pmod{561}$ to the seventh power proves
$$
\boxed{a^{560}\equiv1\pmod{561}\quad(\gcd(a,561)=1).}
$$
Thus 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.
Back to article page
