5
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Thomas Andrews Jan 1 '17 at 21:10
  • 2
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Jan 1 '17 at 21:12
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$

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.