### 37th Putnam 1976

Problem B6

Let σ(n) be the sum of all positive divisors of n, including 1 and n. Show that if σ(n) = 2n + 1, then n is the square of an odd integer.

Solution

If n is odd and non-square, then the divisors can be arranged in pairs d, n/d. The components of each pair are odd, so their sum is even and hence σ(n) is even and cannot equal 2n+1. It is more difficult to show that n cannot be even.

We have σ(n) = ∏(1 + p + p2 + ... + pk), where the product is taken over all primes p dividing n and k is the highest power of p dividing n. If p and k are odd, then the factor (1 + p + ... + pk) is even, and hence σ(n) is even. So if σ(n) = 2n+1, all k corresponding to odd primes must be even. In other words, we have n = 2aN2, for some odd integer N. Hence σ(n) = (2a+1-1)σ(N2) = 2a+1N2 + 1. So N2 = (2a+1-1)(σ(N2) - N2) - 1. Hence if q is any odd prime dividing 2a+1-1, then N2 = - 1 (mod q). But -1 is a quadratic non-residue of primes of the form 4r+3. So every prime factor of 2a+1 - 1 must be of the form 4r+1. But that is not possible if a ≥ 1 (a product of numbers congruent to 1 mod 4 is congruent to 1, not -1). Hence a = 0 and n is an odd square.