\[a^{n} \equiv a \; (mod \; n)\]
for every integer \[a \nequiv 0 \; (mod \; n)\]
it does not follow that \[n\]
is prime. Counterexamples to this converse are not easy to find. One such is\[a^{561} \equiv a \; (mod \; 561)\]
.561 is composite -
\[561 = 11 \times 51 \]
. Composite numbers that have the property that \[n | (2^{n-1} -1)\]
are called psudoprimes.