为什么要数因子,而不是直接相乘?
阶乘增长得很快,但许多问题只问其中某个素数出现多少次。例如,100! 末尾有多少个零,只取决于它有多少个因子十,而不需要算出它的全部数位。素数赋值把庞大的乘法换成有限个整数商的和,也让我们从另一个进位制的普通加法看出二项式系数的整除性。
以下 p 表示素数;当 n≥1 时,n!=1⋅2⋯n,并定义 0!=1。对正整数 N,vp(N) 是 N 的唯一素因数分解中 p 的指数,特别是 vp(1)=0。对整数 a≥0,pa∣N 恰好等价于 a≤vp(N),而且 vp(AB)=vp(A)+vp(B)。对商使用赋值相减时,我们先确认这个商是整数。
逐层数倍数
对每个整数 n≥0,
vp(n!)=j≥1∑⌊pjn⌋.此和是有限的:一旦 pj>n,相应的项便为零。
在 1,…,n 中,每个 p 的倍数至少贡献一个因子 p,这样的数有 ⌊n/p⌋ 个。每个 p2 的倍数再额外贡献一个因子,依此类推。如果一个数能被 pr 整除,却不能被 pr+1 整除,它便恰好被数了 r 次。把 n! 各因子的贡献加起来,就得到公式。只数 p 的倍数会漏掉 p2,p3,… 所含的额外因子。
正整数 N 的十进制末尾零的个数是 min(v2(N),v5(N)):每去掉一个末尾零,就去掉一个因子 10=2⋅5;较小的指数用尽后,商便不能再被十整除。对 100!,
v5(100!)=20+4=24,v2(100!)=50+25+12+6+3+1=97.所以 100! 末尾恰有 24 个零。对一般的 N 必须取两者的较小值;例如 N=5 虽有因子五,末尾却没有零。
求最大的 e,使 12e∣30!。由 12=22⋅3,公式给出 v2(30!)=15+7+3+1=26 和 v3(30!)=10+3+1=14。两个要求分别是 2e≤26 和 e≤14,故 e=13。一般地,若 b=i∏piai>1,最大指数是 imin⌊vpi(n!)/ai⌋。决定答案的素数不一定是 b 的最大素因子。
数位记录了同一个计数
把 n 的 p 进制展开写成 n=i≥0∑dipi,其中 0≤di<p,而且只有有限个数位非零。设 sp(n)=i∑di。将展开式代入阶乘公式,交换有限求和次序,得到
vp(n!)=i≥1∑di(1+p+⋯+pi−1)=p−1n−sp(n).
第一个等号按每个数位 di 分别计算它在 p,…,pi 各层的贡献。公式同时证明 n−sp(n) 可被 p−1 整除;这里不需要对分数作近似取整。
若 0≤k≤n,二项式系数 (kn)=n!/(k!(n−k)!) 是整数,因为它计算 n 元集合的 k 元子集个数。因此
vp(kn)=p−1sp(k)+sp(n−k)−sp(n).
这个等式把整除性连接到 k 与 n−k 在 p 进制相加时的进位。
设 p 是素数,0≤k≤n 为整数。vp(kn) 等于 k 与 n−k 在 p 进制相加时的进位次数;每一个向下一高位送出进位的数位列各计一次。特别地,p 整除 (kn) 恰好等价于至少发生一次进位。
设第 i 列的两个输入数位为 ai,bi,输出数位为 di,进入该列的进位为 ci,其中 c0=0。若 ci 是零或一,则 ai+bi+ci≤2p−1,所以送出的进位 ci+1 也是零或一。由 c0=0 开始归纳,可知这对每一列都成立,而且
ai+bi+ci=di+pci+1.在高位加入足够多个零列,使最后没有进位。把各列等式不带位值地相加,便得到 sp(k)+sp(n−k)−sp(n)=(p−1)i≥1∑ci。结合上面的数位和公式,即证定理。一连串进位中,每个送出进位的列都各算一次;不能把整串只算一次。
证明透视
两种不同的计数
阶乘公式数的是乘积中素数幂的倍数;进位定理数的是加法各列之间的转移。两者相等由数位和恒等式导出,并不需要把每个倍数与每次进位一一配对。
取 n=10、k=3。二进制下 3=00112,7=01112,它们的和为 10102。第一、二、三列各送出一次进位,所以 v2(310)=3。确实 (310)=120=23⋅15。进入第四列的进位形成最高位,但第四列本身没有再送出进位。
三进制中,2=023 与 3=103 相加没有进位,和为 5=123。因此 3∤(25)=10。这本身没有排除其他素数:2 和 5 都整除 10。
求整除 (516) 的二的确切次方。要相加的数是 5 和 16−5=11,二进制分别为 001012 和 010112。由个位开始,各列依次为 1+1=2、0+1+1=2、1+0+1=2 和 0+1+1=2,每列都送出进位。第五列接收最后的进位并输出 1,但没有再送出进位。结果是 100002=16,四次送出进位给出
v2(516)=4.这是确切的指数,因此该系数可被 16 整除,却不能被 32 整除。独立验算得 (516)=4368=16⋅273,而 273 是奇数。若把最后的最高位也算作一次进位,就会高估指数。
从无进位得到逐位判据
进位定理不只能检验一个系数,还能在不计算整行系数的情况下,找出哪些不被指定素数整除。把 n 和 k 写成 p 进制:
n=i∑nipi,k=i∑kipi,
位数不够时在前面补零。
设 0≤k≤n,数位记号如上。下面三句话等价:
- p∤(kn);
- k 与 n−k 相加时没有进位;
- 每一位都满足 ki≤ni。
前两句的等价性正是进位定理。若相加时没有进位,每列的输出位就是两个输入位之和,因而至少是 ki,得到第三句。反过来,若每一位都满足 ki≤ni,令 mi=ni−ki。每个 mi 都是合法的 p 进制数位,且 m=i∑mipi 满足 k+m=n。逐列有 ki+mi=ni<p,因此这次相加没有进位。又因为 m=n−k,它恰好是定理要求的加法。这个论证也包括零位和前导零,不必预先依赖借位减法。
概念视角代数
由多项式恒等式得到逐位判据
模 p 时 (1+x)p≡1+xp,因为 0<j<p 时 p 整除 (jp)。对每一位应用这一点,得到
(1+x)n≡i∏(1+xpi)ni(modp).由于每个 ki≤ni<p,每个幂 xk 至多由一种数位选择产生,所以 (kn)≡i∏(kini)(modp);当 ki>ni 时相应因子为零。非零因子都不被 p 整除,因此既恢复了判据,也给出系数模 p 的余数。
取 n=13=11012、p=2。允许的 k 只能在 11012 为 1 的位置取 1,所以
k∈{0,1,4,5,8,9,12,13}.第 13 行恰有这八个奇数系数。例如 k=5 时,01012+10002=11012 没有进位,实际 (513)=1287 也是奇数。相反,k=2=00102 在二位使用了 n 的零位;2 与 11 相加产生一次进位,故 v2(213)=1,确实 (213)=78。逐位判据失败只保证至少一个因子 p;要知道确切指数,仍须数出所有向外送出的进位。
现在不逐个列出,而直接计数。第 i 位的 ki 可以独立取 0 到 ni,共有 ni+1 个选择;非零数位只有有限个。因此
#{k:0≤k≤n, p∤(kn)}=i∏(ni+1).
这个乘积包含两个端点系数。13 的二进制有三个 1 位,所以共有 23=8 个选择,包括 k=0 和 k=13。这是下标的个数,并不是某个系数的数值,也没有给出该系数模 p 的具体余数。
因为 23=2123,三位分别有 3、2、3 个选择,所以 24 个系数 (k23) 中恰有 18 个不被 3 整除。例如 k=5=0123、23−5=18=2003,相加无进位。若 k=6=0203,它的三位数码 2 超过 23 同一位的数码 1。事实上 23−6=17=1223,相加 0203+1223=2123 恰送出一次进位,所以该系数能被 3 整除,却不能被 9 整除。
用对称性检查列表
因为 (kn)=(n−kn),不被整除的下标列表必须关于 k↦n−k 对称。逐位判据把这一点显示出来:无进位时,配对下标的每一位为 ni−ki,也都允许。因此第 13 行中 0 与 13、1 与 12、4 与 9、5 与 8 分别成对。这是检查手算列表的方法,不应再把配对数加到乘积上重复计数。
当 n=2m>0 且 p=2 时,可能的不动下标 k=m 不在列表中:在 m+m 中,m 的二进制最低一个 1 与另一个 1 相加必送出进位,故 (m2m) 为偶数。n=0 时唯一系数 (00)=1 不属于这个正行号的结论。使用对称性时单独检查不动点,可避免未经论证就把总数除以二。
何时所有内部项都含有因子 p
计数公式还能区分素数幂与其他行号。
定理 1.3.12
(内部系数全被 p 整除的行)
设 n≥1。所有内部系数 (kn)(即 0<k<n)都被 p 整除,当且仅当 n 是 p 的幂,允许 p0=1。特别地,n=1 没有内部系数,因此对内部系数的断言空真。
证明时注意端点下标 0 与 n 不同,两个系数都是 1。所以所有内部系数都被 p 整除,当且仅当乘积 i∏(ni+1) 等于 2。每个因子都是正整数,乘积为 2 便要求恰有一个因子为 2,其余都为 1。换句话说,n 恰有一个数位为 1,其余数位均为 0;这正是 n=pa。此论证同时给出反方向;只检验已知为素数幂的行,不能证明反方向。
例如 9=1003 只有两个端点系数不被 3 整除;但 12=1103 有四个允许下标:0、3、9、12。其中 k=3 和 k=9 的内部系数都是 220,不被 3 整除。因此,行号本身能被 p 整除还不够。当 n=0 时只有一个端点下标;此时应单独看 (00)=1,不能照搬两个端点的计数。
常见错误
反例模式
逐层计数公式需要素数
命题:对任意整数 b>1,b 在 n! 中的指数是 j≥1∑⌊n/bj⌋。取 b=4、n=8,这个和是 ⌊8/4⌋+⌊8/16⌋=2。但 8!=40320=43⋅630,而 630 不被 4 整除,所以整除 8! 的 4 的最高次幂是 43。这个和只看到 4 的倍数;2 和 6 中各一个因子 2,加上 8=4⋅2 中多出的因子 2,合起来又组成一个因子 4。修正方法是先把 b 分解为素数:此处 ⌊v2(8!)/2⌋=⌊7/2⌋=3。
阶乘的商要先证明是整数,才能自动把它的素数赋值视为非负整数。
常见错误
(把 n 与 k 相加,而不是 k 与 n−k)
进位定理使用的是 k 和 n−k 的加法,不是 n 和 k 的加法。它计算素因子的重数:两次进位证明可被 p2 整除,而不只证明可被 p 整除。
在 (516) 中,001012+010112=100002 共送出四次进位;第五列只接收一次进位并输出最高位的 1,自己没有送出进位。若把这个最高位也算作第五次进位,便会声称 32∣(516),但 4368/32=136.5 不是整数。
总结
检验单个系数是否被 p 整除,可以逐位比较 k 与 n;要求确切指数,则数 k+(n−k) 的进位。要数整行中不被 p 整除的系数,就把每一位允许的选择数相乘。这些方法都要求 p 是素数,计数时也包括两个端点。
练习
快速检查
(求最大的整数 e,使 18e 整除 25!。)
解答 · 答案
由 18=2⋅32,v2(25!)=12+6+3+1=22,v3(25!)=8+2=10。因此 e≤22 且 2e≤10,最大值为 5。
快速检查
(用进位及另一个独立计算,求 (412) 中 3 的确切指数。)
解答 · 答案
三进制中 4=0113、8=0223,它们的和 12=1103 在个位及三位各送出一次进位,所以指数是 2。独立计算得 v3(12!)=4+1=5、v3(4!)=1、v3(8!)=2,相减为 5−1−2=2。确实 (412)=495=9⋅55。
快速检查
(证明素数 p 整除每个二项式系数 (kp),其中 0<k<p。)
解答 · 答案
当 0<k<p 时,k! 和 (p−k)! 都没有因子 p,但 p! 恰有一个。因此 vp(kp)=1。在 k=0 和 k=p 时,系数为 1,所以严格不等式不可省略。
快速检查
(先用进位,再用阶乘赋值,求 (820) 中 3 的确切指数。)
以三进制把八和十二相加;区分进入一列的进位与该列新送出的进位。
解答 · 答案
在三进制下,8=0223,12=1103。个位 2+0=2 没有进位;三位 2+1=3 送出一次进位;九位 0+1+1=2 没有再送出进位。因此 0223+1103=2023=20,故 v3(820)=1。独立计算得 v3(20!)=6+2=8、v3(8!)=2、v3(12!)=4+1=5,所以指数为 8−2−5=1。最后一列接收的进位是已经数过的那一次,不是第二次送出进位。
快速检查
(对任意非负整数 n 和素数 p,解释为何进位定理给出 (0n) 和 (nn) 的赋值都是零。)
把一个 p 进制展开式与零相加,会发生什么事?
解答 · 答案
当 k=0 时,加法是 0+n=n;当 k=n 时,加法是 n+0=n。两种情况中,每列都有一个加数的数位是零,也没有从前一列收到进位,因此不会送出进位。定理给出的赋值是零,正如 (0n)=(nn)=1 所要求的。这也包括 n=0:唯一的系数是 1,而加法 0+0=0 没有进位。