Question related to pseudoprimes and Carmichael numbers

Question

We know by Fermat's little theorem that if $m$ is a prime then for any $n \in \mathbb{Z}$, then $$ n^m \equiv n (mod \ m). $$ I was wondering if there was a composite $m$ that satisfies this condition? (Maybe this condition is equivalent to being a Carmichael number, but I wasn't sure...) Thank you!

Answer 1

We need to prove two things: (i) if $m$ is composite and $a^m\equiv a\pmod{m}$ for all $a$, then $m$ is a Carmichael number and (ii) If $m$ is a Carmichael number, then $a^m\equiv a \pmod{m}$ for all $a$.

Proving (i) is easy. For suppose that $a^m\equiv a\pmod{m}$ for all $a$. In particular, suppose that $a$ is relatively prime to $m$. Then by division we get that $a^{m-1}\equiv 1\pmod{m}$. Since $m$ is composite, it follows that $m$ is a Carmichael number.

Proving (ii) is harder. We need the fact that if $m$ is a Carmichael number, then $m$ is square-free. Proofs can be found fairly easily by searching, so we omit the proof.

Thus $m$ can be expressed as a product $p_1p_2\cdots p_t$, where the $p_i$ are distinct primes.

Suppose first that $a$ is not divisible by $p_i$. Then $a^{p_i-1}\equiv 1\pmod{p_i}$. By the Korselt Criterion (please see Wikipedia), we have $p_i-1$ divides $m-1$. It follows that $a^{m-1}\equiv 1\pmod{p_i}$, and therefore $a^m\equiv a \pmod{p_i}$.

Suppose next that $a$ is divisible by $p_i$. Then $a^m\equiv a\pmod{p_i}$, since both are congruent to $0$.

We have shown that $a^m\equiv a\pmod{p_i}$ for all the primes $p_1$ to $p_t$. Since the $p_i$ are distinct, it follows that $a^m\equiv a\pmod{m}$.

Answer 2

Sure there is. It's a Carmichael number by definition. $561$ is the smallest Carmichael number.