A Proof of Menon’s Identity Using Burnside’s Lemma

$$\sum_{i=1}^n [\gcd(i,n)=1] \gcd(i-1,n) = \varphi(n) d(n)$$

第一次看到这个式子的时候,我就觉得非常神奇。\(i\)与\(n\)的互素关系竟然和\(i-1\)与\(n\)的最大公约数如此优美的联系!

然而,我看到这个等式的证明以后,更加地被震撼了!

Continue reading A Proof of Menon’s Identity Using Burnside’s Lemma