1972.国际奥林匹克IMO.3数论——Legendre定理与高斯函数不等式

原文迁自 B 站 · B 站标注的最后编辑日期：2023-08-26。正文与配图按原文保留。

世界的意义必定在世界之外。世界中一切事情就如它们之所是而是，如它们之所发生而发生；世界中不存在价值——如果存在价值，那它也会是无价值的。

——《逻辑哲学论》路德维希‧维特根斯坦

---

$$(1972.IMO.3)$$

$m,n\in \mathbb{N}($规定$0!=1)$

证明$:\frac{(2m)!(2n)!}{m!n!(m+n)!}\in \mathbb{Z}$

---

引理$1(Legendre$定理，勒让德定理)：

$n!$中任意素因子$p$的次幂$e$满足关系：

$$e=\sum_{i=1}^{\infty}[\frac{n}{p^i} ]$$

证明详见《初等数论》教材，高等教育出版社。

引理$2($高斯函数):

对$\forall a,b\in \mathbb{R}:$

$$[a]+[b]+[a+b]≤[2a]+[2b]$$

引理$2$证明：

定义$\{a\}=a-[a]$

$I.$若$\{a\},\{b\}≥\frac{1}{2}:$

$$\begin{aligned} & RHS=2[a]+2[b]+2 \\[0.5em] & LHS=[a]+[b]+[a]+[b]+1 \\[0.5em] & ∴RHS>LHS \end{aligned}$$

$II.$若$\{a\},\{b\}<\frac{1}{2}:$

$$RHS=2[a]+2[b]=LHS$$

$III.$若$1>\{a\}≥\frac{1}{2}>\{b\}:$

$$\begin{aligned} & RHS=2[a]+2[b]+1 \\[0.5em] & LHS≤2[a]+2[b]+1 \\[0.5em] & ∴RHS≥LHS \end{aligned}$$(由对称性知另一部分成立)

综上引理$2$得证。

现在来证明我们的原命题：

原命题转化为:

$$m!n!(m+n)!|(2m)!(2n)!$$

构造函数$V_{p_i}(x)$为$x$标准分解式中$p_i$的次幂大小。

$p_i$为$x$素因子

则原命题转化为:

$$\begin{aligned} & \forall p_i,V_{p_i}(m!n!(m+n)!)= \\[0.5em] & V_{p_i}(m!)+V_{p_i}(n!)+V_{p_i}((m+n)!) \\[0.5em] & ≤V_{p_i}((2m)!(2n)!)=V_{p_i}((2m)!)+V_{p_i}((2n)!) \end{aligned}$$

由引理$1(Legendre$定理):

即证$:\sum\nolimits_{i=1}^{\infty } [\frac{m}{p^i}]+[\frac{n}{p^i}]+[\frac{n+m}{p^i}] ≤$

$$\sum\nolimits_{i=1}^{\infty }[\frac{2m}{p^i}]+[\frac{2n}{p^i}]$$

由引理$2$知:

$[\frac{m}{p^i}]+[\frac{n}{p^i}]+[\frac{n+m}{p^i}]≤[\frac{2m}{p^i}]+[\frac{2n}{p^i}]$恒成立

所以上述式子恒成立，命题成立。

证毕。

---

勒让德定理是数论中常见且基本的一个定理，一般在学习素数基本定理的时候会补充。本题思路并无难处，但是步骤较为繁琐（也指我码字繁琐），能够熟悉高斯函数的性质是关键。

高中生自行整理，如有错误，欢迎指出。