Page 2 of 2 FirstFirst 12
Results 16 to 27 of 27

Math Help - Mersenne numbers

  1. #16
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Wiki

    According to Wiki (Wieferich prime - Wikipedia, the free encyclopedia), for a Mersenne number M_q, if there exists a p^2|M_q where p and q are relatively prime, then p is a Wieferich prime. This result does not seem trivial to me, and it is uncredited, so I wonder if it is correct. It is equivalent to saying that not only are Wieferich primes counterexamples to your conjecture, but they are the only counterexamples. If this is correct, then you can prove there are only finite Wieferich numbers by placing a lower bound on your conjecture.
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by Media_Man View Post
    According to Wiki (Wieferich prime - Wikipedia, the free encyclopedia), for a Mersenne number M_q, if there exists a p^2|M_q where p and q are relatively prime, then p is a Wieferich prime. This result does not seem trivial to me, and it is uncredited, so I wonder if it is correct.
    This part of the theorem is true for sure. If p^2|M_q then q| p-1, which implies that
    2^q - 1|2^(p-1) - 1, from which p^2|2^(p-1) - 1 follows. The reverse direction of that theorem (recall that the theorem is 'iff') is not at all obvious to me.

    Quote Originally Posted by Media_Man View Post
    It is equivalent to saying that not only are Wieferich primes counterexamples to your conjecture, but they are the only counterexamples. If this is correct, then you can prove there are only finite Wieferich numbers by placing a lower bound on your conjecture.
    I'm not sure I follow you here. Can you explain? Remember that in my conjecture, the integer n in 2^n -1 can be composite, whereas in theorem quoted on wiki, n is a prime.
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Member
    Joined
    Jun 2008
    Posts
    148
    Actually that theorem on wiki is flawed (see link 5 at bottom of page and scroll down to the conjecture about square factor of M_q).

    Indeed it is an open problem whether or not there are any Mersenne numbers (with prime index) that posses square factors. The two currently known Wieferich primes don't work.
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    All Jamix primes are Wieferich primes

    Here are four lemmas I have been able to prove. I am not well versed enough in number theory to know which are obvious or already known. Let me know and I can provide proofs for any or all of them:

    Let p be an odd prime and define r as the lowest positive integer satisfying 2^r \equiv 1 (\bmod p). Denote M_n as the nth Mersenne 2^n-1. Then the following hold:

    (1) if M_a \equiv M_b (\bmod n) then M_{ka} \equiv M_{kb} (\bmod n) for any a,b,n,k
    (2) r|p-1
    (3) if p|M_n then r|n
    (4) M_{kr} \equiv kM_r (\bmod p^2) for all k

    Theorem: If p^2|2^n-1 for some odd prime p and positive integer n, then p|n or p is a Wieferich prime.

    Proof: Let p^2|2^n-1 for some odd prime p and positive integer n. By (3), p^2|2^{kr}-1 for some positive int k. By (4), p^2|k(2^r-1). Since p|2^r-1 by definition of r, then p|k or p^2|2^r-1. If p|k then p|n. By (1) and (2), if p^2|2^r-1 then p^2|2^{p-1}-1. Therefore, either p|n or p is a Wieferich prime.

    Note: I have verified this numerically up to n=10,000. The only counterexamples I found to your original conjecture were the two known Wieferich primes, 1093 and 3511. I thought this was odd since your conjecture did not seem as strong as the Wieferich condition. But the above proof does indeed verify it. If p^2|2^n-1 for some p \not | \ n (a Jamix prime), then p is a Wieferich. So p is a Jamix prime iff p is a Wieferich prime. Short-lived legacy - sorry.

    So, pick your favorite large integer L>3511, and if you can show that for any p, your conjecture holds for all n>L, that would mean there are no counterexamples >L, i.e. no Wieferich primes >L. (It is an open question whether there are a finite number of them or infinite. If there are any other Wieferich primes besides 1093 and 3511, they must be greater than 10^{25} or something ridiculous like that.)

    Fermat's Little Theorem tells us that p|2^{p-1}-1 for all odd primes p. By (2), for some primes p there exists an r<p-1 where r|p-1 satisfying p|2^r-1, but for some primes there does not. A question I am interested in is why this r<p-1 exists only some of the time? For which primes does r not exist? Are there only a finite number of either case?
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Member
    Joined
    Jun 2008
    Posts
    148
    Could you prove (4)? I think this might be a result of Abel but I don't I have time to check (I've got a stat exam in a couple of hours so I'm mostly online to review lecture notes).
    Follow Math Help Forum on Facebook and Google+

  6. #21
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    A tedious and tree-killing proof

    For some odd prime p, define r as the lowest positive int satisfying 2^r \equiv 1 (\bmod p)

    Lemma (4) M_{kr} \equiv kM_r (\bmod p^2)

    Proof: 2^r \equiv 1 (\bmod p) by definition.
    So 2^r \equiv sp+1 (\bmod p^2) for some positive int s
    Thus, 2^{kr} \equiv (sp+1)^k (\bmod p^2)
    Expanding by the binomial theorem, (sp+1)^k=p^2(...)+sp+1
    So 2^{kr} \equiv sp+1 (\bmod p^2)
    Now, 2^{kr}(2^r-1) \equiv (sp+1)sp (\bmod p^2)
    Multiplying, 2^{kr}(2^r-1) \equiv (s^2p^2+sp) (\bmod p^2)
    So 2^{kr}(2^r-1) \equiv sp (\bmod p^2)
    So 2^{kr}(2^r-1) \equiv 2^r-1 (\bmod p^2)
    Distribute 2^{(k+1)r}-2^{kr} \equiv 2^r-1 (\bmod p^2)
    Now 2^{(k+1)r}-1-(2^{kr}-1) \equiv 2^r-1 (\bmod p^2)
    Giving us M_{(k+1)r}-M_{kr}\equiv M_r (\bmod p^2)
    So M_{(k+2)r}-M_{kr} = M_{(k+2)r}-M_{(k+1)r}+M_{(k+1)r}-M_{kr} = M_r+M_r = 2M_r (\bmod p^2)
    We can generalize this to M_{(k+a)r}-M_{kr} = aM_r (\bmod p^2)
    Letting k=0, M_{ar}-M_0 = aM_r (\bmod p^2)
    Noting that M_0=2^0-1=1-1=0, M_{ar} = aM_r (\bmod p^2)


    I'm sure there's a less tedious way of doing this, but as you can see, some fancy and admittedly liberal manipulation of modular arithmetic gets it done. A peculiar property of r (the "order" of 2, mod p, I believe) and Mersenne numbers.

    Note: If s=0 in the above construction, then p is a Wieferich prime. Looking at these on a computer, s appears to be pretty random, as does r. This leads me to wonder if they are computable at all. My guess is no.
    Follow Math Help Forum on Facebook and Google+

  7. #22
    Member
    Joined
    Jun 2008
    Posts
    148
    I was able to verify the theorem you put (there are a couple of well known tricks that make the proof very simple). If you don't mind though, let me nitpick through yours.

    Quote Originally Posted by Media_Man View Post
    Theorem: If p^2|2^n-1 for some odd prime p and positive integer n, then p|n or p is a Wieferich prime.

    Proof: Let p^2|2^n-1 for some odd prime p and positive integer n. By (3), p^2|2^{kr}-1 for some positive int k
    How does this follow from (3)? Did you mean (1) or (2) instead?


    Quote Originally Posted by Media_Man View Post
    For some odd prime p, define r as the lowest positive int satisfying 2^r \equiv 1 (\bmod p)

    Lemma (4) M_{kr} \equiv kM_r (\bmod p^2)

    Proof: 2^r \equiv 1 (\bmod p) by definition.
    So 2^r \equiv sp+1 (\bmod p^2) for some positive int s
    Thus, 2^{kr} \equiv (sp+1)^k (\bmod p^2)
    Expanding by the binomial theorem, (sp+1)^k=p^2(...)+sp+1

    I got up to here in your proof to (4). We have that (sp+1)^k=p^2(...)+ksp+1 by expanding though.


    Are you familiar with Euler's famous theorem (seehttp://en.wikipedia.org/wiki/Euler%27s_theorem otherwise)? Here is a proof using this and one other trick.


    Proof: We know that p^2|2^{p(p-1)}-1 by Euler's theorem. As p^2|2^{n}-1, it follows that (this is the other trick!) the order of 2 must divide gcd(n,p*(p-1)). If gcd(n,p)=1, then gcd(n,p*(p-1)) = gcd(n,p-1). As gcd(n,p-1)|p-1, it follows that p^2|2^{p-1}-1 making it a Wieferich number.


    Quote Originally Posted by Media_Man View Post
    Fermat's Little Theorem tells us that p|2^{p-1}-1 for all odd primes p. By (2), for some primes p there exists an r<p-1 where r|p-1 satisfying p|2^r-1, but for some primes there does not. A question I am interested in is why this r<p-1 exists only some of the time? For which primes does r not exist? Are there only a finite number of either case?
    r is called the order of 2. If r=p-1, then we say that 2 is primitive with respect to p. The questions your asking are well known, however I don't think they have all been solved. I believe (but I'm not sure) that it is still an open question whether or not there are infinitely many primes p such that 2 is primitive.
    Follow Math Help Forum on Facebook and Google+

  8. #23
    Member
    Joined
    Jun 2008
    Posts
    148
    Media_Man and Aryth

    If you guy don't mind, I'd like to write up a 1-2 page paper of the theorem recently posted by Media_Man, with you guys as coauthors. I don't know if it will necessarily be accepted, but I'll ask my supervisor on Monday which Journal would be most optimal to send a short result like this to. So long as its new (which I'm still not sure of), I think its worth a shot. Let me know what you guys think.
    Follow Math Help Forum on Facebook and Google+

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

    My mistake...

    I got up to here in your proof to (4). We have that (sp+1)^k=p^2(...)+ksp+1 by expanding though.
    Yes, that is correct, that is my mistake. The proof still holds, though, as three lines later, the ksp term would become ks^2p^2 and would still disappear via the modulus of p^2. Good catch.

    By (3), p^2|2^{kr}-1 for some positive int k
    (3) actually follows from (1) and (2), via Fermat's Little Theorem. Since p^2|2^n-1 , then p|2^n-1 , so by (3) r|n .

    Proof: We know that p^2|2^{p(p-1)}-1 by Euler's theorem. As p^2|2^{n}-1, it follows that (this is the other trick!) the order of 2 must divide gcd(n,p*(p-1)). If gcd(n,p)=1, then gcd(n,p*(p-1)) = gcd(n,p-1). As gcd(n,p-1)|p-1, it follows that p^2|2^{p-1}-1 making it a Wieferich number.
    Much more succinct. I figured as such.

    If you guy don't mind, I'd like to write up a 1-2 page paper of the theorem recently posted by Media_Man, with you guys as coauthors.
    Sounds good. Although the above proof derived from Euler gives a very nice shortcut to all the crap I went through. The major result here is that the Wieferich primes are the only counterexamples to Jamix's original conjecture that p|2^n-1 implies p|n . This gives us another angle of defining Wieferich primes that may (or may not) aid in proving how many there are.
    Follow Math Help Forum on Facebook and Google+

  10. #25
    Member
    Joined
    Jun 2008
    Posts
    148
    Thats great. I sent Aryth a pm to ask him as well. I'll write this up soon and post a first draft here for you (and hopefully Aryth) to comment on soon.
    Follow Math Help Forum on Facebook and Google+

  11. #26
    Member
    Joined
    Jun 2008
    Posts
    148
    Hey guys,

    sorry to say, but that small result which I thought was new turns out actually to not be new (look at the bottom paragraph here: Wieferich Prime -- from Wolfram MathWorld). Oh well.
    Follow Math Help Forum on Facebook and Google+

  12. #27
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    651
    Thanks
    1
    Awards
    1
    I knew that it was older material. There are conjectures on the Wieferich primes dating back to 1910. I've done my fair share of research on them, they seem to have interesting properties, but alas, hardly anything about the Wieferich primes is unknown.
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum