1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove or disprove whether number is prime using theorem listed in post

  1. Nov 7, 2011 #1
    So the problem has to deal with Mersenne numbers 2^p-1 where p is a odd prime, and Mp may or may not end up being prime.

    The theorem given is:
    If p is an odd prime, but Mp=2^p-1 is not a Mersenne prime, then every divisor of the Mersenne number 2^p-1 is of the form 2*c*p+1 where c is a nonnegative integer.

    Assuming this theorem is true, I need to somehow use it to determine whether M(13)=2^11-1=2047 and M(23)=2^23-1=8388607 are prime.

    I know it's supposed to start with something like "If 2047 is not prime, then we know it must have prime factor <=sqrt(2047) which is about 45.24...but I am unsure of where to go from there.

    Help would be awesome!

  2. jcsd
  3. Nov 7, 2011 #2


    User Avatar
    Science Advisor
    Homework Helper

    Take the first one, M(13)=2047. To check if that's prime you'd ordinarily have to check all of the primes less than 45.24 to see if any divide it. But the theorem tells you you don't have to check all of them. Which ones do you have to check? In the case of M(23) there's a lot more to check, but you can hope that one of the smaller ones will work.
  4. Nov 7, 2011 #3
    That helps a lot. I'm not sure why I didn't look at it that way before but now I know what was meant by the question. Thanks! I'll let you know if for some reason I get stuck again.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook