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.

Return to MathPages Main Menu