wu :: forums
wu :: forums - Sum the Divisors (9/13/2002)

Welcome, Guest. Please Login or Register.
Aug 8th, 2022, 2:42pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Grimbal, Eigenray, Icarus, william wu, SMQ, towr)
   Sum the Divisors (9/13/2002)
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Sum the Divisors (9/13/2002)  (Read 1891 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Sum the Divisors (9/13/2002)  
« on: Sep 16th, 2002, 1:50pm »
Quote Quote Modify 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
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: Sum the Divisors (9/13/2002)  
« Reply #1 on: Sep 17th, 2002, 12:41pm »
Quote Quote Modify 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. Smiley
 
  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: male
Posts: 1948
Re: Sum the Divisors (9/13/2002)  
« Reply #2 on: Apr 24th, 2003, 10:55pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board