# Show that if $N=2^p -1$, $p$ prime, then $2^{N-1} \equiv 1$ mod $N$

$N=2^p -1$, $p$ prime $\implies$ $2^{N-1} \equiv 1$ mod $N$

I thought about using Euler's Theorem: clearly $(2, 2^p -1)=1$, so $2^{\varphi (N)} \equiv 1$ mod $N$, which will finish the proof iff N is a prime.

Uh oh, $2^{11} -1$ is not prime, so this argument won't work.

• I thought about using Euler's Theorem: clearly $(2, 2^p -1)=1$, so $2^{\varphi (N)} \equiv 1$ mod $N$, which will finish the proof iff N is a prime. – futuremathteacher Jun 9 '15 at 19:22

It is enough to have $2^p\equiv 1\pmod{\! N}$. By Little Fermat $\frac{2^p-2}{p}=\frac{N-1}{p}$ is an integer.
$$2^p\equiv 1\pmod{\! N}\stackrel{\frac{N-1}{p}}\implies 2^{N-1}\equiv 1\pmod{\! N}$$
This is equivalent to showing that if $p$ is prime, then $2^p-1 \mid 2^{2^p-2}-1.$ It therefore suffices to prove that $p \mid 2^p-2$, which is a clear consequence of Fermat's little theorem.
• Can you explain why it suffices to show $p|2^p-2$? Does it have something to do with the binomial theorem? – futuremathteacher Jun 9 '15 at 20:45
• @futuremathteacher It is because $2^{ab}-1=\left(2^a-1\right)\left( 2^{ab-a}+2^{ab-a-1}+\cdots+ 2+1\right)$. – user26486 Jun 9 '15 at 21:08
• @futuremathteacher Btw, my answer uses this too, but in the form of Congruence Power Rule (which can be proved using this factorization). Also, as I said, $N\mid 2^p-1$ is enough. This is because if $N\mid 2^p-1\mid 2^{2^p-2}-1$, then $N\mid 2^{2^p-2}-1$. – user26486 Jun 9 '15 at 21:11