奥数数论

勒让德公式是计算阶乘与二项系数精确素数幂整除性的标准工具,与库默尔定理结合可精确解释哪些二项系数能被给定素数整除。

**第1步:将 $v_p(n!)$ 写成对各因子的求和。** 由定义 $n! = 1\cdot 2\cdots n$,故 $v_p(n!) = \sum_{k=1}^{n} v_p(k)$,即从 $1$ 到 $n$ 每个整数的 $p$进赋值之和。

**第2步:将每个 $v_p(k)$ 改写为计数。** 对每个 $k$,$v_p(k) = \sum_{i=1}^{\infty} [p^i \mid k]$(用艾弗森记号,真为 $1$,假为 $0$),因为 $k$ 恰好对 $v_p(k)$ 个 $i$ 值(即 $i=1,\dots,v_p(k)$)能被 $p^i$ 整除。

第3步:交换求和顺序。 代入得 $v_p(n!) = \sum_{k=1}^n \sum_{i=1}^{\infty} [p^i \mid k] = \sum_{i=1}^{\infty} \sum_{k=1}^n [p^i \mid k]$,交换(有限从而合理的)双重求和。

**第4步:直接计数 $p^i$ 的倍数。** 内层和 $\sum_{k=1}^n [p^i \mid k]$ 计数 $1$ 到 $n$ 中有多少整数是 $p^i$ 的倍数,恰为 $\left\lfloor \frac{n}{p^i} \right\rfloor$(这些倍数为 $p^i, 2p^i, \dots, \lfloor n/p^i\rfloor \cdot p^i$)。

第5步:结论。 代回得 $v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$,由于一旦 $p^i > n$ 就有 $\lfloor n/p^i \rfloor = 0$,故该和有限,证明完成。

升幂引理把关于高次幂之差整除性的难题变成关于赋值的简单算术,是解决要求整除 $a^n-b^n$ 之类表达式的最大素数幂次,或证明该表达式永不(或总是)被某个素数幂整除的奥数问题的最快方法之一。

**第1步:利用乘性归结到 $n=p$ 的情形。** 写 $n = p^{v_p(n)} \cdot m$,其中 $p \nmid m$。将下面证明的 $n=p$ 情形反复应用于 $a^m, b^m$(代替 $a,b$),可得 $v_p(a^n-b^n) = v_p((a^m)^{p^{v_p(n)}} - (b^m)^{p^{v_p(n)}}) = v_p(a^m-b^m) + v_p(n)$,故只需证明当 $p \nmid m$ 时 $v_p(a^m - b^m) = v_p(a-b)$,以及证明基础步骤 $v_p(a^p-b^p) = v_p(a-b)+1$。

第2步:用因式分解证明基础步骤。 分解 $a^p - b^p = (a-b)(a^{p-1}+a^{p-2}b+\cdots+b^{p-1})$。需证第二个因子 $S = \sum_{j=0}^{p-1} a^{p-1-j}b^j$ 满足 $v_p(S) = 1$。

**第3步:证明 $p \mid S$。** 由 $p \mid a-b$ 得 $a \equiv b \pmod p$,故每一项 $a^{p-1-j}b^j \equiv b^{p-1-j}b^j = b^{p-1} \pmod p$。将全部 $p$ 项相加,$S \equiv p\cdot b^{p-1} \equiv 0 \pmod p$(利用 $p \nmid b$),故 $p \mid S$。

**第4步:证明 $p^2 \nmid S$。** 写 $a = b + pt$($t$ 为整数,因 $p\mid a-b$ 而可行)。展开每一项 $a^{p-1-j}b^j = (b+pt)^{p-1-j}b^j \equiv b^{p-1-j}b^j + (p-1-j)pt\, b^{p-2-j}b^j \pmod{p^2}$(二项式展开,舍去 $p^2$ 及以上的项)。对 $j=0,\dots,p-1$ 求和:首项之和如前为 $p\,b^{p-1}$,修正项之和为 $pt\,b^{p-2}\sum_{j=0}^{p-1}(p-1-j) = pt\,b^{p-2}\cdot\frac{p(p-1)}{2}$,可被 $p^2$ 整除(因 $p$ 为奇数,$\frac{p-1}{2}$ 为整数,故此修正项为 $p^2\cdot(\text{integer})$,即 $\equiv 0 \pmod{p^2}$)。于是 $S \equiv p\,b^{p-1} \pmod{p^2}$,又因 $p \nmid b$,$p\,b^{p-1}$ 能被 $p$ 整除但不能被 $p^2$ 整除,得 $v_p(S)=1$。

第5步:合并。 由第2–4步,$v_p(a^p-b^p) = v_p(a-b) + v_p(S) = v_p(a-b)+1$。结合第1步的归约(以及当 $p\nmid m$ 时 $v_p(a^m-b^m)=v_p(a-b)$ 这一事实,此时 $S \equiv m\,b^{m-1} \not\equiv 0 \pmod p$,可同法证明),对 $v_p(n)$ 归纳即得对所有正整数 $n$ 有 $v_p(a^n-b^n) = v_p(a-b)+v_p(n)$。