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\)的最大公约数如此优美的联系!

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

证明:

令\(G\)为模\(n\)的乘法群它的阶显然是\(\varphi(n)\)。令\(S\)为\(\{1,\ldots,n\}\)

考虑\(G\)对\(S\)的一个作用 \(x · y \equiv x*y\pmod n\)。

在这个作用下,两个数具有相同的轨道当且仅当他们和\(n\)的最大公约数相同。

所以本质不同的轨道数目为\(d(n)\)个。

另一方面,对于\(G\)中的每一个元素\(a\),满足\(a·b\equiv b\pmod n\)的\(b\)的个数是\(\gcd(a-1,n)\)个。

由Burnside引理,我们就可以得到本文开头的那个式子!

Leave a Reply

Your email address will not be published. Required fields are marked *