Sum of divisors - Relations

Let N = ∏pm the prime factorization of N. We get divisors of N by choosing exponents between 0 and m for each prime factor p, in all possible ways. The number of divisors, 1 and N included, is then :

∏(m+1)

For instance 600 = 23×3×52 has (3+1)(1+1)(2+1) = 24 divisors.
By expanding the product ∏p (∑i pi), for which in every sum ∑ : 0 ≤ i ≤ m for that prime p, we get every term of expansion by choosing an exponent for each prime factor p.
Hence it is a divisor of N and the sum is the sum of divisors of N, as we get all of them.
∑pi can be written (pm+1-1)/(p-1) as sum of a geometric series, and finally :

S = ∏p (∑i pi) = ∏(pm+1-1)/(p-1)

For instance N = 600 : S = (1+2+4+8)(1+3)(1+5+25) = (16-1) × (9-1)/2 × (125-1)/4 = 1860

Script for calculation of sum of divisors

Let's speak now about perfect numbers. The odd perfect numbers are unknown, and we think there are none. However if there is one, it is more than 300 digits ! On the contrary, even perfect numbers are known since Euclid, and Euler proved they are all :

2(p-1)(2p-1) with 2p-1 being prime

The number 2p-1 is not prime for every exponent p.
p must be prime, but it is not sufficient, for instance 211-1 = 2047 = 23x89.
Numbers Mp = 2p-1 are primes (Mersenne primes) for p = 2, 3, 5, 7, 13, 17, 19, 31...
That is Mersenne primes 3, 7, 31, 127, 8191, 131071, 524287, 2147483647...
and perfect numbers :

6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128...

Miscellaneous

There are other curiosities related with the sum of divisors :

Inverse problem

That is to find a number N given the sum S of its divisors.
This is solved by searching divisors of S in the form ∑pi, with p prime.

For instance to search numbers whose sum of all divisors is 56 :
First of all get all divisors of 56 = 2³×7 : 1, 2, 4, 7, 8, 14, 28 and 56.
Next look for those of the form Q = 1+p+...pn.
To check if a number q is of the form Q, we look for prime factors p of q-1.
For each one, check if q(p-1)+1 is a power of p.

For instance to check if q=31 is a Q number : 31-1 = 30 = 2x3x5
    p = 2 : 31×1+1 = 32 = 25 and 31 = 1+2+4+8+16
    p = 3 : 31×2+1 = 63 not a power of 3
    p = 5 : 31×4+1 = 125 = 53 and 31 = 1+5+25
Hence 31 is of the form Q in two ways.

The only divisors of 56 of the form Q = 1+p+...pn are :
    4 = 1+3
    7 = 1+2+4
    8 = 1+7
    14 = 1+13

Look for factorization of 56 with these divisors : 56 = 1×56 = 2×28 = 4×14 = 8×7 = 2×2×14 = 2×4×7 = 2×2×2×7.
Only factorizations 4×14 and 8×7 are made of Q numbers only.
4×14 = (1+3)(1+13) results into N = 3×13 = 39
8×7 = (1+7)(1+2+4) results into N = 7×4 = 28

All this doesn't work anymore if the sum of proper divisors is given instead of all divisors.

Annexe 1 : Checking the Frenicle number

n = 236 × 38 × 55 × 77 × 11 × 132 × 19 × 312 × 43 × 61 × 83 × 223 × 331 × 379 × 601 × 757 × 1201 × 7019 × 112303 × 898423 × 616318177

Check first that all these numbers are primes (hard job with just paper and pencil ! The script giving the sum of divisors gives also the prime factorization)
The sum of all divisors of n is then :
S = (237-1) × (39-1)/2 × (56-1)/4 × (78-1)/6 × 12 × (133-1)/12 × 20 × (313-1)/30 × 44 × 62 × 84 × 224 × 332 × 380 × 602 × 758 × 1202 × 7020 × 112304 × 898424 × 616318178.
and we have to factorize all these numbers :

237-1 = 223×616318177  (39-1)/2 = 9841 = 13×757
(56-1)/4 = 3906 = 2×32×7×31  (78-1)/6 = 960800 = 25×52×1201
12 = 22×3  (133-1)/12 = 183 = 3×61
20 = 22×5  (313-1)/30 = 993 = 3×331
44 = 22×11  62 = 2×31
84 = 22×3×7  224 = 25×7
332 = 22×83  380 = 22×5×19
602 = 2×7×43  758 = 2×379
1202 = 2×601  7020 = 22×33×5×13
112304 = 24×7019  898424 = 23×112303
616318178 = 2×73×898423
Grouping all prime factors :
S = 237 × 39 × 55 × 77 × 11 × 132 × 19 × 312 × 43 × 61 × 83 × 223 × 331 × 379 × 601 × 757 × 1201 × 7019 × 112303 × 898423 × 616318177 = 6n.
Sum of proper divisors is S - n = 5n QED.

 

Home Arithmetic Geometric Misc Topics Scripts Games Exercices Mail Version Française Previous topic Next topic