1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ That's right. Perhaps you are expected to give some detail about the claim that $2^{20}\equiv 4\pmod{21}$. $\endgroup$ – André Nicolas Apr 28 '15 at 23:57
  • $\begingroup$ @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? $\endgroup$ – user175343 May 3 '15 at 19:42
  • $\begingroup$ 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. $\endgroup$ – André Nicolas May 3 '15 at 19:52
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user175343 May 3 '15 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy