Menon’s identity

Question

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?

Answer 1

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