<s>[INST] Show that if $p'=2p+1$ and $p\equiv 3\pmod{4}$, then $2^p\equiv 1\pmod{p'}$ 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'}$.
 [/INST] 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'}$.
</s>