Proof Of Condition for Prime Dividing Mersenne Number
If
\[p\]
and \[2p+1\]
are prime numbers, where \[p \equiv 3 \; (mod \; 4)\]
then \[2p+1\]
divides the Mersenne Number \[M_p=2^p-1\]
.Since
\[2p+1\]
is prime, \[2^{(2p+1)-1} \equiv 1 \; (mod \; 2p+1) \rightarrow 2^{2p} -1 \equiv 0 \; (mod \; 2p+1)\]
by Fermat's Little Theorem/\[2^{2p}-1=(2^p-1)(2^p+1)\]
so by Euclid's Lemma either \[(2p+1) | (2^p-1)=M_p\]
or \[(2p+1) | (2^p+1)\]
.\[p \equiv 3 \; (mod \; 4) \rightarrow p=4k+3\]
for some integer \[k\]
, then \[2p+1=2(4k+3)+1=4k+7\]
.Suppose
\[(2p+1) | (2^p+1)\]
.\[2^{4k+3-1}+1=2^{4k+2}+1 \equiv 0 \; (mod \; 4k+7)\]
which is impossible since \[4^{4k+2} \equiv 0 \; (mod \; 4)\]
.Hence
\[(2p+1) | M_p\]
.Alternative Proof
Let
\[p, \; q=2p+1\]
be prime. \[p=4k+3 \rightarrow q= 2p+1=8k+7 \equiv 7 \; (mod \; 8)\]
. This Theorem on The Quadratic Character of 2 gives \[(2/q)-1\]
so that 2 is a quadratic residue of \[q\]
. Euler's Criterion gives \[2^{\frac{q-1}{2}} \equiv 1 \; (mod \; q)\]
, so that \[q=2p+1\]
divides \[2^{\frac{q-1}{2}}-1=2^p-1=M_p\]
. 
