ImperialViolet

Mersenne Primes and Perfect Numbers (09 Sep 2002)

Mersenne (named after a french monk) primes are of the form 2n-1 where n is an integer, greater then 0. There is a distributed.net like effort to find them called GIMPS (search Google).

A perfect number is a number where the sum of its divisors (excluding itself, but including 1) equals that number. For example 6 is perfect because (1 + 2 + 3) = 6. Thus the sum of all the divisors is twice the number.

Now, I read a while back in a book that (2n-1)(2n-1) was proven to be a perfect number, but the book didn't have the proof. Thankfully, I ran across the proof today. That proof leaves out a number of steps thou, so here's a better one:

  • p = 2n - 1, and is prime
  • m = (2n-1)p
  • sigma(x) is the sum of all the positive divisors of x
  • sigma(a*b) = sigma(a)*sigma(b) where gcd (a, b) = 1 (think about it)
  • sigma(m) = sigma (2n-1p)
  • = sigma(2n-1) * sigma (p)
  • Now, p was defined to be prime, thus its only divisors are 1 and itself, thus the sum of those divisors must be p + 1
  • Also, by thinking of the prime factorisation of 2a, the divisors of 2a must include all lesser powers of 2 (where the power is greater then, or equal to, 0). By still considering the prime factorisation there can be no other divisors. Thus sigma (2n-1) must be 2n-1. It might help to think of the numbers in binary form to see this.
  • thus sigma(m) = (2n-1)(p+1)
  • expanding this gives 2n(2n-1) which is equal to 2m.
  • Thus the sum of all the divisors of m is 2m. Thus m is perfect.

One from The Book