1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – futuremathteacher Jun 9 '15 at 19:22
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you explain why it suffices to show $p|2^p-2$? Does it have something to do with the binomial theorem? $\endgroup$ – futuremathteacher Jun 9 '15 at 20:45
  • 1
    $\begingroup$ @futuremathteacher It is because $2^{ab}-1=\left(2^a-1\right)\left( 2^{ab-a}+2^{ab-a-1}+\cdots+ 2+1\right)$. $\endgroup$ – user26486 Jun 9 '15 at 21:08
  • $\begingroup$ @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$. $\endgroup$ – user26486 Jun 9 '15 at 21:11

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.