A GCD summation $\sum_{\gcd(i,n)=1} \gcd(i-1,n)$

Question

Let $$\ n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\ldots$$ where $p_1,p_2\ldots$ are prime factors of $n$.

Show that
$$\sum_{i=1,\,\gcd(i,n)=1}^n \gcd(i-1,n) = \prod_{} (a_i+1)(p_i-1)p_i^{a_i-1}.$$

I was able to prove it for $n$ having only one prime factor, but I don't know how to proceed for the general case. Assume $\gcd(0,n)=n$.

Answer 1

The RHS of your identity is $\tau(n)\phi(n)$, which was very suggestive, so I made some google search and I found the what you want to prove is known as Menon's identity, but in that link there is no proof about this result, however I found another link where this identity is proved. The proof only uses elementary number theory.

By the way, Menon's identity has been generalized in different ways. Here are some of them:

1. Menon’s identity and arithmetical sums representing functions of several variables

2. A generalization of Menon’s identity

3. A generalization of Menon's identity with respect to a set of polynomials

4. Another generalization of the gcd-sum function