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

### Prove Mersenne Number is Prime or Pseudoprime

```Date: 10/11/2008 at 19:01:14
From: Jamie
Subject: Mersenne Number either prime or pseudoprime

Let p be a prime number.  Prove that 2^p - 1 is either a prime number
or a pseudoprime number (2^n is congruent to 2 modulo n, where n is
composite).

I really don't know where to start.  I've been messing around with the
definition of a pseudoprime and Fermat's Little Theorem, but I don't
seem to be getting anywhere.  Fermat's Little Theorem is the only
thing I have that seems even remotely related.  I feel like you would
have to  prove this in two cases, somehow show that in one case you
get a pseudoprime and in another you get a prime and these exhaust all
numbers possible from 2^p-1.

```

```
Date: 10/12/2008 at 04:21:33
From: Doctor Jacques
Subject: Re: Mersenne Number either prime or pseudoprime

Hi Jamie,

Let N = 2^p - 1 = q_1 * ... * q_r, where the q_i are the prime
factors of N (the q_i are not necessarily distinct, and, if N is
prime, there will be only one factor).

Note that:

2^p = 1    (mod N)      [1]

and therefore

2^p = 1    (mod q)      [2]

where q is any prime factor of N (actually, [2] is true for any
factor of N).

We must prove that 2^N = 2 (mod N).  The idea is to compute
2^N (mod N) by "nested exponentiation".  We write:

2^N = 2^(q_1*...*q_r)
= (((2^q_1)^q_2)...^q_r)   [3]

If we could prove that 2^q_i = 2 (mod N) for each of the q_i, we
could successively replace each bracket in [3] by 2, and this would
give the desired result.  Specifically, we would replace 2^q_1 by 2,
then 2^q_2 = (2^q_1)^q_2 by 2, and so on.

Try to prove that q_i = 1 (mod p) for all q_i.  This is where you
would use Fermat's theorem, together with the fact that p and q_i
are prime.

Once you've done that, you can write:

q_i    = m_i*p + 1
2^q_i  = 2 * 2^(p*m_i)
= 2 * (2^p)^m_i
= 2        (mod N) (by [1])

and you can finish the proof as explained before.

For example, with p = 11, we have N = 2^11 - 1 = 2047 = 23*89.
Notice that both factors are congruent to 1 (mod 11)--this is what
you will need to prove.  We may write (all congruences are mod 2047):

2^2047 = (2^23)^89
= (2*(2^(11*2))^89
= (2*(2048^2))^89
= 2^89
= 2*2^(11*8)
= 2*(2048^8)
= 2

Please feel free to write back if you require further assistance.

- Doctor Jacques, 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