3
$\begingroup$

(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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yeah David, good idea! It works, I'm going to perform the precise computation. Thanks a lot! $\endgroup$ – PITTALUGA May 9 '14 at 16:48
  • $\begingroup$ 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$. $\endgroup$ – Ramin May 16 '14 at 3:42
  • $\begingroup$ @Ramin: not all odd numbers are divisible by 3, unfortunately :-) $\endgroup$ – David Loeffler May 16 '14 at 10:07
  • $\begingroup$ @DavidLoeffler That's very true, and it turns out that not for many integers $n$, the expression $8n/\pi^2$ is an integer. :-) $\endgroup$ – Ramin Jun 1 '14 at 20:46
  • $\begingroup$ 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$. $\endgroup$ – David Loeffler Jun 1 '14 at 22:42

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.