1
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Nov 28, 2011 at 17:02
  • $\begingroup$ @DimitrijeKostic,If you have an idea how to prove that $M_p\equiv 7 \pmod {24}$ you could write proof as answer.. $\endgroup$
    – Pedja
    Nov 28, 2011 at 17:11
  • $\begingroup$ @DimitrijeKostic CRT isn't needed to deduce $\rm\:a,b\:|\:c\ \Rightarrow\ lcm(a,b)\:|\:c$ $\endgroup$ Nov 28, 2011 at 17:37
  • $\begingroup$ @BillDubuque : Your reasoning is indeed correct and simpler. It's not my fault CRT is fun to invoke! :-) $\endgroup$ Nov 28, 2011 at 17:59

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .