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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).$$

Improve this answer
$\endgroup$
5
  • $\begingroup$ Yeah David, good idea! It works, I'm going to perform the precise computation. Thanks a lot! $\endgroup$
    – PITTALUGA
    May 9, 2014 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, 2014 at 3:42
  • $\begingroup$ @Ramin: not all odd numbers are divisible by 3, unfortunately :-) $\endgroup$
    – David Loeffler
    May 16, 2014 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, 2014 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, 2014 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.