一道数论题的两种证法

本站人工转写（文字版）

下面这段文字由本站对照上方图片逐条录入，公式写成可读的记号，只为方便检索与读屏；它不是公众号原文的一部分，如与图片或原文有出入，请以原文为准。

1. 1.（2000 年 Putnam 数学竞赛）已知正整数 $m,n$ 满足 $n\ge m$，求证：$\frac{\gcd(m,n)}{n}\binom{n}{m}$ 为整数．
2. 证明 1：由裴蜀定理，存在整数 $a,b$，使得 $\gcd(m,n)=an+bm$，于是 $\frac{\gcd(m,n)}{n}\binom{n}{m}=a\binom{n}{m}+\frac{bm}{n}\binom{n}{m}=a\binom{n}{m}+\frac{bmn!}{nm!(n-m)!}=a\binom{n}{m}+\frac{b(n-1)!}{(m-1)!(n-m)!}=a\binom{n}{m}+b\binom{n-1}{m-1}\in\mathbb{Z}$．
3. 证明 2：$n$ 个白球等间距地摆放在一个圆周上，选取其中 $m$ 个白球染成黑色．如果一种染色方案经过旋转后与另一种重合，则认为这两种染色方案是等价的．对于任意一种染色方案，其旋转 $n$ 次（每次一格）后必与自身重合，设其至少旋转 $d$（$d>0$）次后与自身重合，易知 $\frac{n}{d}\mid\gcd(m,n)$．于是 $\frac{n}{\gcd(m,n)}$ 能整除每个等价类中的元素个数 $d$，从而也能整除染法总数 $\binom{n}{m}$，证毕．