Fermat Little Theorem 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?
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$.
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.