## Sum of Divisors Equals a Power of 2

```Jeff Shallit challenged the readers of Mathematics Magazine to prove
that the sum of the divisors of N (denoted by s(N)) is a power of 2
if and only if N is a product of distinct Mersenne primes.  (We assume
N greater than 1 to exclude the trivial counter-example s(N) = 2^0.)

Let N > 1 be an integer with the prime factorization

N = (p1^a1)(p2^a2)...(pk^ak)

where the pj are distinct primes.  Since the sum of divisors is
multiplicative (cf. "Elementary Number Theory and its Applications"
by Kenneth Rosen), we have

s(N)  =  s(p1^a1) s(p2^a2) ... s(pk^ak)

from which it follows that s(N) is a power of 2 if and only if each
of s(pj^aj) is a power of 2.  Now, for any prime power p^a we have

s(p^a) = 1 + p + p^2 + ... + p^a                  (1)

For this sum to be even, it's clear that both p and a must be odd.
Thus there is a non-negative integer m such that a = 2m + 1, so we
can factor (1+p) out of equation (1) to give

/                                          \
s(p^a)  =  (1 + p) ( 1 + p^[2(1)] + p^[2(2)] + ... + p^[2(m)])  )
\                                          /

Clearly s(p^a) is a power of 2 iff all of its factors are powers of
2, so we have

(1 + p) = 2^u                                    (2)

/                                          \
( 1 + p^[2(1)] + p^[2(2)] + ... + p^[2(m)])  )  =  2^v      (3)
\                                          /

for integers u > 1 and v greater than or equal to 0.  Equation
(2) proves that p must be a Mersenne prime, because it has the form
p = 2^u - 1, where u is obviously a prime because 2^(ab) - 1 has
the non-unit factor 2^a - 1 for any integers a,b > 1.  Thus a
necessary condition for s(N) to be a power of 2 is that N be the
product of Mersenne primes.

To prove that N is necessarily the product of DISTINCT Mersenne
primes, suppose that equation (3) were satisfied for some positive
integer m (corresponding to an exponent aj > 1 in the prime
factorization of N).  Then v > 0, and m must be odd, so we have
m = 2r+1 for some non-negative integer r.  We could then factor
(1 + p^2) from the left side of (3) to give

/                                        \
(1 + p^2)( 1 + p^[4(1)] + p^[4(2)] + ... + p^[4(r)] ) = 2^v
\                                        /

which implies that (1 + p^2) is a power of 2.  However, we also
have
(1 + p^2)  =   1  +  (2^u - 1)^2

=   2 [ 2^u (2^(u-1) - 1) + 1]

proving that 1+p^2 has an odd factor greater than 1, contradicting
the previous equation.  It follows that the only solution of equation
(3) (if p is a Mersenne prime) is the trivial solution with m=v=0.
Therefore, each non-zero exponent in the prime factorization of N
must equal 1, so N is the product of distinct Mersenne primes.

Finally, we observe that the stated condition is also sufficient,
since s(p) = 1+p is (by definition) a power of 2 if p is a Mersenne
prime.
```