# $2^{251 }-1$ not Mersenne Prime

I need to show that $2^{251} - 1$ is not a Mersenne prime. Hard because $251$ is prime. If i can show that a prime $p$ is congruent to $3 \bmod 4$, and $q = 2p + 1$ is a prime, then $2^p$ is congruent to $1 \bmod q$... then I can show that $2^{251} - 1$ is not prime. Having difficulty with the middle part .

Thank you for aid!

-

You have almost done it. Note that $2(251)+1$ is prime. It follows that $503$ divides your Mersenne number.

Remark: The relevant theorem was not stated precisely in the OP. Here is a precise statement. Let $q$ be a prime of the form $4k+3$. If $2q+1$ is prime, then $2q+1$ divides $2^q-1$.

-
Yes, this is the theorem I'd like to show – Winnie Nov 13 '12 at 2:30
Your post did not make it clear that you wanted to prove the theorem. It seemed you wanted to use it. But if you post a new question about proving the theorem, I am sure someone will write out a proof. I hope you are familiar with Euler's Criterion, and facts about the primes that have $2$ as a quadratic residue. – André Nicolas Nov 13 '12 at 2:35
Sorry, I don't have the best English. I've seen this "Euler's Criterion" – Winnie Nov 13 '12 at 2:38