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?