前言
其实这是某大佬的 PPT 里的一个问题，觉得很有意思，就花了一些时间想了想。
问题
总所周知，组合数的数论定义式是 \(\frac {(n-m+1)\times (n-m+2)\times \cdots \times n} {1\times 2\times 3\times \cdots \times m}\)。
那么，仅通过这个定义式，如何证明组合数一定是整数呢？
证明
感性的证明
一个组合数，可以看成是连续的 \(m\) 个正整数的积除以 \(m!\)。
那么，我们可以先找到所有 \(m!\) 的质数，从小到大分别是 \(p_1,p_2,p_3 \cdots p_x\)。
那么，我们可以考虑枚举质数。
对于质数 \(p_i\)，包含了因子 \(p_i\) 的数，在 \([1,m]\) 中应当有 \(\lfloor \frac m {p_i} \rfloor\) 个，在 \([n-m+1,n]\) 中也应当有 \(\lfloor \frac m {p_i} \rfloor\) 个。
那么，把这些数全部除以 \(p_i\)。
再考虑包含了因子 \({p_i}^2\) 的数，在两个区间都应该有\(\lfloor \frac m {{p_i}^2} \rfloor\) 个，同样全部除掉。
再考虑 \({p_i}^3\) 一直到 \({p_i}^k\)，这样的话，我们就可以发现可以完全地把质因子 \(p_i\) 的影响消去。
所以当我们把所有的质因子全部消去时，分母就是 \(1\)，分子还剩下一些 \(>p_x\) 的质因子，所以一定是整数。
严谨的证明
上面的证明，我自己感觉比较正确，但是感觉不够数学，所以又想了一种大概是归纳法的证明方法。
我们考虑证明 \(m=i\) 的情况，假设 \(m<i\) 的情况都已经证明一定正确。
再构造两个数列 \(a\) 和 \(b\)，最开始，都是 \(\{1,2,3\cdots i\}\)。
把序列 \(a\) 的积看作分子，序列 \(b\) 的积看作分母，那么这个比值就对应某个组合数，通过把 \(a\) 整体加上一个数，来表示所有的 \(m=i\) 的组合数。
首先，原始的序列 \(a\)，对应 \(n=i\) 的情况，并且一定是整数。
现在考虑 \(n=i+1\) 的情况，也就是把序列 \(a\) 整体加上 \(1\) 的情况。
我们可以把中间 \(i-1\) 个相同的数都消去，这样序列 \(a\) 仅留下 \(i+1\)，序列 \(b\) 仅留下 \(1\)，这个显然是整数对吧，不过，我们眼光还要放长远一些，这个不就是 \(m=1\) 的组合数吗？因为 \(m<i\) 的组合数我们都看作已经证明是整数了，所以这种情况是对的。
再把序列 \(a\) 加 \(1\)，那么这一次序列 \(a\) 留下的是 \(\{i+1,i+2\}\)，序列 \(b\) 留下的是 \(\{1,2\}\)，这又对应 \(m=2\) 的组合数，也是证明过的。
再不断地把 \(a\) 加 \(1\)，可以分别对应 \(m=k,k\in [1,i-1]\) 的所有组合数情况。
但是，当 \(a\) 加了 \(i\) 次时，就没有可以对应的了，这该怎么证明呢？
可以先看看 \(i-1\) 次的时候，序列 \(a\) 是 \(\{i,i+1,\cdots,2\times i -1\}\)，序列 \(b\) 是 \(\{1,2,3\cdots,i\}\)。
因为对应了 \(m=i-1\) 的组合数，所以一定是整数，这个时候，再把序列 \(a\) 都加上 \(1\)，可以等价地看作去掉 \(i\)，加上 \(2\times i\)，所以序列 \(a\) 的积扩大了两倍，也一定是整数。
那么，再往后面继续加 \(1\)，证明方式也同理，所以我们证明得到了 \(m=i\) 的组合数都一定是整数，再继续证明 \(m=i+1\)，后续都一定可以证明，所以推广到 \(m\) 是任意数，组合数都一定是整数，证明完毕。