Two Column Problem Solving

Problem (Liouville): Let n > 0 be a positive integer. For each positive divisor r of n count the number of divisors of r. Suppose that the number of divisors of r is s_r. Let S be the square of the sum of the s_r's. Let T be the sum of the cubes of the s_r's. What is the relationship between S and T?

First Column:

Case 1: n = p, p a prime.

In this case the only divisors of n are 1 and p. 1 has 1 positive divisor and p has 2. Hence s_1 = 1 and s_p = 2. S = (1 + 2)^2 = 9. The sum of their cubes is 1^3 + 2^3 = 9.

Case 2: n = pq, p and q distinct primes.

In this case the divisors of n are 1, p, q, and pq. s_1 = 1, s_p = s_q = 2, and s_{pq} = 4. Thus S = (1 + 2 + 2 + 4)^2 = (1+2 +2 (1+2))^2 = (1+2)^2 * (1+2)^2= 81. T = 1^3 + 2^3 + 2^3 + 4^3 = (1^2 + 2^3 + 2^3(1 + 2^3))= (1^3 + 2^3)(1^3 + 2^3) = 9*9 = 81.

Case 3: n = p^m, p a prime and m > 1 is a positive integer.

In this case the divisors of n are 1, p, p^2, ... p^m. s_1 = 1, s_p = 2, s_{p^2} = 3, and in general s_{p^j} = j+1. Thus S = (1 + 2 + 3 + ... + (m+1))^2 = [(m+1)(m+2)/2]^2. T = (1^3 + 2^3 + ... + (m+1)^3) = [(m+1)(m+2)/2]^2 by the summation of cubes formula.

Case 4: n = (p^a)(q^b) where p,q are distinct primes and a, b > 1 are positive integers.

In this case the divisors of n are of the form (p^i)(q^j), where 0 =< i =< a, 0 =< j =< b. After reorganizing we can write S = [(1 + 2 + ... + (a+1)) + 2(1 + 2 + ... +(a+1)) + ... + (b+1)(1 + 2 + ... + (a+1))]^2 = [(1 + 2 + ... + (a+1))^2][1 + 2 + ... + (b+1)]^2 = [(a+1)(a+2)/2]^2 * [(b+1)(b+2)/2]^2 . Similarly, after reorganizing we find T = (1^3 + 2^3 + ... + (a+1)^3)(1 + 2 + ... + (b+1)^3) which by the previous case is equal to S.

The general case follows by induction on k, where n = (p_1)^(a_1) * (p_2)^(a_2) * ... * (p_k)^(a_k) where the p_i's are distinct primes and a_i's are positive integers.

Second Column:

The problem looks very interesting because the wording problem strongly suggests finding an unexpected equality. As the problem is all about the NUMBER of divisors and nothing about the size of the divisors it strongly suggests that the SIZE of the prime factors in the factorization of n doesn't matter, it is all about the NUMBER of divisors. It then make sense to first explore the case when n is a prime.

After examining case 1 our suspicions are confirmed when we find that regardless of which prime p is, the value of S (as defined on the first column) remains the same. We then boldly explore perhaps more difficult cases, which leads us to case 2. In this simple case we found a method to 'reorganize' the terms involved in the sum to obtain S and T respectively that we hope may generalize.

We find that case 2 is not a sufficient 'work horse' to solve the general result. We need something to deal with the case when n has arbitrarily large prime powers as factors. The simplest such case of course is when n = p^m, a power of a prime. This is what we choose as our third case.

Eureka! Third case gave us something incredibly illuminating. It seems that Liouville is attempting to find a more general case of of the sum of cubes formula, which is exactly what turns out to be the case when n is the power of a prime. This is the 'work horse' that we are looking for. But just to be safe, we should see if we can combine the insights obtained in case 2 and 3 together by consider when n is the product of two distinct prime powers.

And we see that the factoring and re-organizing tactic employed in the second case can be applied fruitfully in conjunction with the third case to provide a satisfying and complete solution to case 4. Thus, the rest of the problem follows easily by induction.

This problem is reminiscent of the typical train of thought of research mathematicians of that era, an emphasis on searching for new and surprising equalities. This result is a relatively deep and interesting extension on the fact that the number of factors of a number only depends on how many prime factors it has and to what powers these primes are raised, and not on the value of the primes themselves.