Fermat witness to compositeness of $n=21$

Question

I have to find a Fermat witness to compositeness of $n=21$.

I found this

The Fermat compositeness test is a primality test based on the observation that by Fermat’s little theorem if $b^{n-1} \not\equiv 1 \pmod n$ and $b \not\equiv 0 \pmod n$ then $n$ is composite. The Fermat compositeness test consists of checking whether $b^{n-1} \equiv 1 \pmod n$ for a handful of values of $b$. If a $b$ with $b^{n-1} \not\equiv 1 \pmod{n}$ is found, then $n$ is composite.

A value of $b$ for which $b^{n-1} \not\equiv 1 \pmod{n}$ is called a witness to $n$’s compositeness. If $b^{n-1} \equiv 1 \pmod n$ then $n$ is said to be pseudoprime base $b$.

• $b=2$: $2^{20} \mod{21} \equiv 4 \mod{21}$

So $2$ is a witness to 21's compositness.

Is this correct?

Answer 1

Yes, that's right. It might be nice to note that this is often a very easy test to perform by hand, even if you use to different bases $b$ (which usually means $2$ and $3$).

In this case, $$ 2^{20} \equiv (2^4)^5 \equiv (-5)^5 \equiv (25)^2 (-5) \equiv 16\cdot -5 \equiv (-5)^2 \equiv 25 \equiv 4 \pmod {21}.$$ This is sufficiently simple that you might even be able to do it in your head.