0
$\begingroup$

Motivated by this question, My question pertains to closed form of the sum $$\sum_{d|n}\frac{\phi(d)}{d}$$

There are some formulae and expressions for $\sum_{n}\frac{\phi(n)}{n}$, but what about when we replace $n$ by divisors of $n$ By seeing this question, I think the sum is multiplicative. Any hints? Thanks beforehand.

$\endgroup$
1
$\begingroup$

Here is not a closed form, but an alternative representation. Below, $(x,y)={\rm gcd}(x,y)$.

I claim that $$\sum_{k=1}^n (k,n)=n\sum_{d\mid n}\frac{\phi(d)}{d}. $$ To see this, observe that if $d\mid n$ is a divisor of $n$ $$ (k,n)=d \iff \left(\frac{k}{d},\frac{n}{d}\right)=1. $$ In particular, the divisor, $d$, appears exactly $\phi(n/d)$ times in the summation. Thus, $$ \sum_{k=1}^n (k,n)=\sum_{d\mid n}\phi(\frac{n}{d})d. $$ Now, letting $d'=n/d$, the sum can be rewritten as, $$ \sum_{k=1}^n (k,n)=n\sum_{d'\mid n}\frac{\phi(d')}{d'}. $$ Hence, this object has the given operational meaning.

Now, for multiplicative property, take coprime $(m,n)$. Our goal is to show, $$ \left(\sum_{d\mid mn}\frac{\phi(d)}{d}\right) = \left(\sum_{d\mid m}\frac{\phi(d)}{d}\right)\left(\sum_{d\mid n}\frac{\phi(d)}{d}\right). $$ Check that, the left hand side sum has $\phi(mn)=\phi(m)\phi(n)$ terms, so do the right hand side. Furthermore, each divisor $d\mid mn$ can be uniquely decomposed into $d=d_1d_2$ where $d_1\mid m$ and $d_2\mid n$, since $(m,n)=1$. Hence, we deduce the given function is indeed multiplicative.

Remarks: In fact, more is known about this function.

Theorem: For any positive integer $a$, there exists a positive integer $n$, such that, $$ \sum_{d\mid n}\frac{\phi(d)}{d}=a. $$

Try to prove this theorem, it is nice ;)

$\endgroup$
0
$\begingroup$

After a little observation, the sum is similar to evaluating $\sum_{d|n}d\phi(d)$. Since the function $\sum_{d|n}\frac{\phi(d)}{d}$ is (weakly) multiplicative, therefore, it suffices to evaluate the sum for prime powers. We have, $$\sum_{d|p^k}\frac{\phi(d)}{d}=1+\frac{p-1}{p}+\frac{p^2(p-1)}{p^3}+\ldots+\frac{p^k(p-1)}{p^{k+1}}$$ $$=1+k\frac{p-1}{p}$$ Hence the form of the sum for any general $n=\prod_ip_i^{k_i}$ is: $$\sum_{d|n}\frac{\phi(d)}{d}=\prod_{i}\left(1+k_i\frac{p_i-1}{p_i}\right)$$ where $n$ is the product of $p_i$ distinct primes with multiplicity $k_i$

$\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.