wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Sum the Divisors (9/13/2002)
        
(Message started by: william wu on Sep 16^th, 2002, 1:50pm)

Title: Sum the Divisors (9/13/2002)
Post by william wu on Sep 16^th, 2002, 1:50pm

A Perfect Number is a positive integer equal to half the sum of all its divisors. Two examples are 6 = (1+2+3+6)/2 and 28 = (1+2+4+7+14+28)/2. All Perfect Numbers found over the past two and a half millenia are even; nobody knows whether odd Perfect Numbers exist.

If either n = -1 mod 6 or n = -1 mod 4, show why n cannot be a Perfect Number.

Note: In the modular arithmetic equations of the 2nd paragraph, the "=" symbol in this context means congruent to. The congruence symbol is drawn with three horizontal bars instead of two.

Title: Re: Sum the Divisors (9/13/2002)
Post by Pietro K.C. on Sep 17^th, 2002, 12:41pm

I think the "perfect number" definition is prettier if you say that the sum of all its proper (i.e. less than itself) divisors is equal to itself. Like 1+2+3 = 6. It makes you see better why the ancients thought studying them was worthwhile.

But let's get to the problem. I just had an idea as I was writing on the "arithmetical progression" topic, which is the following: if you take a number n such that n = 3 (mod 4) and divide it by another number a = 1 (mod 4), the result (if it is an integer) is a number b = 3 (mod 4). Also, if a = 3 (mod 4), then b = 1 (mod 4). These properties are relatively easy to prove using modular congruencies. Also, note that if n = 3 (mod 4), it is odd, and hence cannot have any divisors congruent to 0 or 2 modulo 4, because these would be even numbers.

What this means is that, for n = 3 (mod 4), and x a divisor of n, x + n/x = 0 (mod 4). Therefore, the sum of all n's divisors (including itself) is divisible by 4, and half of that is even. But n is not even. Hence half the sum of its divisors cannot be equal to itself, and n cannot be perfect. Q.E.D. :)

The case where n = 5 (mod 6) can be treated similarly, but you must notice that n cannot have any divisors congruent to 0, 2, 3 or 4 modulo 6. The 1's and 5's have a similar property as that explored before.

Title: Re: Sum the Divisors (9/13/2002)
Post by Eigenray on Apr 24^th, 2003, 10:55pm

Another way to do this, which gives a stronger result, is to write any odd integer
n = prod pi^ai * prod qi^bi,
where each pi == 1 mod 4, and each qi == 3 mod 4 are distinct primes. Then
sigma(n) = prod (1+pi+pi^2+...pi^ai) * prod (1+qi+...qi^bi)
sigma(n) == prod(1+ai) * prod (1-1+1-...(-1)^bi) (mod 4)
2n == 2 (mod 4)
Therefore all bi's must be even (otherwise 4 | sigma(n)), and so any odd perfect number is the sum of two squares. In particular, n==1 mod 4.
Further, in order to have 2|sigma(n), we must have at least one ai odd, but no more than one, otherwise 4|sigma(n).
Therefore any odd perfect number can be written in the form n = pm^2, where p is a prime 1 mod 4 (and further, ord_p(m) is even).