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
    Commented 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
    Commented May 16, 2014 at 3:42
  • $\begingroup$ @Ramin: not all odd numbers are divisible by 3, unfortunately :-) $\endgroup$
    – David Loeffler
    Commented 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
    Commented 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
    Commented Jun 1, 2014 at 22:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .