# Mersenne numbers

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Apr 12th 2009, 03:12 PM
jamix
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.
• Apr 14th 2009, 02:40 AM
chisigma
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$
• Apr 14th 2009, 11:34 AM
jamix
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?
• Apr 14th 2009, 01:10 PM
Aryth
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.
• Apr 14th 2009, 01:39 PM
jamix
Hey thanks a bunch. So Wieferich primes eh. I'll remember that one. I wonder if infinitely many counterexamples exist.
• Apr 14th 2009, 01:57 PM
Aryth
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.
• Apr 14th 2009, 02:30 PM
jamix
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).
• Apr 14th 2009, 02:40 PM
jamix
Just filled in a big missing part of the previous incomplete text, so you may want to reread last post.
• Apr 15th 2009, 07:35 AM
Media_Man
Clarify
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?
• Apr 15th 2009, 08:44 AM
Aryth
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.
• Apr 15th 2009, 11:55 AM
Media_Man
Infinite Counterexamples
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.
• Apr 15th 2009, 02:05 PM
jamix
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?
• Apr 15th 2009, 02:22 PM
Media_Man
That's a no-no
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)$
• Apr 15th 2009, 02:37 PM
jamix
Okay thanks, I just changed it to a question that should make sense now.
• Apr 15th 2009, 02:54 PM
jamix
Just fixed another typo. I'll have to come back to this when I'm not doing multiple tasks.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last