Let $n$ be an integer greater than zero. Prove


where $v(d)$ is the number of positive divisors of $n$.

I'll outline what my problem is. I write $n= p_{1}^{a_{1}}, p_{2}^{a_{2}}, \cdots , p_{m}^{a_{m}}$. Then I write out each divisor $d_{1}, d_{2}, ..., d_{(a_{1} + 1)(a_{2}+1)...(a_{m} + 1)}$ for $n$. Then

$$(\sum_{d|n}v(d)){}^{2}=(v(d_{1})+v(d_{2})+\ldots+v(d_{(a_{1}+1)(a_{2}+1)\cdots(a_{m}+1)}))^{2}, $$

but now how do I simplify anything? I don't know how many divisors of EACH $d_{i}$ there are. $d_{i}$ might be prime, it might have 3 divisors--I don't know. That depends on the prime factorization of $d_{i}$. So now I have to write each $d_{i}$ in its very own prime factorization, so I'll have $(a_{1}+1)(a_{2}+1)\cdots(a_{m}+1)$ prime factorizations written out. That's just silly. I realize $v(d)$ is multiplicative but so what? I still have to actually know how many divisors each divisor will have, which means I have to write out each divisor in its own prime factorization.

  • $\begingroup$ Isn't it the case that both sides are multiplicative functions? so all you have to do is prove it in the case where $n$ is a prime power? $\endgroup$ – Gerry Myerson Oct 23 '14 at 11:58
  • $\begingroup$ THe book says that as a hint but it also said "why?". Honestly I missed a couple of classes and I don't see how multiplicativity implies that we don't have to show it for any integer; but rather, any prime power. I guess I'll just do it but I don't know why I'm doing it! $\endgroup$ – Sultan of Swing Oct 23 '14 at 12:02
  • $\begingroup$ When a function is multiplicative, it is completely determined by its values on prime powers. $\endgroup$ – Gerry Myerson Oct 23 '14 at 12:03
  • $\begingroup$ The book keeps saying that and I'm trying to apply it and figure out what it means. I guess it's because if $ab$ is not a prime power, then we could write $f(ab) = f(a)f(b)$ and consider each $f(a)$ individually, right? $\endgroup$ – Sultan of Swing Oct 23 '14 at 12:05
  • $\begingroup$ You can factor any integer into powers of different primes, and then evaluate $f$ as the product of its values on the prime powers. $\endgroup$ – Gerry Myerson Oct 23 '14 at 12:07

Quickly show $v$ is multiplicative:

Let $a, b$ be relatively prime integers, so $a=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{m}^{a_{m}}$ and $b=p_{1'}^{b_{1}}p_{2'}^{a_{2}}\cdots p_{n}^{a_{n}} $. They have no primes in common as we assume they are relatively prime.

Then $$v(ab) = v((p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{m}^{a_{m}})(p_{1'}^{b_{1}}p_{2'}^{a_{2}}\cdots p_{n}^{a_{n}}))$$ $$= v(p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{m}^{a_{m}}p_{1'}^{b_{1}}p_{2'}^{a_{2}}\cdots p_{n}^{a_{n}})$$

and by a properties previously established in my textbook

$$=(a_{1}+1)(a_{2}+1)\cdots(a_{m}+1)(b_{1}+1)(b_{2}+2)\cdots(b_{n}+1)$$ $$=\left((a_{1}+1)(a_{2}+1)\cdots(a_{m}+1)\right)\left((b_{1}+1)(b_{2}+2)\cdots(b_{n}+1)\right)$$ $$v(a)v(b).$$

I realize this leaves out a lot but for purposes of my question and given the information in the book that has already been established, it would suffice for my assignment (I believe).

So now this means $v(d)$ is completely determined by its values on prime powers, and so we can assume $n$ is a prime power. Let $n = p^{a}$ for some positive integer $a$. Then all the divisors of $n$ are $\left\{ 1,p,p^{2},p^{3},\ldots,p^{a}\right\}.$

$$(\sum_{d|n}v(d)){}^{2}=(\sum_{d|p^{a}}v(d)){}^{2}$$ $$= v(1) + v(p) + v(p^{2}) + ... + v(p^{a})$$ $$=(1+(1+1)+(2+1)+...+(a+1))^{2}$$ $$=(1+2+3+...+a+1)^{2}$$ $$=\left(\sum_{k=0}^{a}k+1\right)^{2}$$ and by Faulhaber's formula, we have $$=\sum_{k=0}^{a}\left(k+1\right)^{3}$$ $$=1^{3}+ 2^{3} + 3^{3} + ... + (a+1)^{3}$$ $$=1 + (1+1)^{3} + (2+1)^{3} + ... (a+1)^{3}$$ So by definition of $v$, $$=v(1) + v(p^{1})^{3} + v(p^{2})^{3} + ... + v(p^{a})^{3}$$ $$=\sum_{d|p^{a}}\left(v(d)\right)^{3}$$ and since $n=p^{a}$, $$\sum_{d|n}\left(v(d)\right)^{3}\blacksquare $$

  • $\begingroup$ That's the idea, but it's not enough to show that $v(d)$ is multiplicative, you need to show that $(\sum_{d\mid n}v(d))^2$ is multiplicative and that $\sum_{d\mid n}(v(d))^3$ is multiplicative. To do that, you have to show that if $f$ is multiplicative then so is $f^m$ for all $m$, and you probably have a theorem that says that if $f$ is multiplicative then so is $\sum_{d\mid n}f(d)$. $\endgroup$ – Gerry Myerson Oct 23 '14 at 22:03
  • $\begingroup$ Are you still here? $\endgroup$ – Gerry Myerson Oct 25 '14 at 3:52
  • $\begingroup$ I'm around, just really busy with some graph theory at the moment. $\endgroup$ – Sultan of Swing Oct 25 '14 at 9:49

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.