Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83 (MC840302); site klipper.UUCP
Path: utzoo!watmath!clyde!cbosgd!ihnp4!qantel!lll-crg!seismo!mcvax!vu44!botter!klipper!victor
From: victor@klipper.UUCP (L. Victor Allis)
Newsgroups: net.math
Subject: Re: Can you prove/disprove this?
Message-ID: <526@klipper.UUCP>
Date: Sat, 30-Nov-85 10:19:44 EST
Article-I.D.: klipper.526
Posted: Sat Nov 30 10:19:44 1985
Date-Received: Mon, 2-Dec-85 03:14:02 EST
References: <34080@lanl.ARPA>
Reply-To: victor@klipper.UUCP (L. Victor Allis)
Distribution: net
Organization: VU Informatica, Amsterdam
Lines: 50

In article <34080@lanl.ARPA> dxm@lanl.ARPA writes:
>In an assembler programming class once we were asked to write a program 
>that determined if a given integer was perfect or not.  I took a short cut
>past the obvious method of finding and adding all the divisors by noticing
>that numbers of the form 
>
>		x = 2^(n-1) * (2^n - 1)
>
>are perfect if n is a prime number.  This was true up to the largest
>integer the machine could represent.  This does not constitute a proof
>though, and so I lay the problem before all you net.math.wizards to see if
>anyone knows of or can think of a way to prove or disprove the statement
>that all numbers of the above form are perfect if n is prime.
>
>
> Doug Miller                     dxm@lanl.arpa
>                                 ....!ihnp4!lanl!dxm

The restriction is a little stronger :

  x = 2^(n-1) * (2^n - 1) is perfect if and only if 2^n - 1 is prime.

(this implies that n is prime, but not vice versa (take n=11, 2047=23*89)
These primes are called Mersenne primes and it is easy to find something
about those primes in literature. It is also proved that all even perfect
numbers are of this form. It is not known if there are any odd perfect numbers.
It is rather easy to proof that x (in the formula above) is prime if
and only if 2^n - 1 is prime.

Proof:
  
  Since 2^n - 1 is prime, the only divisors of x are 1, 2, 4, ..., 2^(n-1),
  and 1*(2^n - 1), 2*(2^n - 1), 4*(2^n - 1), ... ,2^(n-1)*(2^n - 1).
  (all divisors of 2^(n-1) multiplied, or not, by 2^n - 1)
  Since: (1 + 2 + 4 + ... + 2^(n-1)) = 2^n - 1,
  the sum of all the divisors is:
  2^n - 1 + (2^n - 1)*(2^n - 1) = 2^n * (2^n - 1) = 2*x
  Thus x is perfect (x is counted as a divisor here, thus the sum of
  the real divisors is 2x - x = x).

  If 2^n - 1 is not prime, the sum of the divisors is greater than the
  just obtained result, therefore x is perfect if and only if 2^n - 1
  is prime.

I believe, it is much harder to proof that all even perfect numbers
are of this form, which result is due to Euler if I'm not mistaking.

Victor Allis.
Free University of Amsterdam
The Netherlands.