# Is this proof about Mersenne numbers acceptable?

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 ?

-
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

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.

-

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

-