Unsure if this is relevant: In the previous part of the question I deduced that if a number of the form $2^n-1$ is prime (a Mersenne prime), $n$ must also be prime.

Question: For primes $p$ and $p'$, where $p'=2p+1$, does $p\equiv 3\pmod{4}$ imply that $2^p\equiv 1\pmod{p'}$?

Attempt: By Euler's theorem, since $(2,p)=(2,p')=1$ we have $2^{\phi(p')}\equiv 2^{p'-1}\equiv 1\pmod{p'}$. Substituting $p'=2p+1$, we obtain $2^{p'-1}\equiv2^{2p}\equiv 1\pmod{p'}$, and thus $2^p\equiv\pm 1\pmod{p'}$.

Letting $p\equiv 4p_0+3$, then $p'\equiv 2(4p_0+3)+1 \equiv 8p_0+7$. So $p'\equiv 7\pmod{8}$.

I am stuck as to how to link this last bit to show that $2^p\equiv 1\pmod{p'}$, not $2^p\equiv -1\pmod{p'}$.


As you pointed out, $p'$ is of the form $8k+7$. You have probably already seen the proof of the fact that $2$ is a quadratic residue of the odd prime $q$ if and only if $q\equiv \pm 1\pmod{8}$.

So $2$ is a quadratic residue of $p'$, say $2\equiv x^2\pmod{p}$. But $x^{p'-1}=x^{2p}\equiv 1\pmod{p'}$ and therefore $2^{p}\equiv 1\pmod{p'}$.

  • 1
    $\begingroup$ Yes, thank you, fixed. I am typo prone, particularly when I am typing outside in bright sunshine while smoking. $\endgroup$ Mar 22 '15 at 18:07

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.