Find a CounterexampleDate: 10/19/2002 at 04:07:47 From: Jae Subject: Counterexample for prime number Hi Dr. Math, If p is a prime number, must 2^p - 1 also be prime? Prove or disprove by counterexample. I know it is false but I can't find the a counterexample. Can you show me the procedure to find a counterexample for this kind of problem? Thank you very much. Date: 10/19/2002 at 11:11:24 From: Doctor Paul Subject: Re: Counterexample for prime number p = 11 is the first counterexample. A method known to Fermat is really helpful in factoring 2^p - 1, where p is a prime number. It's theorem three here: Mersenne Primes: History, Theorems and Lists - Chris Caldwell http://www.utm.edu/research/primes/mersenne/ It says: Let p and q be primes. If q divides M_p = 2^p-1, then q = +/-1 (mod 8) and q = 2*k*p + 1 for some integer k. Any divisor of 2^11 - 1 = 2047 must be less than or equal to floor (sqrt(2047)) = 45. So you could quickly check all primes less 45 to see if any of them divided evenly into 2047. If none of them did, then 2047 would be prime. 2047 is a relatively small number and doing this wouldn't be too hard. For larger numbers, this method isn't so easy. Fermat's result above allows us to drastically reduce the number of possible divisors of 2^p - 1. Let's see what we get for different values of k: k = 0 --> q = 1 k = 1 --> q = 23 k = 2 --> q = 45 k = 3 --> q = 67 67 is greater than 45 so we can stop here. As well, 67 is not congruent to 1 or -1 mod 8 so we can immediately throw it away. Now, q = 45 is not congruent to 1 or -1 mod 8 either and can hence be eliminated (it can also be eliminated because it isn't prime). And q = 1 is an obvious divisor that leads to a trivial factorization. So for this problem, instead of having to test all primes less than 45 (there are 14 of them), we only have to check one number, namely 23. If 23 does not divide 2047, then 2047 is prime. But inspection shows that 2047/23 = 89 and thus the desired counterexample has been shown. I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/