Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Let us denote a prime factor of Mersenne number as $q$ . How to prove following :

$(M_p\equiv0\pmod q \land q\equiv 1 \pmod 8) \Rightarrow q\equiv 1 \pmod {4\cdot p}$

There is a proof that any prime $q$ that divides $2^p − 1$ must be $1$ plus a multiple of $2p$ but I think that is possible to prove this stricter condition. I guess that one should use Fermat's Little Theorem as starting point for this proof .

share|cite|improve this question
By Fermat's Theorem, $q\equiv 1 \pmod{p}$. If further we ask that $q\equiv 1\pmod 8$, then $q\equiv 1 \pmod {8p}$. – André Nicolas Nov 27 '11 at 20:01
@AndréNicolas,you have small should be $q^{p-1} \equiv 1 \pmod p $ – pedja Nov 28 '11 at 7:07
It is true that $q^{p-1}\equiv 1 \pmod p$. But I do mean $q\equiv 1 \pmod {p}$. Since $q$ divides $2^p-1$, we know that $2^p\equiv 1 \pmod q$. By Fermat's theorem, $2^{q-1}\equiv 1 \pmod{q}$. Since the order of $2$ modulo $q$ is not $1$, it follows that this order is $p$, and therefore $p$ divides $q-1$. Or in other words, $q \equiv 1 \pmod{p}$. – André Nicolas Nov 28 '11 at 7:24

If $x\equiv a\pmod{m}$ and $x\equiv b\pmod{n}$, then $x$ is uniquely defined modulo $\frac{mn}{\gcd(m,n)}$. The proof is that we also have $x\equiv a\pmod{\frac{m}{\gcd(m,n)}}$ and $x\equiv b\;(n)$. Now $\frac{m}{\gcd(m,n)}$ and $n$ are two coprime moduli. The Chinese Remainder Theorem implies a unique solution for $x$ modulo the product of the moduli.

Given that $q\equiv1\;\pmod{8}$ and the fact you cite that $q\equiv1\pmod{2p}$, then since $p$ is coprime to $2$, it must be that $q\equiv1\pmod{8p}$, since $8p = \frac{8\cdot2p}{\gcd(8,2p)}$. This is even stronger than what you have proposed.

share|cite|improve this answer

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.