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?


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


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.