wu :: forums « wu :: forums - Sum the Divisors (9/13/2002) » Welcome, Guest. Please Login or Register. Sep 26th, 2023, 11:02am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register wu :: forums  riddles  putnam exam (pure math) (Moderators: Icarus, Grimbal, SMQ, towr, Eigenray, william wu)  Sum the Divisors (9/13/2002) « Previous topic | Next topic » Author Topic: Sum the Divisors (9/13/2002)  (Read 1905 times)
william wu       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

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »