# Proof that $2^{2017} -1$ is prime

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.

• 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.) – rogerl Nov 29 '17 at 22:03
• 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). – Arnaud D. Nov 29 '17 at 22:04
• @ArnaudD. I wrote it wrong. I'm being asked to test if it is prime using that theorem. – chris Nov 29 '17 at 22:08
• According to the table at en.wikipedia.org/wiki/Mersenne_prime it will be precisely 900 years before the corresponding problem will be valid. :) – Daniel Schepler Nov 29 '17 at 22:08

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$.
• 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}. – chris Nov 29 '17 at 22:38