如何证明对任意正整数(m,n)，m!n!(m+n)!整除(2m)!(2n)!

阿华AIGC实验室

2026-5-19

证明 $m!n!(m+n)! \mid (2m)!(2n)!$ 对任意正整数对 $(m,n)$ 成立

嘿，我来一步步拆解这个数论整除性问题的证明过程：

我们的核心目标是证明：对于任意正整数对 $(m,n)$，$m!n!(m+n)!$ 能整除 $(2m)!(2n)!$，也就是数学表达式 $m!n!(m+n)! \mid (2m)!(2n)!$。

第一步：转化为素因子指数的不等式

要证明阶乘乘积的整除关系，我们可以用Legendre公式——这个公式告诉我们，素数 $p$ 在 $k!$ 中的指数等于 $\sum_{i=1}^{\infty} \left\lfloor \frac{k}{p^i} \right\rfloor$（这里的 $\lfloor x \rfloor$ 是向下取整函数，也就是不大于 $x$ 的最大整数）。

整除关系的本质是：对任意素数 $p$，$p$ 在被除数中的指数不小于它在除数中的指数。所以原命题等价于证明：对任意素数 $p$，以下不等式成立：
$$
\sum_{i=1}^{\infty}\left\lfloor\frac m{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac n{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac {m+n}{p^i}\right\rfloor \le\sum_{i=1}^{\infty}\left\lfloor\frac {2m}{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac {2n}{p^i}\right\rfloor
$$

第二步：简化到单一项的不等式

因为求和的每一项都是独立的，我们只需要证明对每个正整数 $i$，下面的单一项不等式成立就行：
$$
\left\lfloor\frac{m}{p^i}\right\rfloor + \left\lfloor\frac{n}{p^i}\right\rfloor + \left\lfloor\frac{m+n}{p^i}\right\rfloor \le \left\lfloor\frac{2m}{p^i}\right\rfloor + \left\lfloor\frac{2n}{p^i}\right\rfloor
$$
只要每一项都满足，求和后的整体不等式自然成立。

第三步：用带余除法拆分变量

令 $a = \left\lfloor\frac{m}{p^i}\right\rfloor$，$b = \left\lfloor\frac{n}{p^i}\right\rfloor$，然后把 $m$ 和 $n$ 拆成：
$m = a p^i + r$，$n = b p^i + s$，其中 $0 \le r,s < p^i$（这就是带余除法，$r$ 和 $s$ 是余数）。

把这些代入到单一项不等式里：

$\left\lfloor\frac{m+n}{p^i}\right\rfloor = a + b + \left\lfloor \frac{r+s}{p^i} \right\rfloor$
$\left\lfloor\frac{2m}{p^i}\right\rfloor = 2a + \left\lfloor \frac{2r}{p^i} \right\rfloor$
$\left\lfloor\frac{2n}{p^i}\right\rfloor = 2b + \left\lfloor \frac{2s}{p^i} \right\rfloor$

代入后两边的 $a+b+a+b$ 会抵消，最终我们只需要证明：
$$
\left\lfloor \frac{r+s}{p^i} \right\rfloor \le \left\lfloor \frac{2r}{p^i} \right\rfloor + \left\lfloor \frac{2s}{p^i} \right\rfloor
$$

第四步：分情况验证不等式

因为 $0 \le r,s < p^i$，所以 $2r$ 和 $2s$ 要么小于 $p^i$（此时向下取整为0），要么在 $[p^i, 2p^i)$ 之间（此时向下取整为1）。我们分四种情况讨论：

情况1：$r < \frac{p^i}{2}$ 且 $s < \frac{p^i}{2}$
此时 $r+s < p^i$，左边 $\left\lfloor \frac{r+s}{p^i} \right\rfloor = 0$；右边两个项都是0，不等式 $0 \le 0+0$ 成立。
情况2：$r \ge \frac{p^i}{2}$ 且 $s < \frac{p^i}{2}$
右边 $\left\lfloor \frac{2r}{p^i} \right\rfloor = 1$，$\left\lfloor \frac{2s}{p^i} \right\rfloor = 0$，总和是1；左边 $\left\lfloor \frac{r+s}{p^i} \right\rfloor$ 最多是1（因为 $r+s < p^i + \frac{p^i}{2} = \frac{3p^i}{2}$），显然 $1 \le 1$，不等式成立。
情况3：$r < \frac{p^i}{2}$ 且 $s \ge \frac{p^i}{2}$
和情况2完全对称，右边总和是1，左边最多1，不等式成立。
情况4：$r \ge \frac{p^i}{2}$ 且 $s \ge \frac{p^i}{2}$
右边两个项都是1，总和是2；左边 $r+s \ge p^i$，所以 $\left\lfloor \frac{r+s}{p^i} \right\rfloor$ 要么是1要么是2，不管哪种情况都 $\le 2$，不等式成立。