# Estimate sum with Euler function

(Note: this question was posted also in MSE)

I'd like to know if there's a closed formula or at least an estimate for the following (finite) sum: $$\sum_{D|p-1} \varphi(D) \,\varphi\left(\frac{p-1}{D} \right) \frac{1}{D}$$ where $\varphi(n)$ is the Euler totient function. An upper bound would come from $$\varphi(D) \,\varphi\left(\frac{p-1}{D} \right) \leq \varphi(p-1)$$ so I get $$\varphi(p-1)\sum_{D|p-1}\frac{1}{D} = \varphi(p-1)\frac{\sigma(p-1)}{p-1}$$

Can I do better than this? No closed formula?

You use $p - 1$, suggesting that you are thinking of the case where $p$ is prime; but one might as well consider the sum $$f(n) := \sum_{d \mid n} d^{-1} \varphi(d) \varphi(n/d)$$ for arbitrary positive integers $n$. Now it is clear that $f$ is a weakly multiplicative function (that is, we have $f(mn) = f(m) f(n)$ if $m$ and $n$ are coprime) so it's enough to understand $f(\ell^k)$ for $\ell$ prime and $k \ge 1$. A fiddly but easy calculation shows that $f(\ell^k)$ is something like $(\ell^2-1) \ell^{k-2}$. So you get $$f(n) = n \prod_{\ell \mid n} (1 - 1/\ell^2).$$
• In particular, if $n$ is even, which $p-1$ is, you always have $0.6 n \leq f(n) \leq 0.75 n$. If $n$ is odd, you get $8n/\pi^2 \leq f(n) \leq 8n/9$. – Ramin May 16 '14 at 3:42
• @DavidLoeffler That's very true, and it turns out that not for many integers $n$, the expression $8n/\pi^2$ is an integer. :-) – Ramin Jun 1 '14 at 20:46
• Ramin: I wasn't just being facetious. My point is that your claim "If $n$ is odd, you get $f(n) \le 8n/9$" is false, since it seems to be based on the assumption that $3 \mid n$. – David Loeffler Jun 1 '14 at 22:42