Author 
Topic: Sum the Divisors (9/13/2002) (Read 1905 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Sum the Divisors (9/13/2002)
« on: Sep 16^{th}, 2002, 1:50pm » 
Quote Modify

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.

« Last Edit: Sep 16^{th}, 2002, 1:50pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: Sum the Divisors (9/13/2002)
« Reply #1 on: Sep 17^{th}, 2002, 12:41pm » 
Quote Modify

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.

« Last Edit: Sep 17^{th}, 2002, 9:44pm by Pietro K.C. » 
IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Sum the Divisors (9/13/2002)
« Reply #2 on: Apr 24^{th}, 2003, 10:55pm » 
Quote Modify

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 (11+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 2sigma(n), we must have at least one ai odd, but no more than one, otherwise 4sigma(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).


IP Logged 



