In 1965 Puliyakot Keshava Menon proved that $${\displaystyle \sum _{\substack {1\leq k\leq n \\ \gcd(k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n)}$$ being $\varphi(n)$ the totient function of $n$. If we move under summation the function $d(n)$ (the function that counts the divisors of $n$), that is if we consider the function $${\displaystyle g(n)=\sum _{\substack {1\lt k\leq n \\ \gcd(k,n)=1}}d(k-1)}$$ and analyze its behavior up to $n=10^6$, we find that (for $n\gt35$) $${\displaystyle 1 \lt \frac {g(n)} {\varphi (n)log(n)} \lt 2}$$ Is there a way to prove the above bounds?

Many thanks.

  • $\begingroup$ What is the value of $d(0)$? $\endgroup$
    – saulspatz
    Commented Jun 7, 2021 at 20:08
  • $\begingroup$ @saulspatz Thanks. I have corrected the question. $\endgroup$ Commented Jun 7, 2021 at 20:17
  • $\begingroup$ You may be interested to know (apart from the asymptotics) that there are multi-dimensional generalizations of this identity. I remember proving it using Burnside's lemma somewhere on this site, but the generalizations are equally magnificent to look at, and may pique your interest. $\endgroup$ Commented Jun 8, 2021 at 23:46

1 Answer 1


We can actually deduce an asymptotic expression for the sum $g(n)$ using some known estimates. I'll present a sketch of the calculation.

First remove the coprimality condition using Mobius inversion: $$ g(n) = \sum_{2\leq k\leq n} d(k-1) \sum_{a\mid (k,n)} \mu(a). $$ Inverting the order of summation gives $$ g(n) = \sum_{a\mid n} \mu(a) \sum_{\substack{2\leq k\leq n\\ a\mid k}} d(k-1). $$ After a change of variables, the inner sum is $$ \sum_{\substack{2\leq k\leq n\\ a\mid k}} d(k-1) = \sum_{\substack{m\leq n\\ m\equiv-1 (\text{mod}\ a)}} d(m). $$ Using a result of Pongsriiam and Vaughn (see this paper, for instance), we have $$ \sum_{\substack{m\leq n\\ m\equiv-1 (\text{mod}\ a)}} d(m) = \frac{1}{\phi(a)} \sum_{\substack{1\leq m\leq n\\(n,a)=1}} d(m) + O\left(n^{1/2+\epsilon}\right). $$ The Dirichlet series assosiated to the sum on the right is $$ \zeta(s)^2 \prod_{p\mid a} \left(1-\frac{1}{p^s}\right)^2. $$ A calculation involving Perron's Formula gives $$ \sum_{\substack{1\leq m\leq n\\(m,a)=1}} d(m) = n \left(\frac{\phi(a)}{a}\right)^2\left(\log n + 2\gamma-1+2\sum_{p\mid a} \frac{\log p}{p-1}\right) + O\left(d(a)n^{3/4}(\log n)^2\right). $$ (This is not the sharpest error term one can get, but it suffices here.)

Combining things, we have $$ g(n) = n\sum_{a\mid n} \frac{\mu(a)\phi(a)}{a^2} \left(\log n + 2\gamma-1+2\sum_{p\mid a} \frac{\log p}{p-1}\right) + O\left(n^{3/4+\epsilon}\right). $$ Returning to your actual question, the leading order term is $$ n\log n \sum_{a\mid n} \frac{\mu(a)\phi(a)}{a^2} = n\log n \prod_{p\mid n} \left(1-\frac{1}{p}\right)\prod_{p\mid n}\left(1+\frac{1}{p^2-p}\right) = \phi(n)\log n \prod_{p\mid n}\left(1+\frac{1}{p^2-p}\right) $$ A numerical computation shows that $$ 1 < \prod_{p\mid n}\left(1+\frac{1}{p^2-p}\right) < \prod_{p}\left(1+\frac{1}{p^2-p}\right)< 2 $$ for all $n$ (since the product can be extended to infinity absolutely). I'm not sure if your estimate holds for all $n$, but it at least holds for all sufficiently large $n$.


You must log in to answer this question.

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