What's the difference between a Fermat pseudoprime and a Carmichael number?

Question

I've read a lot of definitions in different places on the Internet and I'm confused since all of them express the same thing, but using seemingly different explanations.

Can somebody please point out the difference in a clear way?

Answer 1

In elementary theory of numbers there are two very important theorems in relation to prime numbers, Fermat's little theorem and Wilson's theorem. But while the first one does not characterize the prime numbers the second one does because $ p $ is prime if and only if $p$ satisfies Wilson's theorem.

The above implies that there are composite numbers that satisfy, totally or partially, Fermat's little theorem. These are the Fermat pseudoprimes and the Carmichael numbers.

A composite number $A$ is a Carmichael number if for all $a$ coprime with $A$ one has $a^{A−1}≡1\pmod A$. The composite $B$ is a Fermat pseudoprime when some number $b$ is such that $b^{B−1}≡1\pmod B$.

Fermat pseudoprimes "mimics" FLT with a single (maybe more) number but Carmichael completely satisfies the theorem without being a prime.

In short, $p$ prime implies $FLT$ but not the reciprocal while $p$ prime is equivalent to satisfy Wilson's theorem.

Example (1).- The composite number $91$ is Fermat pseudoprime because $3^{90}\equiv 1\pmod {91}$.

Example (2).- The composite number $561$ is Carmichael because for all $a$ coprime with $561$ one has the same property $a^{560}\equiv 1\pmod{561}$ as for FLT.