Take the 2-minute tour ×
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.

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|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 typo...it 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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.