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.

I want to prove following property of Mersenne numbers :

If $p > 3$ then $M_p\equiv 1 \pmod {6\cdot p}$

So, according to Fermat's Little Theorem we may write :

$2^p\equiv 2 \pmod p \Rightarrow 2^p-2=a\cdot p \Rightarrow 2^p-1=a\cdot p +1 \Rightarrow$

$\Rightarrow 2^p-1\equiv 1 \pmod p \Rightarrow M_p\equiv 1 \pmod p$

Now, since $M_p\equiv 7 \pmod {24} $ it follows that :

$M_p=24\cdot a +7 =24\cdot a+6+1=6\cdot(4a+1)+1 \Rightarrow M_p\equiv 1 \pmod 6$

Therefore we may conclude :

$(6 \mid (M_p-1) \land p \mid (M_p-1))\Rightarrow 6\cdot p \mid(M_p-1) \Rightarrow M_p \equiv 1 \pmod{6\cdot p}$

Am I correct ?

share|improve this question
    
You need to make clear where you're using the $p>3$ hypothesis. I think that's probably buried inside your claim that $M_p \equiv 7 \mod 24$. That claim deserves a little more comment. Also, your last line ("Therefore we may conclude") is using the Chinese Remainder Theorem, and you should say that. Other than that, it looks right. –  Dimitrije Kostic Nov 28 '11 at 17:02
    
@DimitrijeKostic,If you have an idea how to prove that $M_p\equiv 7 \pmod {24}$ you could write proof as answer.. –  pedja Nov 28 '11 at 17:11
    
@DimitrijeKostic CRT isn't needed to deduce $\rm\:a,b\:|\:c\ \Rightarrow\ lcm(a,b)\:|\:c$ –  Bill Dubuque Nov 28 '11 at 17:37
    
@BillDubuque : Your reasoning is indeed correct and simpler. It's not my fault CRT is fun to invoke! :-) –  Dimitrije Kostic Nov 28 '11 at 17:59

2 Answers 2

up vote 1 down vote accepted

There is nothing incorrect, but there are a few things that could be changed. We only need $p>2$.

From $2^p \equiv 2 \pmod {p}$ one should conclude $M_p=2^p -1\equiv 1 \pmod{p}$ immediately, without the detour through $a\cdot p +1$.

A similar needless detour is made when from $M_p\equiv 7\pmod{24}$ it is argued that $M_p \equiv 1 \pmod{p}$. Instead, if we are going to go that route, we could note that since $6$ is a factor of $24$, we have $M_p\equiv 7\equiv 1\pmod{6}$. But the assertion $M_p \equiv 7 \pmod{24}$ may not be familiar to people, and it is easy to prove. We won't bother, and will only prove what you need.

To prove your result, all you need is to show that $M_p \equiv 1 \pmod{6}$. It is clear that $M_p$ is odd, that is, $M_p\equiv 1 \pmod{2}$. So all we need is to show that $M_p \equiv 1 \pmod 3$. We have $2\equiv -1\pmod 3$. So if $n$ is odd, then $2^n\equiv (-1)^n \pmod{3}$, and therefore $M_p=2^p-1\equiv (-1)-1\equiv 1\pmod {3}$.

It is a standard fact about congruences that if $x\equiv a \pmod{m}$ and $x\equiv a \pmod{n}$, then $x\equiv a \pmod{\text{lcm}(m,n)}$. You chose to prove it in the special case $m=6$, $n=p$. That's fine, perhaps not needed.

Comment: The congruence machinery is very powerful, and it is useful to learn to exploit it efficiently.

share|improve this answer

Note that $M_p= 2^p -1 = (2-1)(2^{p-1} + 2^{p-2} + \dots + 2^2 + 2^1 + 1)$. If $p>3$ then modding out by $2^3=8$ leaves $2^2+2^1+1 =7$ behind. Also $M_p = 2^p-1$ and $p$ is odd, so $2^p \equiv 2 \mod 3$, which means $M_p \equiv 1\mod 3$. The Chinese Remainder Theorem then applies and shows that $M_p \equiv 7 \mod (3*8)$.

share|improve this answer

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.