Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

some more.

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search