Prove Mersenne Number is Prime or PseudoprimeDate: 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/ |
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/