1
$\begingroup$

I'm supposed to prove test if $2^{2017}-1$ is prime given that I know the following:

If $p$ is prime then $2^{p-1}=1 \mod p$

I'm pretty much lost on where to begin. I can't prove this directly since I don't know $p$ is prime. I tried doing a proof by contradiction but couldn't get anywhere. Any suggestions would be appreciated. I'm fairly certain I'm not actually supposed to calculate $2^{2^{2017}-1} \mod 2^{2017}-1$ directly in doing this.

$\endgroup$
  • $\begingroup$ Are you sure this is what you're being asked? (Note that the theorem you quote would not suffice in any case - it is not an if and only if.) $\endgroup$ – rogerl Nov 29 '17 at 22:03
  • $\begingroup$ Note that $2^{p-1}=1\pmod p$ can also hold for some non-primes $p$, for example Carmichael numbers (en.wikipedia.org/wiki/Carmichael_number). $\endgroup$ – Arnaud D. Nov 29 '17 at 22:04
  • $\begingroup$ @ArnaudD. I wrote it wrong. I'm being asked to test if it is prime using that theorem. $\endgroup$ – chris Nov 29 '17 at 22:08
  • 1
    $\begingroup$ According to the table at en.wikipedia.org/wiki/Mersenne_prime it will be precisely 900 years before the corresponding problem will be valid. :) $\endgroup$ – Daniel Schepler Nov 29 '17 at 22:08
4
$\begingroup$

No, $2^{2017}-1$ is not prime. One factor is $9338711$. However, it is true that $2^{p-1} \equiv 1 \mod p$ where $p = 2^{2017}-1$.

$\endgroup$
  • $\begingroup$ That was fast ! How did you find this? $\endgroup$ – Arnaud D. Nov 29 '17 at 22:04
  • $\begingroup$ I used Maple: p:= 2^2017-1; isprime(p); ifactor(p, easy); 2 &^(p-1) mod p; $\endgroup$ – Robert Israel Nov 29 '17 at 22:08
  • $\begingroup$ I wrote the question wrong originally. I'm supposed to test if it is prime using that theorem. By which I assume it means I supposed to use that theorem to demonstrate that it isn't prime, so a computer program doesn't help here. $\endgroup$ – chris Nov 29 '17 at 22:11
  • $\begingroup$ Unfortunately, in this case that theorem doesn't demonstrate that it isn't prime. $\endgroup$ – Robert Israel Nov 29 '17 at 22:13
  • $\begingroup$ Below that question is a line that says p-2^2017-1; Mod(2,p)^(p-1). That is written in a different font, so I'm thinking its meant to be a bit of code for Sage, which we have used a bit in class. Unfortunately, I don't really understand the connection because that looks like it would do either $(2 \mod p)^{p-1}$ or $(p \mod 2)^{p-1}. $\endgroup$ – chris Nov 29 '17 at 22:38

Your Answer

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

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