一道整除问题的组合意义证法——2009年罗马尼亚大师杯第1题

2009年罗马尼亚大师杯 第1题

对正整数a_(1),a_(2),⋯,a_(k)，记

令d是a_(1),a_(2),⋯,a_(k)的最大公约数，求证：(d)/(n)((n)/(a_(1),⋯,a_(k)))是整数．

分析

本题比较自然的方法是计算幂次进行比较，也可以用Kummer定理进行理解．

更巧妙的方法则是用Bézout定理表示最大公约数，再使用组合恒等式化简．

注意到((n)/(a_(1),⋯,a_(k)))表示可重排列，而除以n往往是圆排列中进行的操作，于是可以想到对可重圆排列进行计数，从而给出一个组合意义的证明．

证明

设X为所有含a_(i)个i（1≤i≤k）的长度为n的排列集合，则

按循环旋转将X分成若干等价类．任取一个排列，设它的最小正周期为t，则其所在等价类的大小也为t．

由于该排列由(n)/(t)个相同的块重复组成，所以每个 a_(i)都能被(n)/(t)整除．

而d是a_(1),a_(2),⋯,a_(k)的最大公约数，因此(n)/(t)∣d，从而(n)/(d)∣t．

将所有等价类大小相加，得到((n)/(a_(1),⋯,a_(k)))．因此

即(d)/(n)((n)/(a_(1),⋯,a_(k)))是整数．