If d(x) is the number of positive divisors of x, and n(x) is the number of distinct prime factors of x, show that d(A)=Σ(2^n(A/i²)) for all positive i such that A/i² is an integer.

It suffices to show that both sides agree when A is a prime power, and that both sides are multiplicative.

If A=p^a, then d(A)=a+1.  The divisors i on the RHS are all of the form p^b, where b <= a/2.  So the RHS is

\sum_{0<=b<a/2} 2^1 + [2^0 if a is even] = a+1.

Now suppose A,B are relatively prime.  Then d(AB)=d(A)d(B).  For the RHS, the divisors k^2 of AB are all of the form k=ij, where i^2 | A and j^2 | B, and n(AB/k^2) = n(A/i^2)+n(B/j^2).  Thus

\sum_{k^2 | AB} 2^n(AB/k^2) = \sum_{i^2 | A, j^2 | B} 2^n(A/i^2) * 2^n(B/j^2)
 = \sum_{i^2 | A} 2^n(A/i^2) * \sum_{j^2 | B} 2^n(B/j^2),

establishing the result.

Posted by Eigenray on 2007-08-06 09:09:20