• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter lostNfound
  • Start date
  • #1
12
0
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!

Thanks!
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #3
12
0
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.
 

Related Threads on Prove or disprove whether number is prime using theorem listed in post

Replies
9
Views
2K
  • Last Post
Replies
2
Views
3K
Replies
1
Views
574
Replies
4
Views
15K
  • Last Post
Replies
1
Views
5K
Replies
1
Views
1K
Replies
12
Views
9K
Top