Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How would you solve this problem:

Two arithmetic functions $f$ and $g$ may be multiplied using the Dirichlet product, which is defined by $(f * g)(n) = \displaystyle\sum\limits_{d \mid n} f(d)g(\frac{n}{d})$. Show that $(f * g) * h = f * (g * h)$ for the case when $f$ is the Euler-phi function, $g(n) = 1$ and $h(n) = \sigma(n)$

Thanks in advance!

share|cite|improve this question
It would be quite useful if you explain the context of the problem, what you tried to far, and where you got stuck. – Ittay Weiss Nov 7 '12 at 4:25
When you put dirichlet product associative, you will find quite a lot of useful resources. (Soon that Google search will probably return this question, too.) – Martin Sleziak Nov 7 '12 at 7:17
up vote 3 down vote accepted

This is true in general, not just for those functions. We have

$$ ((f*g)*h)(n)=\sum_{d|n}(f*g)(d)h\left(\frac nd\right)=\sum_{d|n}\left(\sum_{r|d}f(r)g\left(\frac dr\right)\right)h\left(\frac nd\right) $$


$$ (f*(g*h))(n)=\sum_{d|n}f(d)(g*h)\left(\frac nd\right)=\sum_{d|n}f(d)\sum_{r|\frac nd}g(r)h\left(\frac n{rd}\right)\;, $$

and both of these are sums over all factorizations of $n$ into three factors and are thus equal to

$$ \sum_{drs=n}f(d)g(r)h(s)\;. $$

share|cite|improve this answer
True, but maybe there was some reason the person who wrote the problem wanted to draw attention to the special case. – Gerry Myerson Nov 7 '12 at 5:39

An answer has already been posted that shows that this holds in general. In this particular case, for $f = \varphi$, $g=1$, and $h=\sigma$, we may simplify matters by using the fact that each of $f,g,h$ are multiplicative (and that this holds true for their Dirichlet products too, because of this). Thus it suffices to derive our equality for $n=p^k$, with $p$ prime. We have $$f * g(n) =\sum_{d \mid n} \varphi(d)=n$$ by (for example) partitioning the cyclic group of order $n$ with respect to elemental order. Thus $$(f*g)*h(p^k)=\sum_{i=0}^k p^{k-i} \sigma(p^i)=\sum_{i=0}^k p^{k-i} \frac{p^{i+1}-1}{p-1}=\frac{(k+1)p^{k+2}-(k+2)p^{k+1}+1}{(p-1)^2}$$ Next, we calculate $$g * h(p^k)=\sum_{i=0}^k \sigma(p^i)=\sum_{i=0}^k \frac{p^{i+1}-1}{p-1}=\frac{1}{p-1}\sum_{i=0}^kp^{i+1}-1=\frac{p^{k+2}-p(k+2)+k+1}{(p-1)^2},$$ and so $$f*(g*h)(p^k)=\sum_{i=0}^k\varphi(p^{k-i})\frac{p^{i+2}-p(i+2)+i+1}{(p-1)^2}$$ $$=\frac{p^{k+2}-p(k+2)+k+1}{(p-1)^2}+\sum_{i=0}^{k-1} p^{k-i-1}\frac{p^{i+2}-p(i+2)+i+1}{p-1}$$ wherein we have had to split this sum because $\varphi(p^0) =1\neq p^{-1}(p-1)$, which requires a special case. I won't write out the final simplifications of this product because Mathematica can do all of what's left (with greater accuracy than me, too!), but suffice it to say that you will end up with $$\frac{(k+1)p^{k+2}-(k+2)p^{k+1}+1}{(p-1)^2}$$ as predicted.

As a general rule, you can always plod through these sorts of things when you have multiplicative functions.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.