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

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

对正整数，记

令是的最大公约数，求证：是整数．

分析

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

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

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

证明

设为所有含个（）的长度为的排列集合，则

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

由于该排列由个相同的块重复组成，所以每个 都能被整除．

而是的最大公约数，因此，从而．

将所有等价类大小相加，得到．因此

即是整数．