Kvant Math Problem 549

Let $N$ be a natural number and let its divisors be $d \mid N$.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 8m56s
Source on kvant.digital

Problem

Given a natural number $N$. Let us list all of its divisors $d_1$, $d_2$, $\ldots$, $d_n$ and for each of them determine how many divisors it has. Prove that for the resulting numbers $a_1$, $a_2$, $a_3$, $\ldots$, $a_n$ the equality $$(a_1+a_2+\ldots+a_n)^2=a_1^3+a_2^3+\ldots+a_n^3.$$ holds.

For example, the number $N=6$ has four divisors: $1$, $2$, $3$, $6$; here $a_1=1$, $a_2=2$, $a_3=2$, $a_4=4$ and $$(1+2+2+4)^2=1^3+2^3+2^3+4^3.$$

V. E. Matizen

Exploration

Let $N$ be a natural number and let its divisors be $d \mid N$. For each divisor $d$, define $a(d)=\tau(d)$, the number of positive divisors of $d$. The identity to be proved is

$$\left(\sum_{d\mid N}\tau(d)\right)^2=\sum_{d\mid N}\tau(d)^3.$$

Write

$$S(N)=\sum_{d\mid N}\tau(d), \qquad T(N)=\sum_{d\mid N}\tau(d)^3.$$

The statement becomes $S(N)^2=T(N)$.

A first structural observation is that both $\tau(d)$ and the divisor relation $d\mid N$ behave well under prime factorization. This suggests attempting multiplicativity with respect to $N$. If both $S$ and $T$ are multiplicative arithmetic functions, then the identity reduces to checking it for prime powers.

For $N=p^n$, divisors are $p^k$ for $0\le k\le n$, and $\tau(p^k)=k+1$. The problem then reduces to proving a classical identity involving sums of squares and cubes of integers:

$$\left(\sum_{k=1}^{n+1} k\right)^2=\sum_{k=1}^{n+1} k^3.$$

The main point requiring justification is the multiplicativity of $S$ and $T$, and the fact that no interaction between different primes affects the identity.

Problem Understanding

This is a Type B problem. One must prove the identity

$$\left(\sum_{d\mid N}\tau(d)\right)^2=\sum_{d\mid N}\tau(d)^3$$

for every natural number $N$.

The core difficulty is not computation but structural reduction: the expression involves a sum over divisors, and the correct approach is to exploit the factorization of $N$ into prime powers and reduce the statement to a one-variable identity.

The claim will be shown true for all $N$ by proving that both sides are multiplicative functions and then verifying the identity on prime powers.

Proof Architecture

The function $\tau(n)$ is multiplicative, so $\tau(n)^3$ is also multiplicative.

The function $S(n)=\sum_{d\mid n}\tau(d)$ equals the Dirichlet convolution $(\tau*1)(n)$, hence it is multiplicative because convolution of multiplicative functions is multiplicative when one factor is $1$.

The function $T(n)=\sum_{d\mid n}\tau(d)^3$ equals $(\tau^3*1)(n)$ and is therefore multiplicative by the same reasoning.

If $S$ and $T$ are multiplicative, then $S^2$ is also multiplicative, so it suffices to prove $S(p^n)^2=T(p^n)$ for all primes $p$ and all $n\ge 0$.

The hardest step is the reduction to the identity

$$\left(\sum_{k=0}^n (k+1)\right)^2=\sum_{k=0}^n (k+1)^3,$$

which must be verified by direct evaluation.

Solution

Let

$$S(N)=\sum_{d\mid N}\tau(d), \qquad T(N)=\sum_{d\mid N}\tau(d)^3.$$

The function $\tau(n)$ is multiplicative, meaning that if $\gcd(a,b)=1$, then $\tau(ab)=\tau(a)\tau(b)$. Consequently $\tau(n)^3$ is also multiplicative.

Define the divisor-sum operator $F \mapsto F*1$, where

$$(F*1)(n)=\sum_{d\mid n}F(d).$$

Since $\tau$ is multiplicative, both $\tau_1$ and $\tau^3_1$ are multiplicative functions. Hence $S$ and $T$ are multiplicative.

Therefore $S^2$ is multiplicative as well, so the identity $S(n)^2=T(n)$ holds for all $n$ if and only if it holds for all prime powers.

Let $n=p^m$. The divisors of $p^m$ are $p^k$ for $0\le k\le m$, and

$$\tau(p^k)=k+1.$$

Hence

$$S(p^m)=\sum_{k=0}^m (k+1)=\sum_{j=1}^{m+1} j.$$

Thus

$$S(p^m)=\frac{(m+1)(m+2)}{2}.$$

Similarly,

$$T(p^m)=\sum_{k=0}^m (k+1)^3=\sum_{j=1}^{m+1} j^3.$$

Using the classical identity for cubic sums,

$$\sum_{j=1}^{n} j^3=\left(\frac{n(n+1)}{2}\right)^2,$$

with $n=m+1$, we obtain

$$T(p^m)=\left(\frac{(m+1)(m+2)}{2}\right)^2.$$

Therefore,

$$S(p^m)^2=T(p^m).$$

By multiplicativity of both sides, the identity holds for all natural numbers $N$.

This completes the proof. ∎

Verification of Key Steps

The multiplicativity of $S(n)=\sum_{d\mid n}\tau(d)$ depends on rewriting it as a Dirichlet convolution $(\tau*1)(n)$. Since both $\tau$ and the constant function $1$ are multiplicative, their convolution is multiplicative, which ensures $S(ab)=S(a)S(b)$ for coprime $a$ and $b$.

The same reasoning applies to $T(n)=\sum_{d\mid n}\tau(d)^3$, since $\tau^3$ remains multiplicative. This guarantees that reduction to prime powers loses no information.

The identity for prime powers reduces exactly to the known formula for $\sum_{k=1}^n k^3$, and substituting $n=m+1$ aligns the indexing correctly, ensuring both sides match term by term.

Alternative Approaches

A direct combinatorial interpretation is possible by writing $\tau(d)$ as the number of factorizations $d=xy$ and interpreting both sides as counting structured collections of divisors of $N$. One can then construct a bijection between ordered triples of factorizations of a divisor and ordered pairs of factorizations of divisors of $N$, leading to the same identity.

Another approach uses exponent vectors of prime factorizations of $N$, rewriting all sums as products over primes and reducing the problem immediately to the one-dimensional case.