Fermat Little Theorem

Question

The problem I am trying to solve is how to use Fermat Little theorem to prove that the number 66013 is not prime. I found this problem on another website (Question Cove). The student who had to solve this problem didn't know how to proceed. I offered to help. I read the following lecture notes Princeton lecture notes on cryptography and thought I would follow the same procedure. I wrote $66013 = 257^2 + 36 = 256^2 + 513 + 36 = 2^{16} + 2^9 + 37$ but I am stuck after that. What is the correct approach?

Answer 1

Pick $a:=3$. We have $$a^{66212}=3^{66212}\not\equiv1\pmod{66213}$$ because $3\mid 66213$. Well, there, I used Fermat's Little Theorem!

Edit: Originally, the OP's question was to disprove the primality of $66213$.

---

For the corrected question (with number $66013$), choose $a:=15781$. Then, $$a^2=249039961\equiv 38925\pmod{66013}\,.$$ That is, $$a^4\equiv 38925^2=1515155625\equiv25249\pmod{66013}\,.$$ Finally, $$a^5=a\cdot a^4\equiv 15781\cdot 25249=398454469\equiv 1\pmod{66013}\,.$$ That is, $$a^{66013-1}=a^2\,\left(a^5\right)^{13202} \equiv a^2\cdot 1^{13202}\equiv a^2\equiv 38925\pmod{66013}\,.$$ Thus, $66013$ is not prime.

Answer 2

Fermat's little theorem is an incredibly inefficient method for proving primality. In this case the standard test for divisibility by 3 (by adding the digits and checking whether the sum is a multiple of 3) shows that $66213$ is a multiple of $3$.