Mersenne Primes and Perfect Numbers (09 Sep 2002)
- A good argument against Dave Winer's position on software copyright
- KCachegrind, a KDE frontend for the superb Valgrind
- Suggested answering machine greetings
- HP fires Bruce Perens for being nasty to Microsoft
- Indroduction to Geometric Algebra
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