# Fermat witness to compositeness of $n=21$

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?

• That's right. Perhaps you are expected to give some detail about the claim that $2^{20}\equiv 4\pmod{21}$. – André Nicolas Apr 28 '15 at 23:57
• @AndréNicolas thanks so much! Do you know if there is a trick how we can find an $a$ and an $i$ such that $a^{2^{I-1}u} \not\equiv \pm 1 \mod{n}$ and $a^{2^iu} \equiv 1 \mod{n}$ given that $n-1=2^tu$ so that we find a Rabin-Miller compositness? – user175343 May 3 '15 at 19:42
• I think somewhere in problem solutions for a number theory course, I had stuff about that. Would have to find it. In the meantime, you can look at Pepin's Test, and the Lucas primality test. – André Nicolas May 3 '15 at 19:52

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.
• thanks so much! Do you know if there is a trick how we can find an $a$ and an $i$ such that $a^{2^{I-1}u} \not\equiv \pm 1 \mod{n}$ and $a^{2^iu} \equiv 1 \mod{n}$ given that $n-1=2^tu$ so that we find a Rabin-Miller compositness? – user175343 May 3 '15 at 19:41