I also put this question in stackexchange, but remained unanswered. <https://math.stackexchange.com/questions/506996/menons-identity>


Let $G$ be a group of order $n$. Consider an action of $U\_n$, the group of invertible residues modulo $n$, on $G$. With each $s\in U\_n$ we associate the permutation of $G$, $\psi\_s$, defined by  

$$\psi\_s(g)=g^s,$$
for all $g\in G$. 


Under this action two elements belong to the same orbit if and only if they generate the same cyclic subgoup. Thus the number of orbits, which we shall denote by $c(G)$, is equal to the number of cyclic subgroups of $G$. By Burnside's Lemma we have the relation:
 $$c(G)=\frac{1}{\varphi(n)}\sum\_{s\in U\_n}|F(s)|.$$ 
Here $\varphi(n)$ is the Euler totient function, while $F(s)$ is the fixed set of $\psi\_s$, that is, the set of elements in $G$ which satisfy the equation $x^{s-1}=1$. 


If $G$ is a cyclic group or order $n$, then $c(G)$ is equal to $d(n)$, the number of divisors of $n$, and $|F(s)|$ is equal to $(s-1, n)$. We conclude that


$$d(n)=\frac{1}{\varphi(n)}\sum\_{s\in U\_n}(s-1, n).$$


This identity is known as Menon’s identity and this dedution appears in the paper 


"A remark on the number of cyclic subgroups of a finite group" by I. M. Richards.


In this paper the the author states without proof that for a polynomial $f(x)$ in $\mathbb Z[x]$ we have 


$$\sum\_{s\in U\_n}(f(s), n)=\varphi(n)\sum\_{d|n}|\{r\in U\_d; f(r)\equiv 0 \;\;mod\;d\}|.$$


How can we prove this last identity?



Menon’s identity
[This is a corrected version of my previous answer, in which I incorrectly said that the identity was false. I apologize for getting it wrong the first time.]


Here is a proof of the identity. Since both sides are multiplicative functions of $n$, it suffices to prove the identity when $n$ is a prime power, say $n=p^k$. Write 
$$
C\_i = \lvert\{r\in U\_{p^i}: f(r)\equiv 0 \bmod p^i\}\rvert.
$$
Then the number of $s\in U\_n$ for which $(f(s),n)=p^k$ is $C\_k$, and for $0<i<k$ the number of $s\in U\_n$ for which $(f(s),n)=p^i$ is $p^{k-i}C\_i-p^{k-i-1}C\_{i+1}$. Finally, the number of $s\in U\_n$ for which $(f(s),n)=1$ is $(p^k-p^{k-1})C\_0-p^{k-1}C\_1$, so
$$
\sum\_{s\in U\_n} (f(s),n) = p^k C\_k + \sum\_{i=1}^{k-1} p^i(p^{k-i}C\_i-p^{k-i-1}C\_{i+1}) + (p^k-p^{k-1})C\_0 - p^{k-1}C\_1
$$
which equals
$$
(p^k-p^{k-1})\sum\_{i=0}^k C\_i,
$$
as desired.


Incidentally, Menon's identity has been generalized in many other ways, as I learned from google.


