Wednesday, January 21, 2009

2^(n)-1, Mersenne prime and Perfect Numbers

I was reading about numbers like 2^(n)-1. There is a easy proof that if n is not prime then the number 2^(n) -1 is not prime. Since n is not prime it means n = a*b where a and b are non zero numbers for example 50 = 25*2= 10*5. Thus 2^(50) -1 is not prime. To understand it just multiply and divide by (2^(a)-1)/2^(a)-1. So we have
( 2^(a*b)-1)
*(2^(a)-1)/(2^(a)-1). Which can be written as
[( 2^(a*b)-1)*(2^(a)-1)]*(2^(a)-1) = (1+ 2^a+2^(a.2)+2^(a.3)+2^(a.4)+ .. +2^(a*(b-1)) *(2^(a)-1) and a and b can be interchanged.
When n is prime 2^(n)-1 is sometimes primes and sometimes not. When it is prime it is called Mersenne Prime. The reason they are important because they give rise to what is called perfect numbers. A perfect number is something whose sum of divisor other than itself is equal to the number itself. For example divisors of 6 are 1,2,3 and 1+2+3 = 6. Similarly 28 is another perfect number. The divisors in this case are 1,2,14,4,7 and sum is 1+2+14+4+7 = 28. Euler discovered that if you know Mersenne prime then the perfect number is 2^(n-1)*(2^n -1) i.e Mersenne Prime*2^(n-1). For example we know that 2^(7)-1 = 127 is a prime which implies 2^(6)*(2^7-1) = 4064 is a perfect number. The divisors are 1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032 and sum is 4064

0 Comments:

Post a Comment

<< Home

Site Meter