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, 01:40 AM
Just for correct understanding, what you wanto to prove [or disprove...] is the following...
Let and suppose that some with p prime devides N. Then p devides n...
Is it correct?...
Apr 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?
Apr 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 divides . 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):
So, the conjecture is false.
Apr 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.
Apr 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 , then and
If p divides , then 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
so 2 is a quadratic residue mod p and it follows , which completes the proof.
Theorem 2: Let p and s be primes. If divides , then , which says that p is a Wieferich prime.
First note that p and s must both be odd. In theorem 1 it was shown that if p divides , then for some integer k. So
All we do is raise this to the 2k power to get:
And that's how you arrive at the Wieferich primes. Good luck with the research.
Apr 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.
and is squarefree, then every prime factor of is such that p = 1(modn).
Apr 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.
Apr 15th 2009, 06:35 AM
I'm sorry, I think I'm misunderstanding the problem...
In all of these (quite small) examples, and . You are saying that p=1093 and n=1092 is a counterexample to this apparent relation?
Apr 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 (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:
Also known as the Wieferich Primes.
Apr 15th 2009, 10:55 AM
There are indeed an infinite number of counterexamples, jamix:
... implies 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, 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
is divisible by
Furthermore, can you guys think of some other similar types of questions?
Apr 15th 2009, 01:22 PM
That's a no-no
Um, Fermat's Little Theorem says for any odd prime , , so , so there can never be a
Apr 15th 2009, 01:37 PM
Okay thanks, I just changed it to a question that should make sense now.
Apr 15th 2009, 01:54 PM
Just fixed another typo. I'll have to come back to this when I'm not doing multiple tasks.