Page 1 of 2 12 LastLast
Results 1 to 15 of 27

Math Help - Mersenne numbers

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    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.
    Last edited by Aryth; April 14th 2009 at 01:25 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2008
    Posts
    148
    Hey thanks a bunch. So Wieferich primes eh. I'll remember that one. I wonder if infinitely many counterexamples exist.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jun 2008
    Posts
    148
    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).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2008
    Posts
    148
    Just filled in a big missing part of the previous incomplete text, so you may want to reread last post.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    652
    Thanks
    2
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    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.
    Last edited by Media_Man; April 15th 2009 at 12:14 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jun 2008
    Posts
    148
    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?
    Last edited by jamix; April 15th 2009 at 02:52 PM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    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)
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jun 2008
    Posts
    148
    Okay thanks, I just changed it to a question that should make sense now.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Jun 2008
    Posts
    148
    Just fixed another typo. I'll have to come back to this when I'm not doing multiple tasks.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Mersenne numbers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 14th 2010, 07:06 PM
  2. Mersenne Primes
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: June 7th 2010, 08:15 AM
  3. Divisibility of Mersenne numbers?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 23rd 2010, 03:05 AM
  4. Mersenne prime
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: January 17th 2009, 02:16 PM
  5. [SOLVED] New Mersenne numbers conjecture
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 29th 2008, 04:59 PM

Search Tags


/mathhelpforum @mathhelpforum