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

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

• You need to show this sum is a multiplicative function of $n$ - that is, if $f(n)$ is your sum and $n,m$ are relatively prime, then $f(nm)=f(n)f(m)$. Jan 1, 2017 at 21:10
• Alternatively, you need to come up with an argument for why the sum is $\tau(n)\phi(n)$, since that is the value on the right, where $\tau(n)$ is the number of divisors of $n$ and $\phi(n)$ is Euler's totient function. Jan 1, 2017 at 21:12

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.