0
$\begingroup$

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?

$\endgroup$

closed as off-topic by Adrian Keister, Mostafa Ayaz, Isaac Browne, José Carlos Santos, Namaste Jul 31 '18 at 0:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Adrian Keister, José Carlos Santos, Namaste
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 66213 = 9* 7357 $\endgroup$ – Thierry Kauffmann Jul 29 '18 at 20:27
  • $\begingroup$ Yes, indeed the quotient is easy to find. I was just pointing out that 66213 falls to the very simplest rule of thumb for checking primality. $\endgroup$ – Rob Arthan Jul 29 '18 at 20:31
-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If $66213$ were prime, any $a$ between $1$ to $66212$ could be used. The point is, because $a=3$ couldn't be used, $66213$ is not prime. $\endgroup$ – Batominovski Jul 29 '18 at 20:20
  • 1
    $\begingroup$ But you can't claim $3|66213$ unless you know that $66213$ is not prime in the first place. This argument is circular. $\endgroup$ – fleablood Jul 29 '18 at 20:21
  • 1
    $\begingroup$ No, I didn't have to use circular logic to verify that $3\mid 66213$. I can just divide it. This problem is a joke. $\endgroup$ – Batominovski Jul 29 '18 at 20:23
  • 1
    $\begingroup$ I agree with Batominovski, it is a form of torture to set students tasks like this. And to placate Anurag A and fleablood, we are entitled to assume for a contradiction that $a = 3$ and $66213$ are relatively prime (since if they aren't then the prime $3$ divides $66213$). $\endgroup$ – Rob Arthan Jul 29 '18 at 20:25
  • 1
    $\begingroup$ @Batominovski May I ask how you picked a:=15781.? $\endgroup$ – Thierry Kauffmann Jul 30 '18 at 13:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.