為甚麼要數因子,而不是直接相乘?
階乘增長得很快,但許多問題只問其中某個質數出現多少次。例如,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 沒有進位。