為甚麼把一個數與它的因數比較?
6 的真因數是 1,2,3,它們的和恰好是 6。28 也有這個性質:1+2+4+7+14=28。我們自然會問:能否找出所有這樣的數?與其每次單獨列出真因數,不如把數本身也加進去,定義因數和函數 σ(n)=d∣n∑d。所求條件便成為 σ(n)=2n,這更適合利用質因數分解。接下來的目標,是把這個關於加法的等式變成對質因數的限制,再證明這些限制確實足夠。
我們假定讀者熟悉唯一質因數分解,下面也會解釋 σ 的積性。
因數和與一個構造
正整數 n 的真因數是不同於 n 的正因數。若真因數之和分別等於、小於或大於 n,就稱 n 為完全數、虧數或盈數。等價地,將 σ(n) 與 2n 比較。例如 1 的真因數集合為空,空和為 0,所以 1 是虧數。
概念視角代數
完全數即因數倒數之和為二
把 n 的每個因數 d 與 n/d 配對,得
nσ(n)=d∣n∑nd=d∣n∑d1.所以 n 是完全數當且僅當 d∣n∑1/d=2;例如對 6,1+21+31+61=2。用這個形式看,n 的真倍數 N 保留每個 d∣n 的倒數 1/d,並多出 1/N,所以和嚴格增大。因此完全數或盈數的每個真倍數都是盈數;例如 σ(12)=28>24。
若 n=i∏piai,每個因數都由各質數的指數從 0 到 ai 獨立選取而唯一確定。展開相應的乘積便得到
σ(n)=i∏(1+pi+⋯+piai)=i∏pi−1piai+1−1.
這也證明了:若 gcd(a,b)=1,則 σ(ab)=σ(a)σ(b),因為兩邊選擇的質數冪互不重疊。互質條件不可省略:例如 σ(4)=7,但 σ(2)2=9。
考慮 18=2⋅32。質數冪因數互質,所以
σ(18)=(1+2)(1+3+9)=3⋅13=39>36=2⋅18.真因數之和為 39−18=21,故 18 是盈數。事實上,其真因數是 1,2,3,6,9,和確為 21。再看 16=24:σ(16)=1+2+4+8+16=31<32,故 16 是虧數。從因數和中減去數本身,可以看清為甚麼應與 2n 而非 n 比較。
候選公式是怎樣得到的?
2 的冪離目標只差一點:當 k≥1 時,
σ(2k)=2k+1−1=2⋅2k−1.
所以它的真因數之和恰好比自身少 1。若再乘一個奇質數 p,每個因數的構造就多了一個選擇:是否乘上 p。由於 p 與 2k 互質,因數和與原數的比值為
2kpσ(2kp)=(2−2k1)(1+p1).
要使這個比值等於 2,就必須有
(2k+1−1)(p+1)=2k+1p,p=2k+1−1.
因此,只要先在「2 的冪乘一個奇質數的一次冪」這種形狀中尋找,常見的公式就已經被等式確定了。接下來還有兩件事:證明奇因數為質數時這些候選數確實可行,以及證明偶完全數不可能含有更複雜的奇數部分。這正是下面定理的兩個方向。此處的計算只是說明公式為何自然,還沒有證明可以把所有可能的數限制成這種形狀。
定理 4.2.3
(歐幾里得(Euclid)的構造)
設整數 r≥2。若 q=2r−1 是質數,則 N=2r−1q 是完全數。
事實上 q 是奇數,因此 N 的兩個因數互質。於是
σ(N)=(1+2+⋯+2r−1)(1+q)=(2r−1)2r=2N.這裏既用到互質,也用到 q 是質數:若 q 是合數,則不能寫 σ(q)=1+q。
反例模式
構造需要奇因數是質數
很容易把定理讀成一條公式:凡 r≥2,2r−1(2r−1) 都是完全數。第一個合數情形已經推翻這個說法。取 r=4,候選數為 N=8⋅15=120=23⋅3⋅5,而
σ(120)=(1+2+4+8)(1+3)(1+5)=15⋅24=360=3⋅120.因數和是該數的三倍而不是兩倍,所以 120 是盈數。15 的額外因數 3 和 5 正是 σ(q)=1+q 這一步看不見的部分。修正後的命題保留「2r−1 是質數」這個假設;下一小節證明,合數值總會令候選數成為盈數。
例題 4.2.4
(由梅森(Mersenne)質數構造完全數)
取 r=5,q=31 是質數,所以 N=16⋅31=496。無須逐一列出十個因數,直接算 σ(496)=(1+2+4+8+16)(1+31)=31⋅32=992=2N。因此真因數之和為 496。
為了看清乘積究竟計算了哪些因數,可以把它們排成兩行:
1,2,4,8,16;31,62,124,248,496.第一行的奇數部分是 1,第二行的奇數部分是 31。由於 31 是質數,不會有第三種可能的奇數部分。求真因數時,只需刪去最後的 496。剩下第一行的和為 31,第二行的和為 31(1+2+4+8)=465,合起來恰好是 496。
這個描述適用於每個質數 q=2r−1。第一行是 2j,其中 0≤j≤r−1;第二行是同一指數範圍內的 q2j。由於 q>1,第一行的每項都是真因數;只有第二行的最後一項是原數自身。因此真因數之和為
q+qj=0∑r−22j=q+q(2r−1−1)=2r−1q.這就是直接從因數列表理解構造證明,也說明了質數假設用在哪裏:若奇因數是合數,它的非平凡真因數會產生額外的行,兩行的描述就漏掉了這些因數。
形如 2r−1 的數稱為梅森數;其中的質數稱為梅森質數。
若 2r−1 是質數,則 r 必須是質數。因為若 r=ab 且 a,b>1,則
2r−1=(2a−1)(1+2a+⋯+2a(b−1)).
兩因數都大於 1,所以 2a−1 是真因數。這會在指數為合數時直接給出分解,卻不是對剩餘指數的質數判定。反過來不成立:11 是質數,但 211−1=2047=23⋅89。因此只檢查指數並不足夠。
奇因數是合數時會怎樣?
事實上,合數的梅森數會使候選數成為盈數。仍令 q=2r−1、N=2r−1q,其中 r≥2。無論 q 是否為質數,2 的冪所貢獻的幾何和都是 q。若 q 是合數,它就有一個嚴格介於 1 與 q 之間的因數,故 σ(q)>q+1。於是
σ(N)=qσ(q)>q(q+1)=2N.
失敗的原因很明確:q 的額外因數使總和超過了構造所允許的大小。即使不知道這些額外因數的完整列表,也足以得到這個嚴格不等式。
取 r=6,候選數是 N=32⋅63=2016。由於 63=32⋅7,
σ(N)=63(1+3+9)(1+7)=63⋅104=6552.目標應為 2N=4032;等價地,實際的真因數之和為 6552−2016=4536>2016。63 所貢獻的因數和是 104,而質數情形的計算要求它只有 1+63=64。這解釋了為甚麼把一個合數代入公式並不能得到完全數。
為甚麼每個偶完全數都來自這個構造?
定理 4.2.7
(歐幾里得–歐拉(Euler)定理)
一個正偶整數是完全數,當且僅當它可寫為 2r−1(2r−1),其中整數 r≥2 且 2r−1 是質數。
上面的構造證明了一個方向。逆向證明不預先限制奇質因數的個數或指數,而是利用完整的因數和,證明奇數部分只能是一個質數。
先分離 2 的冪。 把偶完全數寫成 N=2km,其中 k≥1 且 m 為奇數。這裏 k=v2(N) 是 2 的確切指數:不斷除以 2,直到剩餘因數為奇數。這樣 2k 與 m 必然互質,才能對這兩個因數使用積性。令 q=2k+1−1,則 q≥3。由 σ(N)=2N,
qσ(m)=2k+1m=(q+1)m.迫使一個因數進入奇數部分。 由於 q 與 q+1 互質,歐幾里得引理給出 q∣m。這裏使用引理並不要求 q 本身是質數。也可以直接把等式改寫為 m=q(σ(m)−m),看出整除關係。寫 m=qt,其中 t≥1。代回得
σ(m)=(q+1)t=qt+t=m+t.因數和還容得下甚麼? 等式 σ(m)=m+t 意味著 m 的全部真因數之和必須等於 t。但是 t∣m,而 q>1 保證 t<m,所以 t 自己已經是真因數。若 t>1,另一個不同的真因數 1 就會使總和至少為 t+1,超過允許的值。等價地,1,t,m 是三個不同正因數,它們的和已經是 1+t+m>σ(m)。所有因數都為正數,因此再加入其他因數也無法消除矛盾。
因此 t=1,即 m=q。上式變為 σ(q)=q+1。由於 q>1,它至少有因數 1 和 q;若 q 是合數,就還有別的正因數,使和更大。所以 q 是質數。取 r=k+1 即完成逆向證明。特別地,證明也已經排除了 m=1:它已迫使 m 是 q≥3 的倍數。
證明透視
哪一步用了哪個假設
逆向證明用到三個事實,各在一處使用。第一,正是確切指數 k=v2(N) 使 2k 與 m 互質,才可以寫 σ(N)=σ(2k)σ(m)。若分解不是確切的,等式就會出錯:把 28 寫成 2⋅14,會得到 σ(2)σ(14)=3⋅24=72,但 σ(28)=56。第二,整除 q∣m 只來自 gcd(q,q+1)=1;此時對 q 是否為質數仍一無所知。
關鍵的一步是因數和的「預算」論證。寫成 m=qt 後,等式 σ(m)=m+t 把 m 全部真因數之和固定為 t,而因為 q>1,t 本身已是真因數。因數皆為正數,所以當 t>1 時,額外的因數 1 便帶來嚴格不等式。一旦 t=1,同一預算變成 σ(q)=q+1,迫使 q 為質數。因此質數性是證明的結果而不是假設,論證也毋須對 m 的奇質因數作任何分情況討論便告完成。
證明沒有預先假定奇因數是質數,而是先推出幾何和 q 整除它,再證明不能存在額外因數。這個定理分類的是偶完全數;它既沒有證明存在奇完全數,也沒有證明奇完全數不存在。這是另一問題。
假設正在研究的偶完全數滿足 v2(N)=3,即 8∣N 但 16∤N。證明迫使其奇因數為 24−1=15,又迫使 15 為質數。但 15=3⋅5,矛盾。因此不存在恰含三個因數 2 的偶完全數。這並不能排除所有被 8 整除的數;指數必須恰好為三。
為甚麼這個對應是一一的?
對梅森質數 q=2r−1,構造給出偶完全數
N=2r−1q=2q+1q.
反向操作很具體:取 N 的奇數部分,也就是除去整除 N 的最大 2 的冪。由於 q 是奇數,所得恰為 q。也可以用 v2(N)=r−1 恢復指數 r。因此不同的梅森質數不可能得到同一個 N。逆向定理又說明每個偶完全數都有這樣的原像,所以對應既是單射也是滿射。
例如 28=22⋅7 的奇數部分是 7=23−1,故它來自 q=7 和 r=3,不存在第二個指數選擇。只有已知偶數是完全數時才能這樣恢復:例如 24 的奇數部分是 3,但與 3 對應的完全數是 6,不是 24。
常見誤區
指數為質數是梅森數為質數的必要條件,卻不是充分條件。反過來,一個梅森數是合數,只能排除與該指數對應的偶完全數,本身不能排除其他指數或奇完全數。此外,σ 的值在不互質的參數上不能隨意相乘,這樣可能會重複計數;應改用質數冪公式。定理在梅森質數與偶完全數之間建立一一對應,但沒有證明它們有無窮多個。
寫出 m=qt 後,也許會想把 σ(m) 換成 σ(q)σ(t)。但沒有任何一步證明 q 與 t 互質。例如取 q=t=3,則 σ(9)=13,而 σ(3)σ(3)=16。這個例子只是說明錯誤的乘法,並不是在提出一個完全數候選。逆向證明避開了這一問題:它只用到 t 整除 m,以及取出若干正因數所得到的和不超過總因數和。每當改變分解方式,都應重新檢查所用定理的假設。
練習
計算因數和,判斷 15 和 120 是虧數、完全數還是盈數。
解答 · 答案
σ(15)=(1+3)(1+5)=24<30,故 15 是虧數;σ(120)=(1+2+4+8)(1+3)(1+5)=360>240,故 120 是盈數。
用定理求 r=7 對應的偶完全數,並驗證所需的質數性。
解答 · 答案
27−1=127。合數必有不超過其平方根的質因數:把它寫成兩個大於 1 的因數之積,較小因數不超過平方根,而且這個因數又有質因數。這裏 127<12,故只需檢查質數 2,3,5,7,11。由奇偶性、各位數字和及末位可排除前三者;另外 127=7⋅18+1=11⋅11+6。因此 127 是質數,答案為 26⋅127=8128。
解答 · 答案
此時 k=11,逆向結論要求 q=212−1=4095 為質數。但 4095=3⋅1365,因此不存在這樣的偶完全數。
有人說 r=11 是質數,故 211−1 也是質數。指出錯誤並給出分解。
解答 · 答案
正確的推論方向是:2r−1 為質數,才可推出 r 為質數。逆命題不成立,因為 2047=23⋅89。
求出所有小於 1000 的偶完全數。說明為甚麼只需檢查少數幾個指數;僅列出幾個例子不能證明答案完整。
解答 · 答案
每個偶完全數都可寫成 N=2r−1(2r−1),其中 r≥2。由於 2r−1≥2r−1,所以 N≥22r−2。若 r≥6,此下界至少為 1024,已經超過範圍。因此只需檢查 r=2,3,4,5,所得奇因數依次為 3,7,15,31。第一、第二、第四個是質數:對於 31,因其平方根小於 6,只需檢查質數 2,3,5;更小的情形可直接判斷。15 是合數。所以完整列表為 6,28,496。逆向定理結合大小界保證沒有遺漏,而正向構造保證列出的三個數確實完全。
有人說,由於 24−1=15 是合數,不存在被 8 整除的偶完全數。說明錯誤並給出反例。
解答 · 答案
合數 15 只排除 v2(N)=3,並不排除所有 v2(N)≥3 的情形。完全數 496=24⋅31 被 8 整除,且 v2(496)=4。它的奇因數是另一個梅森數 25−1=31。說 8∣N,並不等於說 8 是整除 N 的最大 2 的冪。