# Thread: Mersenne numbers

1. ## Mersenne numbers

Let M_n denote the nth mersenne number (note that here n can be composite).

Prove the following (or find counter example):

If M_n is not squarefree, then the square factor is a factor of n.

PS: I think this is false, however it may take awhile to find a counterexample.

2. Just for correct understanding, what you wanto to prove [or disprove...] is the following...

Let $\displaystyle N= 2^{n}-1$ and suppose that some $\displaystyle p^{2}$ with p prime devides N. Then p devides n...

Is it correct?...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

3. Yes that is correct. Don't spend too much time on this one though as it is really a research question. Back in the fall, my friend and I looked at the square factors of 2^n -1 and 2^n +1 for all n up to around 500 (I think). We found one example for 2^n +1 in which a square factor was found which wasn't a factor of n. For 2^n -1, no counterexamples were found.

Try coming up with a probability argument. That is, why would it be unlikely that
2^n = 1 (mod p^2) and yet n not have p as a divisor?

4. To date, all known Mersenne primes are squarefree, though there is speculation that there are some non-squarefree primes. So we must note that n not just can but MUST be a composite number.

A good counterexample would be the Wieferich primes:

A prime p is a Wieferich prime if $\displaystyle p^2$ divides $\displaystyle 2^{p-1} - 1$. There are only two known, and this has been tested to approximately 32 trillion digits. And these obviously do not meet the criteria of your problem.

1093 is a known Wieferich prime (1092 is composite):

$\displaystyle 1093^2 | 2^{1092} - 1$

$\displaystyle 1093 \not | \ 1092$

So, the conjecture is false.

5. Hey thanks a bunch. So Wieferich primes eh. I'll remember that one. I wonder if infinitely many counterexamples exist.

6. Actually, here's a couple of interesting theorems:

Theorem 1: Let p and s be odd primes. If p divides $\displaystyle M_s$, then $\displaystyle p = 1(mod \ s)$ and $\displaystyle p = \pm 1 (mod \ 8)$

Proof:

If p divides $\displaystyle M_s$, then $\displaystyle 2^s = 1 (mod \ p)$ and the order of 2 (mod p) divides the prime s, so it must be s. By Fermat's Little Theorem the order of 2 also divides p-1, so p - 1 = 2ks. This gives

$\displaystyle p^{(p-1)/2} = 2^{sk} = 1 (mod \ p)$

so 2 is a quadratic residue mod p and it follows $\displaystyle p = \pm 1 (mod \ 8)$, which completes the proof.

Theorem 2: Let p and s be primes. If $\displaystyle p^2$ divides $\displaystyle M_s$, then $\displaystyle 2^{(p-1)/2} = 1 (mod \ p^2)$, which says that p is a Wieferich prime.

Proof:

First note that p and s must both be odd. In theorem 1 it was shown that if p divides $\displaystyle M_s$, then $\displaystyle p = 2ks + 1$ for some integer k. So

$\displaystyle 2^s = 2^{(p-1)/2k} = 1 (mod \ p^2)$

All we do is raise this to the 2k power to get:

$\displaystyle 2^{2sk} = 2^{(p-1)} = 1 (mod \ p^2)$

And that's how you arrive at the Wieferich primes. Good luck with the research.

7. Thanks Aryth. Its neat stuff. Are you into Mersenne numbers?

Here is a neat trick:

Suppose n is composite, and let p_1,.....,p_k be the distinct prime factors of n.

If $\displaystyle D = lcm (2^\frac{n}{p_1} - 1,2^\frac{n}{p_2} - 1,.....2^\frac{n}{p_k} - 1)$

and $\displaystyle 2^n - 1$ is squarefree, then every prime factor of $\displaystyle \frac{2^n - 1}{D}$ is such that p = 1(modn).

8. Just filled in a big missing part of the previous incomplete text, so you may want to reread last post.

9. ## Clarify

I'm sorry, I think I'm misunderstanding the problem...

$\displaystyle 3^2|2^{6}-1$
$\displaystyle 3^2|2^{12}-1$
$\displaystyle 3^2|2^{18}-1$
$\displaystyle 5^2|2^{20}-1$
$\displaystyle 7^2|2^{21}-1$
$\displaystyle 3^2|2^{24}-1$

In all of these (quite small) examples, $\displaystyle p^2|2^n-1$ and $\displaystyle p|n$. You are saying that p=1093 and n=1092 is a counterexample to this apparent relation?

10. Yes, that is what I'm saying. There are two known counterexamples to the original conjecture. For small values it obviously is true, but when one tries to generalize the conjecture it comes to be a false one. The first blow is when you consider only the non-squarefree Mersenne numbers, meaning that n must be composite, and since one prime number is 1093, which (when squared) does divide $\displaystyle 2^{1092} - 1 = 2^{p-1} - 1$ (I proved that in my previous post.) and does not divide 1092, p = 1093 and n = 1092 must be a counterexample. Generally, a counterexample occurs when p is prime and n = p-1 causes this to hold:

$\displaystyle 2^n = 1 (mod \ p^2)$

Also known as the Wieferich Primes.

11. ## Infinite Counterexamples

There are indeed an infinite number of counterexamples, jamix:

$\displaystyle 1093^2|2^{364}-1$
$\displaystyle 1093^2|2^{728}-1$
$\displaystyle 1093^2|2^{1092}-1$
$\displaystyle 1093^2|2^{1456}-1$
$\displaystyle 1093^2|2^{1820}-1$

$\displaystyle 3511^2|2^{1755}-1$
$\displaystyle 3511^2|2^{3510}-1$
...
$\displaystyle p^2|2^r-1$ implies $\displaystyle p^2|2^{kr}-1$ for any k

Furthermore, for any prime p, there are either no counterexamples M_n or there is a counterexample M_n where n<p and M_kn provides an infinite number of bigger counterexamples. Cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.

12. Good stuff Media man . Lets see if I can give you guys something a little different.

Suppose that prime p is such that 2 has order k. Show that

$\displaystyle 2^{kp} -1$ is divisible by $\displaystyle p^2$

Furthermore, can you guys think of some other similar types of questions?

13. ## That's a no-no

Um, Fermat's Little Theorem says for any odd prime $\displaystyle p$, $\displaystyle p|2^{p-1}-1$, so $\displaystyle 2^{p-1}+1 \equiv 2 (\bmod p)$, so there can never be a $\displaystyle p^2|2^{p-1}+1(\bmod p^2)$

14. Okay thanks, I just changed it to a question that should make sense now.

15. Just fixed another typo. I'll have to come back to this when I'm not doing multiple tasks.

Page 1 of 2 12 Last