在这个专题中，我们将探讨整除、素数、同余等数论问题，这是讨论整数性质的重要数学分支。

参考资料：《具体数学 第 2 2 2 版》

现在来讨论某种很有意思的高度复合而成的数 —— 阶乘的因子分解： n ! = 1 × 2 × ⋯ × n = Π k = 1 n k ，整数 n ≥ 0 \begin{equation} n! = 1 \times 2 \times \cdots \times n = \Pi_{k = 1}^{n} k，整数 n \ge 0 \end{equation} n!=1×2×⋯×n=Πk=1n​k，整数n≥0​​按照我们对于空的乘积的约定，这就定义了 0 ! 0! 0! 是 1 1 1。从而对每个正整数 n n n 有 n ! = ( n − 1 ) ! n n! = (n - 1)!n n!=(n−1)!n。这是 n n n 个不同物体的排列的个数。也就是说，它是将 n n n 件物品排成一行的方法数：对第一件物品有 n n n 种选择；对第一件物品的每一种选择，对第二件物品都有 n − 1 n - 1 n−1 种选择；对这 n ( n − 1 ) n(n - 1) n(n−1) 种选择的每一选择，对第三件物品都有 n − 2 n - 2 n−2 种选择；如此等等，总共给出 n ( n − 1 ) ( n − 2 ) ⋯ ( 1 ) n(n - 1)(n - 2) \cdots (1) n(n−1)(n−2)⋯(1) 种排列方式。下面是阶乘函数的前几个数值。

一个有意思的事实是，当 n ≥ 25 n \ge 25 n≥25 时， n ! n! n! 中的数字的个数超过 n n n。那么阶乘到底以什么方式增长呢？我们给出如下证明。 n ! 2 = ( 1 × 2 × ⋯ × n ) ( n × ⋯ × 2 × 1 ) = Π k = 1 n k ( n + 1 − k ) n!^2 = (1 \times 2 \times \cdots \times n)(n \times \cdots \times 2 \times 1) = \Pi_{k = 1}^n k(n + 1 - k) n!2=(1×2×⋯×n)(n×⋯×2×1)=Πk=1n​k(n+1−k)由于二次多项式 k ( n + 1 − k ) = 1 4 ( n + 1 ) 2 − ( k − 1 2 ( n + 1 ) ) 2 k(n + 1 - k) = \frac{1}{4}(n + 1)^2 - \big( k - \frac{1}{2}(n + 1) \big)^2 k(n+1−k)=41​(n+1)2−(k−21​(n+1))2 在 k = 1 k = 1 k=1 以及 k = n k = n k=n 时取到最小值 n n n，在 k = 1 2 ( n + 1 ) k = \frac{1}{2}(n + 1) k=21​(n+1) 时取到最大值 1 4 ( n + 1 ) 2 \frac{1}{4}(n + 1)^2 41​(n+1)2，于是我们有 n ≤ k ( n + 1 − k ) ≤ 1 4 ( n + 1 ) 2 n \le k (n + 1 - k) \le \frac{1}{4}(n + 1)^2 n≤k(n+1−k)≤41​(n+1)2，则 Π k = 1 n n ≤ n ! 2 ≤ Π k = 1 n ( n + 1 ) 2 4 \Pi_{k = 1}^n n \le n!^2 \le \Pi_{k = 1}^n \frac{(n + 1)^2}{4} Πk=1n​n≤n!2≤Πk=1n​4(n+1)2​这就是 n n / 2 ≤ n ! ≤ ( n + 1 ) n 2 n \begin{equation} n^{n / 2} \le n! \le \frac{(n + 1)^n}{2^n} \end{equation} nn/2≤n!≤2n(n+1)n​​​这个关系式告诉我们，阶乘函数以指数方式增长！！

对于很大的 n n n，为了更加精确地近似 n ! n! n!，我们可以利用斯特林公式（将在专题九中推导）： n ! ∼ 2 π n ( n e ) n \begin{equation} n! \sim \sqrt{2 \pi n} \big(\frac{n}{e} \big)^n \end{equation} n!∼2πn ​(en​)n​​斯特林公式与 n ! n! n! 的渐近相对误差大概是 1 / ( 12 n ) 1 / (12n) 1/(12n)，即便是对于比较小的 n n n，这个近似值也是非常好的。

对任何给定的素数 p p p，我们希望确定能整除 n ! n! n! 的 p p p 的最大幂，也就是说，我们要求 p p p 在 n ! n! n! 的唯一分解式中的指数。我们用 ε p ( n ! ) \varepsilon_p(n!) εp​(n!) 来记这个数，从小的情形 p = 2 p = 2 p=2 和 n = 10 n = 10 n=10 开始研究。 10 ! 10! 10! 是 10 10 10 个数的乘积， ε 2 ( 10 ! ) \varepsilon_2(10!) ε2​(10!) 可以通过将这 10 10 10 个数对 2 2 2 的幂的贡献求和来得到，这一计算对应于如下表格中各个列的求和：

按列求的和有时称为直尺函数（ ruler function \text{ruler function} ruler function） ρ ( k ) \rho(k) ρ(k)，因为它们与直尺类似。这 10 10 10 个和式的和是 8 8 8，从而 2 8 2^8 28 是能够整除 10 ! 10! 10! 的 2 2 2 的最大幂。

还有另外一种方法：我们可以对每一行的贡献求和。第一行记录了对 2 2 2 的幂的贡献，这样的贡献有 ⌊ 10 / 5 ⌋ = 5 \lfloor 10 / 5 \rfloor = 5 ⌊10/5⌋=5 个。第二行记录了对 2 2 2 的增加一次幂的贡献，这有 ⌊ 10 / 4 ⌋ = 2 \lfloor 10 / 4 \rfloor = 2 ⌊10/4⌋=2 个。而第三行记录了对 2 2 2 的再增加一次幂的贡献，这有 ⌊ 10 / 8 ⌋ = 1 \lfloor 10 / 8 \rfloor = 1 ⌊10/8⌋=1 个。这些就计入了所有的贡献，所以我们有 ε 2 ( 10 ! ) = 5 + 2 + 1 = 8 \varepsilon_2(10!) = 5 + 2 + 1 = 8 ε2​(10!)=5+2+1=8。

对一般的 n n n，这个方法给出 ε 2 ( n ! ) = ⌊ n 2 ⌋ + ⌊ n 4 ⌋ + ⌊ n 8 ⌋ + ⋯ = ∑ k ≥ 1 ⌊ n 2 k ⌋ \varepsilon_2(n!) = \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor + \lfloor \frac{n}{8} \rfloor + \cdots = \sum_{k \ge 1}\lfloor \frac{n}{2^k} \rfloor ε2​(n!)=⌊2n​⌋+⌊4n​⌋+⌊8n​⌋+⋯=k≥1∑​⌊2kn​⌋这个和式实际上是有限的，因为当 2 k > n 2^k > n 2k>n 时求和项都是零。因此它只有 ⌊ lg ⁡ n ⌋ \lfloor \lg n \rfloor ⌊lgn⌋ 个非零的项，而这是相当容易计算的。例如，当 n = 100 n = 100 n=100 时有 ε 2 ( 100 ! ) = 50 + 25 + 12 + 6 + 3 + 1 = 97 \varepsilon_2(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97 ε2​(100!)=50+25+12+6+3+1=97。每一项都正好是前一项的一半的底。这对所有 n n n 都是正确的，因为作为专题三第 1 1 1 篇文章中公式 ( 11 ) (11) (11) 的一个特例，我们有 ⌊ n / 2 k + 1 ⌋ = ⌊ ⌊ n / 2 k ⌋ / 2 ⌋ \lfloor n / 2^{k + 1} \rfloor = \lfloor \lfloor n / 2^k \rfloor / 2 \rfloor ⌊n/2k+1⌋=⌊⌊n/2k⌋/2⌋。当我们用二进制写出这些数时，容易发现我们仅仅从一项的二进制表示中去掉了最低有效位就得到了下一项。 100 = ( 1100100 ) 2 = 100 ⌊ 100 / 2 ⌋ = ( 110010 ) 2 = 50 ⌊ 100 / 4 ⌋ = ( 11001 ) 2 = 25 ⌊ 100 / 8 ⌋ = ( 1100 ) 2 = 12 ⌊ 100 / 16 ⌋ = ( 110 ) 2 = 6 ⌊ 100 / 32 ⌋ = ( 11 ) 2 = 3 ⌊ 100 / 64 ⌋ = ( 1 ) 2 = 1 \begin{matrix} 100= & (1100100)_2 = & 100 \\ \lfloor 100 / 2 \rfloor = & (110010)_2 = & 50 \\ \lfloor 100 / 4 \rfloor = & (11001)_2 = & 25 \\ \lfloor 100 / 8 \rfloor = & (1100)_2 = & 12 \\ \lfloor 100 / 16 \rfloor = & (110)_2 = & 6 \\ \lfloor 100 / 32 \rfloor = & (11)_2 = & 3 \\ \lfloor 100 / 64 \rfloor = & (1)_2 = & 1 \end{matrix} 100=⌊100/2⌋=⌊100/4⌋=⌊100/8⌋=⌊100/16⌋=⌊100/32⌋=⌊100/64⌋=​(1100100)2​=(110010)2​=(11001)2​=(1100)2​=(110)2​=(11)2​=(1)2​=​100502512631​二进制表示也指出了怎样推导出另外的公式 ε 2 ( n ! ) = n − ν 2 ( n ) \begin{equation} \varepsilon_2(n!) = n - \nu_2(n) \end{equation} ε2​(n!)=n−ν2​(n)​​其中 ν 2 ( n ) \nu_2(n) ν2​(n) 是 n n n 的二进制表示中 1 1 1 的个数。这是因为对 n n n 的值贡献 2 m 2^m 2m 的每一个 1 1 1，都对 ε 2 ( n ! ) \varepsilon_2(n!) ε2​(n!) 贡献 2 m − 1 + 2 m − 2 + ⋯ + 2 0 = 2 m − 1 2^{m - 1} + 2^{m - 2} + \cdots + 2^0 = 2^m - 1 2m−1+2m−2+⋯+20=2m−1。

将我们的发现推广到任意的素数 p p p，就有 ε p ( n ! ) = ⌊ n p ⌋ + ⌊ n p 2 ⌋ + ⌊ n p 3 ⌋ + ⋯ = ∑ k ≥ 1 ⌊ n p k ⌋ \begin{equation} \varepsilon_p(n!) = \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor + \cdots = \sum_{k \ge 1} \lfloor \frac{n}{p^k} \rfloor \end{equation} εp​(n!)=⌊pn​⌋+⌊p2n​⌋+⌊p3n​⌋+⋯=k≥1∑​⌊pkn​⌋​​ ε p ( n ! ) \varepsilon_p(n!) εp​(n!) 有多大呢？从求和项中直接去掉底，然后对无穷几何级数求和，我们得到一个简单然而很好的上界： ε p ( n ! ) < n p + n p + n p + ⋯ = n p ( 1 + 1 p + 1 p 2 + ⋯ ) = n p ( p p − 1 ) = n p − 1 \begin{aligned} \varepsilon_p(n!) &< \frac{n}{p} + \frac{n}{p} + \frac{n}{p} + \cdots \\ &= \frac{n}{p} \big(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots \big) \\ &= \frac{n}{p}\big( \frac{p}{p - 1} \big) \\ &= \frac{n}{p - 1} \end{aligned} εp​(n!)​ 1 n>1 就会有 n ! < ( 2 n ) k = 2 n k n! < (2^n)^k = 2^{nk} n!