Past exam of the mathematics course of the University of Cambridge / 2005 / ii / Paper 4 / 1H (Number Theory)

An odd composite integer $n>1$ coprime to $b$ is a Fermat pseudoprime to base $b$ if $b^{n-1}\equiv 1(\mathrm{mod}n)$. A Carmichael number is a composite integer satisfying this congruence for every integer $b$ coprime to $n$. The Korselt criterion says that a composite $n$ is a Carmichael number exactly when it is squarefree and $p-1$ divides $n-1$ for every prime divisor $p$ of $n$.

By the Korselt criterion, the prime factors are distinct. There cannot be just one prime factor, since a Carmichael number is composite. If there were exactly two, write $n=pq$ with $p<q$. Then $q-1\mid pq-1=p(q-1)+(p-1)$, so $q-1\mid p-1$, impossible because $0<p-1<q-1$. Hence at least three distinct prime factors are necessary.

The prime factorization is $561=3\cdot 11\cdot 17$, so it is composite and squarefree. Moreover $3-1=2$, $11-1=10$ and $17-1=16$ all divide $560=561-1$. The Korselt criterion therefore proves that 561 is a Carmichael number.