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/