Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 9 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.