Loading ...
Sorry, an error occurred while loading the content.

Re: Mersenne number question

Expand Messages
  • ratwain
    ... have ... divisor ... the ... Cool question!! Don t you just need to use Fermat s Small Theorem. 1) If 2*p+1 divides 2^p-1 You have a prime p and a prime
    Message 1 of 3 , Mar 27, 2003
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "jbrennen" <jack@b...> wrote:
      > I was idly looking for Mersenne numbers (2^p-1, p prime) which
      have
      > many "small" divisors. Of course, it is well known that any
      divisor
      > of 2^p-1 must be of the form 2*a*p+1, for some integer a. (With
      the
      > solitary exception that when p==2, 3 divides 2^p-1 -- those damn
      > even primes don't know how to behave...)
      >
      > A couple of things I noticed, which are true for all p<=10000.
      >
      > If 2*p+1 divides 2^p-1, either p==3 or p==(11 mod 12).
      >
      > 4*p+1 never divides 2^p-1.
      >
      > If 6*p+1 divides 2^p-1, p==(1 mod 4).
      >
      > If 8*p+1 divides 2^p-1, p==(5 mod 6).
      >
      > If 10*p+1 divides 2^p-1, p==(7 mod 12).
      >
      > 12*p+1 never divides 2^p-1.
      >
      > If 14*p+1 divides 2^p-1, p==(5 mod 12).
      >
      > If 16*p+1 divides 2^p-1, p==(1 mod 6).
      >
      > If 18*p+1 divides 2^p-1, p==(3 mod 4).
      >
      > 20*p+1 never divides 2^p-1.
      >
      > If 22*p+1 divides 2^p-1, p==(1 mod 12).
      >
      > If 24*p+1 divides 2^p-1, p==(1 mod 2).
      >
      >
      > And then that same cycle of 12 rules seems to repeat...
      >
      > Are these results well known? Are they true for all p?
      > Does the cycle repeat as it seems to?


      Cool question!!

      Don't you just need to use Fermat's Small Theorem.

      1) If 2*p+1 divides 2^p-1
      You have a prime p and a prime 2*p+1 -- I assume the divisor is
      also a prime number, you don't explicitly say
      :. p is 5%6
      Consider 2 cases, p is 1%4 and p is 3%4
      First let p = 4*n+1
      2^p % (2*p+1)
      = 2^(4*n+1) % (2*(4*n+1)+1)
      = 2^(4*n+1) % (8*n+3)
      = Jacobi(2|8*n+3)
      = -1
      :. 2^p-1 is -2%(2*p+1) and not zero

      Second let p = 4*n+3
      2^p % (2*p+1)
      = 2^(4*n+3) % (2*(4*n+3)+1)
      = 2^(4*n+3) % (8*n+7)
      = Jacobi(2|8*n+7)
      = +1
      :. 2^p-1 is 0%(2*p+1)

      :. p is 3%4 and 5%6
      :. p is 11%12


      2) If 4*p+1 divides 2^p-1
      You have a prime number p and a prime number 4*p+1 -- again making
      that assumption.
      Consider p=2n+1
      2^p % (4*p+1)
      = 2^(2*n+1) % (4*(2*n+1)+1)
      = 2^(2*n+1) % (8*n+5)
      But 2^(4*n+2) % (8*n+5) = Jacobi(2|8*n+5) = -1
      And so (2^(2*n+1))^2 = -1
      :. 2^(2*n+1) % (8*n+5) =/= 1
      :. 2^p-1 % (4*p+1) =/=0
      :. These conditions for p can never be satisfied


      3) If 6*p+1 divides 2^p-1
      You have a prime number p and a prime number 6*p+1 -- again making
      the same assumption.

      Consider p=4*n+3
      2^p % (6*p+1)
      = 2^(4*n+3) % (6*(4*n+3)+1)
      = 2^(4*n+3) % (24*n+19)
      If this was +1, then
      2^(12*n+9) % (24*n+19) = 1^3 = 1
      but 2^(12*n+9) % (24*n+19) = Jacobi(2|24*n+19) = -1
      Contradiction.

      So p has to be 4*n+1
      The proof that it can be 4*n+1 is simple - you just gotta find
      one! I bet Jack's allready done that.

      I assume the rest of the cases can be approached with those same
      techniques, so it shouldn't be too hard. That's your homework
      Jack!! :)

      Ralph
    Your message has been successfully submitted and would be delivered to recipients shortly.