阶乘的估值

像 100! 这样的巨数末尾有多少个零？这个听起来简单的问题，为我们打开了通往数论一个深刻领域的大门：阶乘的估值。其核心是在一个巨大的乘积中计算素因子的数量，这是一项朴素方法无法正确解决的任务。本文通过引入一种强大而优雅的方法来确定任意素数在阶乘中的确切幂次，从而填补这一知识鸿沟。在接下来的章节中，我们将首先探讨“原理与机制”，揭示 Adrien-Marie Legendre 的经典公式以及一个涉及数字各位的惊人替代方法。然后，在“应用与跨学科联系”部分，我们将看到这一个工具如何揭示组合数学、抽象代数乃至一种奇特微积分学中的深刻真理，从而展示其在整个数学领域的基础重要性。

想象一个巨大的数，比如说 100 的阶乘，记作 $100!$。这是从 1 到 100 所有整数的乘积。如果你把这个数写出来，它将有 158 位。我们可能会问一个简单的问题：这个数末尾有多少个零？这等同于问：10 的最高多少次幂可以整除 $100!$？由于 $10 = 2 \times 5$，这个问题就归结为在 $100!$ 的素因子分解中找到因子 2 和 5 的数量。零的个数将由出现次数较少的那个素数决定。在这次探索中，我们将发现一个出乎意料地优雅而强大的工具，用以回答这个问题以及更多普遍的问题，这个工具将可除性的乘法世界与简单的记数行为联系起来。

让我们尝试找出素数 $p=5$ 在 $100!$ 的素因子分解中的指数。这个指数被称为 $100!$ 的 ​​$p$-adic 估值​​，记作 $v_5(100!)$。一个自然的第一猜测可能是简单地计算从 1 到 100 有多少个数是 5 的倍数。这些数是 $5, 10, 15, \dots, 100$。共有 $\lfloor \frac{100}{5} \rfloor = 20$ 个这样的数。那么，答案是 20 吗？

让我们用一个更小的例子来检验这个逻辑。$v_3(9!)$ 是多少？9 以内 3 的倍数是 3、6 和 9。共有 $\lfloor \frac{9}{3} \rfloor = 3$ 个。所以，我们的猜测结果会是 3。但让我们看一下 $9!$ 的素因子分解： $9! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 = 362,880 = 2^7 \times 3^4 \times 5^1 \times 7^1$。 3 的实际指数是 4，而不是 3！我们的初步猜测是错误的。

我们推理中的缺陷是微妙但至关重要的。我们不是要计算能被 3 整除的整数的个数。我们是要计算 3 这个因子的总数。数字 3 和 6 各贡献一个因子 3。但数字 9 不同；它是 $3^2$，所以它贡献了两个因子 3。我们最初的方法只将它计算了一次。我们混淆了计算不同项目的数量与加总它们的属性。

为了修正这个问题，我们必须更加系统。对“重复计数”的恐惧是对这个概念的误用。在这里，能被素数的更高次幂整除的数必须被多次计数，因为它们贡献了多个因子。

伟大的数学家 Adrien-Marie Legendre 最早提出的正确步骤如下：

1. 首先，计算直到 $n$ 为止所有 $p$ 的倍数。有 $\lfloor n/p \rfloor$ 个。每个至少贡献一个因子 $p$。
2. 接着，计算所有 $p^2$ 的倍数。有 $\lfloor n/p^2 \rfloor$ 个。这些数每个至少贡献两个因子 $p$。由于我们在步骤 1 中已经计算了它们的第一个因子，我们现在加上这第二个贡献。
3. 然后，计算所有 $p^3$ 的倍数。有 $\lfloor n/p^3 \rfloor$ 个。我们已经计算了它们的两个因子（一个在 $p$ 的计数中，一个在 $p^2$ 的计数中），所以我们加上这第三个贡献。
4. 我们对所有小于或等于 $n$ 的 $p$ 的幂次重复这个过程。

这个过程确保了像 $p^k$ 这样的数被精确地计算了 $k$ 次——一次在 $\lfloor n/p \rfloor$ 的统计中，一次在 $\lfloor n/p^2 \rfloor$ 的统计中，...，一次在 $\lfloor n/p^k \rfloor$ 的统计中。这正确地捕捉了它所贡献的 $k$ 个因子。这导出了著名的 ​​Legendre 公式​​：

这个和在技术上是无限的，但只要 $p^k > n$，这些项就变成零。让我们再试一次我们的例子。 对于 $v_3(9!)$： $v_3(9!) = \left\lfloor \frac{9}{3} \right\rfloor + \left\lfloor \frac{9}{9} \right\rfloor + \left\lfloor \frac{9}{27} \right\rfloor + \dots = 3 + 1 + 0 = 4$ 这是正确的答案！现在，对于我们最初关于 $100!$ 末尾零的问题： $v_5(100!) = \left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{25} \right\rfloor + \left\lfloor \frac{100}{125} \right\rfloor + \dots = 20 + 4 + 0 = 24$ 对于素数 2： $v_2(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97$ 因子 $10=2 \times 5$ 的数量受限于指数较小的那个，也就是 24。所以，$100!$ 末尾正好有 24 个零。底函数中的向下取整至关重要。例如，在计算 $v_5(24!)$ 时，我们发现 $v_5(24!) = \lfloor 24/5 \rfloor = 4$。这个值一直保持在 4，直到我们达到 $n=25$ 时，它才会跳跃。

让我们将 $v_p(n!)$ 视为 $n$ 的一个函数。它的行为是怎样的？它是一个非减函数，因为随着 $n$ 的增加，我们总是在添加非负项。具体来说，从 $n-1$ 到 $n$ 的变化就是： $v_p(n!) - v_p((n-1)!) = v_p\left(\frac{n!}{(n-1)!}\right) = v_p(n)$ 这为我们描绘了一幅绝妙的函数图像。它是一个​​阶梯函数​​。它在一段时间内保持平稳，然后跳跃。它在什么时候跳跃？它恰好在 $n$ 是 $p$ 的倍数时跳跃，因为那时 $v_p(n)$ 大于 0。跳跃的高度是多少？在 $n$ 处的跳跃高度恰好是 $v_p(n)$。所以在 $n=p$ 时，它跳跃 1。在 $n=2p$ 时，它跳跃 1。但在 $n=p^2$ 时，它跳跃 2！

这种阶梯状的行为揭示了一种隐藏的节奏。函数 $v_p(n!)$ 在两个连续的 $p$ 的倍数之间的所有整数上保持不变。例如，如果我们发现 $v_p((kp)!) = m$，那么对于从 $1$ 到 $p-1$ 的所有整数 $j$，数 $kp+j$ 不能被 $p$ 整除，所以 $v_p(kp+j)=0$。这意味着阶乘的估值保持不变：$v_p((kp+j)!) = m$。这个值只会在下一个 $p$ 的倍数，即 $p(k+1)$ 处再次改变。因此，使 $v_p(n!)$ 取特定值 $m$ 的所有整数 $n$ 的集合总是一个长度为 $p$ 的区间。

你可能认为这个巧妙的计数技巧就是故事的全部了。但数学总有办法在最意想不到的地方揭示惊人的联系。事实证明，存在一个看起来完全不同的 $v_p(n!)$ 公式，它与底函数或无限和无关。相反，它与你如何用 $p$ 进制书写数字 $n$ 有关。

设 $s_p(n)$ 是 $n$ 在 $p$ 进制下的各位数字之和。例如，如果 $p=3$ 且 $n=17$，我们写 $17 = 1 \cdot 3^2 + 2 \cdot 3^1 + 2 \cdot 3^0$，所以 $17$ 在 3 进制下是 $(122)_3$。其各位数字之和是 $s_3(17) = 1+2+2=5$。$p$-adic 估值的第二个公式是：

这简直如同魔法一般。一个关于阶乘乘法结构（可除性）的问题，怎么可能通过其在不同数制下各位数字的简单加法性质来回答？让我们用 $v_3(9!)$ 来检验它。这里 $n=9, p=3$。在 3 进制下，9 是 $(100)_3$。各位数字之和是 $s_3(9) = 1+0+0=1$。该公式给出： $v_3(9!) = \frac{9 - s_3(9)}{3-1} = \frac{9-1}{2} = 4$ 它有效！对于 $v_5(100!)$，我们有 $100 = 4 \cdot 5^2 + 0 \cdot 5^1 + 0 \cdot 5^0$，所以 $100 = (400)_5$。那么 $s_5(100)=4$。该公式给出： $v_5(100!) = \frac{100 - s_5(100)}{5-1} = \frac{100-4}{4} = \frac{96}{4} = 24$ 它再次有效。这两个公式，一个涉及底函数的和，另一个涉及数字，是完全相同的。它们等价性的证明本身就是一种美；通过将 $n$ 写成其 $p$ 进制展开式并代入底函数求和公式，表达式可以通过代数方法逐项重新整理，直到它精确地变换成数字和公式。这是数字深刻、统一结构的证明。

数字和公式提供了一个新的视角。让我们回到函数视角，问问当我们从 $n$ 变为 $n+1$ 时会发生什么。估值的变化是 $v_p(n+1)$。使用数字和公式，这个变化是： $v_p((n+1)!) - v_p(n!) = \frac{(n+1) - s_p(n+1)}{p-1} - \frac{n - s_p(n)}{p-1} = \frac{1 - (s_p(n+1) - s_p(n))}{p-1}$ 所以，$v_p(n+1)$ 取决于各位数字之和的变化！是什么决定了这个变化？是在 $p$ 进制下给 $n$ 加 1 时发生的​​进位​​次数。如果 $n$ 的最后一位不是 $p-1$，加 1 只是使该位增加 1，并且 $s_p(n+1) - s_p(n) = 1$。但如果 $n$ 的最后 $t$ 位都是 $p-1$，加 1 会产生一连串 $t$ 次进位。这 $t$ 位数字变成 0，而第 $(t+1)$ 位数字加 1。这导出了一个优美的恒等式： $s_p(n+1) - s_p(n) = 1 - (p-1)t$ 其中 $t$ 是进位的次数。但 $t$ 是什么？它恰好是 $n+1$ 中因子 $p$ 的数量，即 $v_p(n+1)$！所以，$s_p(n+1) - s_p(n) = 1 - (p-1)v_p(n+1)$。将此代入我们估值变化的表达式中，得到： $\frac{1 - (1 - (p-1)v_p(n+1))}{p-1} = \frac{(p-1)v_p(n+1)}{p-1} = v_p(n+1)$ 一切都完美一致。$p$ 进制下的进位算术与阶乘的素数可除性密不可分。

一个关键问题出现了：为什么底数 $p$ 是一个素数如此特别？我们能为合数底数，比如 $b=10$，创建一个类似的公式吗？

让我们尝试模仿 Legendre 公式来计算 $v_6(10!)$。提议的公式会是 $\sum \lfloor 10/6^k \rfloor = \lfloor 10/6 \rfloor = 1$。但这是错误的。我们知道 $v_2(10!) = 8$ 和 $v_3(10!) = 4$。因为 $6=2 \times 3$，一个整数能被 6 整除，当且仅当它既能被 2 整除也能被 3 整除。在 $10!$ 中，我们有八个因子 2 和四个因子 3。我们最多可以组成四对 (2, 3)，所以我们可以组成四个因子 6。因此，$v_6(10!) = 4$。

对于合数底数，简单的计数公式之所以失败，是因为估值函数 $v_b$ 不具有可加性。对于素数 $p$，我们有基本性质 $v_p(xy) = v_p(x) + v_p(y)$，这让我们能将乘积（$n!$）的估值转化为估值的和。对于合数 $b$，这会彻底失败。例如，$v_6(2)=0$ 和 $v_6(3)=0$，但是 $v_6(2 \times 3) = v_6(6) = 1$。可加性是素数独有的特性。

要处理一个素因子分解为 $b = p_1^{e_1} p_2^{e_2} \cdots$ 的合数底数 $b$，真正的指数 $v_b(n!)$ 由“瓶颈”素数决定。对于每个素因子 $p_i$，我们有 $v_{p_i}(n!)$ 个可用因子。因为我们需要 $e_i$ 个这样的因子来构成一个 $p_i^{e_i}$，所以我们能构成的 $b$ 的数量受限于这些比率的最小值： $v_b(n!) = \min_{i} \left\lfloor \frac{v_{p_i}(n!)}{e_i} \right\rfloor$ 这突显了素数作为整数不可分割的乘法构造块的基本作用。

Legendre 公式是处理乘积 $n!$ 的强大工具。如果我们考虑一个和，比如 $n!+\ell$，会怎么样？阶乘那美丽、可预测的世界突然变得狂野得多。对于和的估值，没有简单的计数公式。其行为由估值的​​非阿基米德性质​​支配： $v_p(x+y) \ge \min\{v_p(x), v_p(y)\}$ 如果估值不同，等号成立。例如，对于 $n \ge p$，我们有 $v_p(n!) \ge 1$。对于 1 和 $p-1$ 之间的任意整数 $\ell$，我们有 $v_p(\ell)=0$。因为估值不同，我们得到 $v_p(n!+\ell) = \min\{v_p(n!), 0\} = 0$。

但如果估值相等，$v_p(x)=v_p(y)$，任何事情都可能发生！和的估值取决于首项是否在模 $p$ 意义下抵消。考虑 $p=5$ 和 $n=5$。我们有 $5! = 120$。估值是 $v_5(120) = v_5(24 \times 5) = 1$。现在让我们加上 $\ell=5$。这里，$v_5(5)=1$，所以估值相等。和是 $120+5=125=5^3$。估值跃升至 $v_5(125)=3$。与此对比，加上 $\ell=10$，其中 $v_5(10)=1$。和是 $120+10=130$，且 $v_5(130)=1$。和的估值是一件微妙的事情，对所涉及的具体数字很敏感，不像乘积那样有稳健、普适的公式。

对阶乘估值的研究，源于一个简单的问题，却引领我们对数的结构有了深刻的洞察。这个工具不仅仅是一个数学上的奇趣之物；它是解开数论和组合数学中深刻定理的钥匙，例如预测二项式系数 $\binom{n}{k}$ 被素数整除的性质。例如，使用相同的 $p$ 进制数字逻辑，可以确定 $\binom{123}{56} \equiv \binom{2}{1}\binom{3}{1}\binom{4}{0} \equiv 6 \pmod 7$，因为 $123=(234)_7$ 且 $56=(110)_7$。计算素因子的简单行为给了我们一个透镜，用以观察整数隐藏的架构。

现在我们已经熟悉了 Legendre 公式和 $p$-adic 估值的机制，你可能会问：“这一切都是为了什么？”这是一个合理的问题。一个公式，无论多么优雅，都像一把制作精美的钥匙。它的真正价值不在于其自身的形式，而在于它能打开的门。事实证明，Legendre 公式是一把万能钥匙，能打开数学殿堂中一些最迷人房间的大门。它揭示了计数、数结构、抽象代数，甚至一种奇妙的微积分形式之间的深刻联系。让我们来一次巡览。

我们在学校学到，二项式系数 $\binom{n}{k}$ 计算的是从一个 $n$ 个元素的集合中选择 $k$ 个项目的方法数。它的定义 $\frac{n!}{k!(n-k)!}$ 包含一个分数，但答案总是一个整数。为什么？你可能会说这是因为组合学的解释，这没错，但这感觉有点像魔术。我们能从分数本身，用代数方法证明它吗？

Legendre 公式为我们提供了一种直接而强大的方法。要证明 $\binom{n}{k}$ 是一个整数，我们只需证明对于任何素数 $p$，分子素因子分解中 $p$ 的总幂次（$n!$）大于或等于分母素因子分解中 $p$ 的总幂次（$k!(n-k)!$）。用我们的语言来说，这意味着我们必须证明 $v_p(\binom{n}{k}) = v_p(n!) - v_p(k!) - v_p((n-k)!)$ 总是非负的。

使用 Legendre 公式，这变成：

底函数的一个基本性质是，对于任意两个实数 $x$ 和 $y$，$\lfloor x+y \rfloor \ge \lfloor x \rfloor + \lfloor y \rfloor$。如果我们令 $x = k/p^i$ 和 $y = (n-k)/p^i$，我们会看到我们和中的每一项，$\lfloor n/p^i \rfloor - \lfloor k/p^i \rfloor - \lfloor (n-k)/p^i \rfloor$，必须是 $0$ 或 $1$。因为所有项都是非负的，它们的和 $v_p(\binom{n}{k})$ 也必须是非负的。就是这样——没有魔术，只有纯粹的算术。这个分数总是能化简成一个整数。

这仅仅是个开始。该公式不仅告诉我们估值是非负的，还告诉我们它确切是多少。这里就引出了初等数论中最优美的结果之一，Kummer 定理。它指出，$v_p(\binom{n}{k})$ 的值就是当你在 $p$ 进制下将 $k$ 和 $n-k$ 相加时执行的“进位”次数。

想一想吧！一个关于阶乘比率的素数可除性的抽象问题，竟然可以通过在不同数基下做小学算术来回答。例如，要找出整除中心二项式系数 $\binom{62}{31}$ 的 2 的幂次，你可以计算 $62!$ 和 $31!$ 的估值，或者你可以简单地在二进制下将 $31$ 与 $31$ 相加并计算进位次数。这是数论的抽象世界与计算的具体行为之间一个惊人的联系。

正如 等问题所探讨的，这种联系给了我们深刻的洞察。$\binom{n}{k}$ 何时不被 $p$ 整除？这等同于问 $v_p(\binom{n}{k}) = 0$ 何时成立。根据 Kummer 定理，这发生在 $k$ 和 $n-k$ 的 $p$ 进制加法中没有进位时。这个“无进位”条件意味着对于每个数字位， $k$ 和 $n-k$ 的数字之和必须小于 $p$。这反过来只有在对于每个数字位置 $i$，$p$ 进制数字 $k_i$ 小于或等于相应的数字 $n_i$ 时才可能。这个强大的结果是 Kummer 定理的一个推论，也是由 Lucas 定理描绘的更广阔图景的一部分，Lucas 定理比较了 $\binom{n}{k}$ 和 $\binom{n_i}{k_i}$ 的乘积在模 $p$ 意义下的值。估值告诉我们关于可除性（一个‘零’）的信息，而模算术告诉我们关于余数（一个‘数字’）的信息。

到目前为止，我们一直在看单个系数。如果我们放眼全局，看一整族系数会发生什么？对于一个固定的 $n$，当 $k$ 从 $0$ 到 $n$ 变化时，我们能对 $\binom{n}{k}$ 的可除性平均情况说些什么？这个问题将我们从数论推向了概率与统计的领域。

我们可以求 $p$-adic 估值的*期望值* $E[v_p(\binom{n}{K})]$，其中 $K$ 是从 $\{0, 1, \dots, n\}$ 中均匀选择的随机变量。使用 Legendre 公式，可以推导出这个期望的一个精确但复杂的封闭形式表达式。类似地，可以提出更结构化的问题，例如找出系数族 $\binom{p^m}{k}$ 的平均 $p$-adic 估值。能够回答这类问题表明，素数可除性的性质并非完全随机；它们遵循深刻的统计模式，而 Legendre 公式是我们揭示这些模式的工具。

$p$-adic 估值不仅仅是一个计数工具；它是一个基本的度量工具，可以定义整个代数结构。考虑所有分母不能被素数 $p$ 整除的有理数集合。这个集合记作 $\mathbb{Z}_{(p)}$，形成一种称为整数“局部化”的特殊类型的环。

值得注意的是，这个环是一个欧几里得整环，这是一种行为非常良好的代数结构，我们可以在其中使用除法算法，就像对普通整数一样。使其工作的“大小”函数是什么？它正是 $p$-adic 估值 $v_p$。在这个世界里，一个元素如果能被 $p$ 的高次幂整除，它就是“小”的。这意味着在 $\mathbb{Z}_{(p)}$ 中，理想（环中最重要的子结构）具有非常简单的形式：它们都由 $p$ 的幂生成。为一个由多个元素生成的理想找到一个生成元，就简化为找到它们 $p$-adic 估值的最小值。因此，我们的阶乘估值公式成为了导航这些抽象代数环结构的工具。

阶乘估值最深刻的应用或许是在 $p$-adic 分析领域。通过使用 $p$-adic 绝对值 $|x|_p = p^{-v_p(x)}$，我们可以对有理数进行完备化，从而构成 $p$-adic 数域 $\mathbb{Q}_p$。这是一个完备的度量空间，就像实数一样，但其几何结构很奇特。在这里，三角不等式被更强的“超度量”不等式所取代：$|x+y|_p \le \max(|x|_p, |y|_p)$。一个后果是在 $p$-adic 世界中，所有三角形都是等腰的！

在这个奇特的新世界里，我们仍然可以讨论微积分——关于由幂级数定义的函数，比如指数函数 $\exp(x) = \sum_{n=0}^\infty \frac{x^n}{n!}$。在实数中，确定收敛半径需要仔细的检验。在 $\mathbb{Q}_p$ 中，规则要简单得多：一个级数收敛当且仅当其项趋于零。

因此，为了使 $p$-adic 指数级数收敛，我们需要 $|x^n/n!|_p \to 0$ 当 $n \to \infty$。这等价于需要 $v_p(x^n/n!) \to \infty$，或者 $n v_p(x) - v_p(n!) \to \infty$。为了找到对 $v_p(x)$ 的条件，我们必须了解 $v_p(n!)$ 的增长率。这正是 Legendre 公式发挥作用的地方。该公式的一个直接推论是，对于大的 $n$，$v_p(n!) \approx \frac{n}{p-1}$。因此，$\exp(x)$ 的收敛条件变为 $v_p(x) > \frac{1}{p-1}$。

这个由 Legendre 的工作产生的不等式，带来了惊人的后果。

• 对于任何素数 $p \ge 3$，我们有 $p-1 > 1$，所以如果 $v_p(x) \ge 1$，条件 $v_p(x) > \frac{1}{p-1}$ 就满足了。这意味着对于任何是 $p$ 的倍数的 $x$，$\exp(x)$ 都收敛。
• 然而，对于 $p=2$，条件变为 $v_2(x) > \frac{1}{2-1} = 1$。由于估值必须是整数，这意味着我们需要 $v_2(x) \ge 2$。2-adic 指数函数仅对 4 的倍数收敛，而不是对所有 2 的倍数！

这个素数 2 与所有其他素数之间的微妙但关键的区别，是阶乘估值增长率的直接结果。我们简单的计数公式决定了分析学中最基本函数之一的存在域。同样的逻辑也帮助确定其他级数的收敛性，比如那些涉及估值本身幂次的级数，或者 $p$-adic 对数函数，其收敛行为是不同的，因为其分母涉及 $v_p(n)$，它比 $v_p(n!)$ 增长得慢得多。

一旦收敛性确定，我们就可以进行在现实世界中看起来毫无意义的计算，例如计算 $\exp(p)$ 模 $p^2$，并发现它是在 $\mathbb{Z}_p$ 中一个良定义的整数。

从证明一个简单的选择是整数，到定义一种新微积分的规则，Legendre 公式是一条将数学不同领域编织在一起的线。它提醒我们，有时，最深刻的洞察是通过带着执着的好奇心简单地问：“这个素数能整除那个阶乘多少次？”来找到的。答案可以，而且确实，改变了我们看待数字宇宙的方式。