4
$\begingroup$

I am trying to prove or disprove the following statement:

$$\sum_{r|n} d(r^2) = d^2(n),$$

where $d$ is the number of divisors function.

Computing it for small numbers yields equality, so I at least think it's true. But I can't see how to prove it formally. I have tried working with prime factorisations, but finding equality between terms seems near-impossible at best. My best guess is there is a way to manipulate

$$\sum_{r\mid n} \sum_{k\mid r^2} 1$$

into a form which becomes the RHS, although my attempts at writing $n=ar$ and $r^2=bk$ for $a,b\in\mathbb{Z}$ become very messy when I attempt substitution.

Any assistance or hints would be greatly appreciated! Thank you!

$\endgroup$
  • $\begingroup$ What divisor function do you mean? just divisors? unique divisors? prime divisors? unique prime divisors? $\endgroup$ – Mastrem Oct 29 '16 at 10:31
  • $\begingroup$ Just divisors - for example $d(6) = 4$ since it has four distinct divisors. $\endgroup$ – Camille Oct 29 '16 at 10:35
3
$\begingroup$

Write $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$. Then \begin{align}\sum_{r|n} d(r^2)&=\sum_{0\leq i_1 \leq \alpha_1,\ldots,0\leq i_k \leq \alpha_k} d((p_1^{i_1}\cdots p_k^{i_k})^2)\\&=\sum_{0\leq i_1 \leq \alpha_1,\ldots,0\leq i_k \leq \alpha_k} d(p_1^{2i_1}\cdots p_k^{2i_k})\\&=\sum_{0\leq i_1 \leq \alpha_1,\ldots,0\leq i_k \leq \alpha_k}(2i_1+1)\cdots(2i_k+1)\\&=\left(\sum_{0\leq i_1 \leq \alpha_1}(2i_1+1)\right)\cdots \left( \sum_{0\leq i_k \leq \alpha_k}(2i_k+1)\right)\\&=\left(2\frac{\alpha_1(\alpha_1+1)}{2}+(\alpha_1+1)\right)\cdots \left( 2\frac{\alpha_k(\alpha_k+1)}{2}+(\alpha_k+1)\right)\\&=(\alpha_1+1)^2\cdots(\alpha_k+1)^2\\&=d(n)^2.\end{align}

$\endgroup$
  • $\begingroup$ Thank you! Just to clarify, the limits of summation in the fifth line should read $0\leq i_k \leq a_k$, yes? $\endgroup$ – Camille Oct 29 '16 at 11:39
  • $\begingroup$ Yes, that's right. $\endgroup$ – SMJK Oct 29 '16 at 11:42
1
$\begingroup$

The divisor counting function $d$ is multiplicative, so it is straightforward to verify that both $d(n^2)$ and $d^2(n)$ are multiplicative. Furthermore, by a fundamental theorem of multiplicative functions, $\sum_{r|n} d(r^2)$ is also multiplicative. Hence, because both sides of the statement are multiplicative, to establish that the statement is true for all positive integers $n$, it suffices to prove that it is true for all prime powers $p^\alpha$:

\begin{align} \sum_{r|p^\alpha} d(r^2) & = d(1^2) + d(p^2) + d(p^4) + \cdots + d(p^{2\alpha}) &&\text{positive divisors of } p^\alpha \text{are } 1, p, p^2, \dots, p^\alpha\\ & = 1 + 3 + 5 + \cdots + 2\alpha + 1 && d(p^i) = i + 1\\ & = (\alpha + 1)^2 &&\text{sum of the arithmetic series}\\ & = d^2(p^\alpha) && i + 1 = d(p^i) \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.