Mersenne numbers

**jamix** · April 12th 2009, 02:12 PM

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.

**chisigma** · April 14th 2009, 01:40 AM

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

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

Is it correct?...

Kind regards

$\chi$ $\sigma$

**jamix** · April 14th 2009, 10:34 AM

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?

**Aryth** · April 14th 2009, 12:10 PM

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 $p^2$ divides $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):

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

$1093 \not | \ 1092$

So, the conjecture is false.

**jamix** · April 14th 2009, 12:39 PM

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

**Aryth** · April 14th 2009, 12:57 PM

Actually, here's a couple of interesting theorems:

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

Proof:

If p divides $M_s$ , then $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

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

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

Theorem 2: Let p and s be primes. If $p^2$ divides $M_s$ , then $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 $M_s$ , then $p = 2ks + 1$ for some integer k. So

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

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

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

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

**jamix** · April 14th 2009, 01:30 PM

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 $D = lcm (2^\frac{n}{p_1} - 1,2^\frac{n}{p_2} - 1,.....2^\frac{n}{p_k} - 1)$

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

**jamix** · April 14th 2009, 01:40 PM

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

**Media_Man** · April 15th 2009, 06:35 AM

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

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

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

**Aryth** · April 15th 2009, 07:44 AM

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 $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:

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

Also known as the Wieferich Primes.

**Media_Man** · April 15th 2009, 10:55 AM

There are indeed an infinite number of counterexamples, jamix:

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

$3511^2|2^{1755}-1$
$3511^2|2^{3510}-1$
...
$p^2|2^r-1$ implies $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.

**jamix** · April 15th 2009, 01:05 PM

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

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

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

**Media_Man** · April 15th 2009, 01:22 PM

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

**jamix** · April 15th 2009, 01:37 PM

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

**jamix** · April 15th 2009, 01:54 PM

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

Thread: Mersenne numbers

LinkBack

Thread Tools

Display

Mersenne numbers

Clarify

Infinite Counterexamples

That's a no-no

Similar Math Help Forum Discussions

Mersenne numbers

Mersenne Primes

Divisibility of Mersenne numbers?

Mersenne prime

[SOLVED] New Mersenne numbers conjecture

Search Tags