Find a Counterexample

Date: 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/