Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site faron.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!unc!mcnc!decvax!linus!faron!bs
From: bs@faron.UUCP (Robert D. Silverman)
Newsgroups: net.math
Subject: Re: Can you prove/disprove this?
Message-ID: <404@faron.UUCP>
Date: Fri, 29-Nov-85 22:32:40 EST
Article-I.D.: faron.404
Posted: Fri Nov 29 22:32:40 1985
Date-Received: Sat, 30-Nov-85 14:23:12 EST
References: <34080@lanl.ARPA>
Distribution: net
Organization: The MITRE Coporation, Bedford, MA
Lines: 52

> 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 theorem as you have stated is incorrect. It is necessary that n be prime
but that is NOT sufficient. In addition 2^n -1 must also be prime. In
fact the interest in Mersenne primes (primes of this form) derives historically
from interest in perfect numbers. To see that 2^(n-1) * (2^n -1) is perfect
when 2^n-1 is prime simply substitute this expression into the expression
for the sum of the divisors which is:

S = (p^a+1 -1)/(p-1) * (q^b+1 - 1)/(q-1) * ...
 
				     a  b
   where the number is question N = p *q *.....

To see this we see that the sum of all divisors is:

(1 + p + p^2 + p^3 + ...)(1 + q + q^2 + q^3 +...)(...)
 
If we substitute N = 2^(n-1) * (2^n -1) where 2^n -1 is PRIME we obtain:

(2^n-1)/(2-1) * ((2^n-1)^2 -1)/(2^n - 2) = (2^n - 1)*2^n = 2N
 
That is to say N is perfect.

It is trivial to see that n must be prime else 2^n-1 will factor into say pq
and the above substitution won't necessarily work. It is also easy to prove
the converse: if N is an even number and it is perfect then it is of the
form 2^(n-1)*(2^n -1 ). I'll leave this latter proof as a simple exercize
and post the proof in a couple of days.

A simple numerical counter example is to note that if n = 11  then
2^11 - 1 = 23.89 and 2^10*23*89 is not perfect. By the way note that
both factors of 2^11 - 1 are of the form 2*11n + 1. This is not coincidence.
ALL primitive factors of numbers of the form A^n + B^n must be of the
form 2kn + 1. This follows trivially from Fermat's little theorem.
 
Bob Silverman  (they call me Mr. 9)