Author |
Topic: Sum the Divisors (9/13/2002) (Read 1913 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Sum the Divisors (9/13/2002)
« on: Sep 16th, 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 16th, 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 17th, 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 17th, 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 24th, 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 (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).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print