動機
把模 7 的所有非零剩餘相乘,得到 6!=720,而 720=7⋅102+6。因此乘積的餘數是 6,也就是 −1 所代表的剩餘類。模 13 時也一樣:12!=479001600=13⋅36846276+12。但模 9 時,8!=40320=9⋅4480 的餘數卻是 0。
本節解釋這些結果。關鍵在於結構:在每個元素都有逆元的乘法系統中,我們可以把所有元素的乘積重新分組成逆元對,每一對的乘積都是 1。留下來的只有自身就是逆元的元素。因此問題歸結為找出 x2=1 的解。這些解是否只有 ±1,取決於模 n 算術能否消去因子;這正是質數與合數出現差異的地方。
以下 n≥2 均為整數。模 n 的運算在 Z/nZ 中進行;它是交換環,但未必是域。我們以 a≡b(modn) 表示兩個剩餘類相等。當我們說某個整數的剩餘「是」6 之類的數,指的是它的最小非負剩餘:滿足 0≤r≤n−1 且 r≡a(modn) 的唯一整數 r。因此 720 是整數,6 是它模 7 的最小非負剩餘,而 −1 代表同一個剩餘類。這些是不同的對象,不應混淆。
定義
剩餘類 a∈Z/nZ 稱為單位,如果存在 b 使得 ab≡1(modn)。這樣的 b 稱為 a 的逆元。所有單位在乘法下構成的集合記為 (Z/nZ)×,或 U(n);它是一個有限阿貝爾(Abel)群。剩餘類 a 是單位,當且僅當 gcd(a,n)=1。
逆元是唯一的。若 ab≡1 且 ab′≡1,則 b≡b(ab′)≡(ba)b′≡b′。正是這個唯一性使「把每個元素與其逆元配對」有明確意義。
若單位 a 滿足 a2≡1(modn),則稱它為自逆元素。若非零剩餘類 a 存在非零剩餘類 c 使得 ac≡0(modn),則稱 a 為零因子。
若 p 是質數,則 Z/pZ 沒有零因子。這由歐幾里得(Euclid)引理得出:若 p∣xy,則 p∣x 或 p∣y。而且,對 gcd(a,p)=1 應用貝祖(Bézout)等式,可知模 p 的每個非零剩餘類都是單位。相比之下,模 8 時 2⋅4≡0,因此 2 和 4 都是零因子。
一般配對原理
設 G 是以乘法表示的有限阿貝爾群。則 G 中所有元素的乘積,等於其中所有自逆元素的乘積。
映射 g↦g−1 是 G 上的一個雙射,而且它自身就是自己的逆映射。因此 G 分拆成互不相交、形如 {g,g−1} 的類。當 g=g−1 時,一類有兩個元素;當 g2=1 時,一類只有一個元素。
由於 G 是阿貝爾群,我們可以按任意次序計算全體元素的乘積,因此可逐類分組。每個雙元素類貢獻 g⋅g−1=1;每個單元素類貢獻它唯一的自逆元素。故全體元素的乘積等於所有自逆元素的乘積。
這裏本質上用到了交換性:沒有交換性,便不能任意重排因子。
把原理應用於 G=U(n),可見計算 a∈U(n)∏a 的問題歸結為研究 x2≡1(modn) 的解。原理本身並沒有說明解有多少個;那是關於 n 的算術問題。
設 p 是質數。x2≡1(modp) 的解恰為 x≡1 和 x≡−1。當 p=2 時,兩者相同,故只有一個解;當 p 為奇數時,兩者不同,故恰有兩個解。
若 x2≡1,則 (x−1)(x+1)≡0(modp)。由於 Z/pZ 沒有零因子,其中一個因子必為零,所以 x≡1 或 x≡−1。這兩個值也確實滿足方程。
現在比較兩個根。1≡−1(modp) 當且僅當 p∣2,亦即 p=2。所以 p=2 時唯一的根是 1;p 為奇數時,根 1 和 p−1 不同。
威爾遜定理
對整數 n≥2,
n 是素數⟺(n−1)!≡−1(modn).
設 n=p 是質數。此時 U(p)={1,2,…,p−1},故 (p−1)! 是 U(p) 中所有元素的乘積。
由配對原理,這個乘積等於所有自逆元素的乘積,而這些元素正是 x2≡1 的根。
- 若 p 為奇數,根是 1 和 −1,其乘積為 −1,所以 (p−1)!≡−1。
- 若 p=2,唯一的根是 1,所以 (p−1)!=1!=1,而 1≡−1(mod2)。
兩種情況都得到 (p−1)!≡−1(modp)。
假設 n 是合數,則它有因數 d 滿足 1<d<n。由於 d≤n−1,整數 d 是 (n−1)! 的一個因子,所以 d∣(n−1)!。
反設 (n−1)!≡−1(modn)。由於 d∣n,模 n 同餘蘊含模 d 同餘,故 (n−1)!≡−1(modd)。但 (n−1)!≡0(modd),因此 0≡−1(modd),即 d∣1,這與 d>1 矛盾。
證明透視
威爾遜定理兩個方向各自用了甚麼
兩個方向依賴不同的事實。正向把質數性用了兩次。第一,每個剩餘 1,…,p−1 都是單位,所以 (p−1)! 恰好是 U(p) 所有元素的乘積,配對原理才適用。第二,沒有零因子,自逆元便只有 1 和 −1,剩下的乘積是 1⋅(−1)=−1;當 p=2 時,唯一剩下的 1 恰好等於 −1。缺少任何一個事實,結論都會改變。對 n=15,四個單位 1,4,11,14 都是自逆元,所有單位之積為 1,正如例題所算。此外 14! 還含有非單位 3,5,6,9,10,12,事實上 14!≡0(mod15)。
逆向完全不用群論。它唯一的一步是:n 的真因數 d 是 (n−1)! 的一個因子;把假設的同餘式化為模 d,便得 0≡−1。換言之,當 n 是合數時,階乘與 n 有公因子 d,所以它模 n 不是單位,而 −1 是單位。這解釋了為何逆向一行便可完成,也解釋了為何下一個定理能準確求出合數情形的剩餘。
逆向證明只需要一個非平凡真因數,完全不必使用單位群。我們還可以得到更精確的結果。
若 n 是合數且 n>4,則 (n−1)!≡0(modn)。若 n=4,則 (n−1)!=6≡2(mod4)。
當 n=4 時,直接計算:3!=6=4+2。
現在設 n>4 是合數。令 q 為其最小質因數,寫成 n=q⋅r,其中 r=n/q。則 r≥q≥2。
情況一:r=q。 此時 q<r,且兩者都嚴格介乎 1 與 n 之間。它們是 {1,…,n−1} 中兩個不同整數,故作為不同因子出現在 (n−1)! 中。因此 qr=n 整除 (n−1)!。
情況二:r=q,即 n=q2。 我們不能把 q 用兩次,因為它在 1,…,n−1 中只出現一次。由於 n>4,有 q≥3,因此 2q<q⋅q=n。所以 q 和 2q 是 {1,…,n−1} 中兩個不同整數。其乘積 2q2=2n 整除 (n−1)!,故 n∣(n−1)!。
n=4 正是此方法失效的情況:q=2 時 2q=4=n,並不小於 n。
證明透視
為何質數平方需要第二個倍數
目標是把 n 或 n 的某個倍數寫成 1,…,n−1 中若干個不同整數的乘積,因為每個這樣的整數在 (n−1)! 中只出現一次。當 n=qr 且 q=r 時,這兩個因子本身已經做到。取 q 為最小質因子只是把它們排好次序,q≤r,於是 r=q 已經意味著 q<r。真正的困難是質數平方 n=q2,這時因子 q 只能用一次。證明以 2q 代替第二個 q。它是另一個小於 n 的因子,當且僅當 2q<q2,即 q≥3;而乘積 q⋅2q=2n 是 n 的倍數。
假設 n>4 只在這裏用到:形如 q2 且 q=2 的合數只有 4。這個界限是準確的,因為 3!=6≡2(mod4)。相比之下,8=2⋅4 不是平方數,屬於第一種情況,用到的是兩個不同因子 2 和 4。
因此對每個 n≥2,(n−1)! 的剩餘在 n 是質數時為 −1,在 n=4 時為 2,其餘情況則為 0。
這是特徵刻畫,不是實用算法
威爾遜定理給出精確的質數判定法,但它並不高效。算術複雜度以輸入長度 k≈log2n 的函數來量度位元運算次數。直接計算 (n−1)!modn 約需 n−2 次乘法。每一步取模後,按普通筆算方法,相乘兩個 k 位元數至多需要 O(k2) 次位元運算。所得上界為 O(nk2);單是這 n−2 次逐一的乘法,已使此直接方法的步數隨 k 指數增長。若不取模,整數 (n−1)! 本身約有 nlog2n 個位元,單是寫下它也需要隨 k 指數增長的空間。
對一個 2048 位元的 n,單是步數已約為 22048。因此威爾遜定理是質數的一個結構性刻畫,對證明很有價值,卻不是實用的質數檢驗。
半階乘與負一的平方根
設 p 是奇質數,m=(p−1)/2。則
(m!)2≡(−1)m+1(modp).
剩餘類 1,…,p−1 分拆為 {j,p−j} 這些對,其中 1≤j≤m,且 p−j≡−j。因此
(p−1)!=j=1∏mj(p−j)≡j=1∏m(−j2)=(−1)m(m!)2(modp).由威爾遜定理,−1≡(−1)m(m!)2。兩邊乘以 (−1)m,並利用 (−1)2m=1,便得到 (m!)2≡(−1)m+1。
這個結果說的是 (m!)2,不是 m! 本身。當 p≡1(mod4) 時,m 是偶數,且 (m!)2≡−1。所以 m! 給出 −1 的一個具體平方根;當 p≥5 時,它既不是 1,也不是 −1。當 p≡3(mod4) 時,m 是奇數,故 (m!)2≡1,而 m!≡±1。兩個符號都確實會出現。例如 3!=6≡−1(mod7),但 11!=39916800=23⋅1735513+1,所以 11!≡1(mod23)。
為了證明當 p≡3(mod4) 時,−1 沒有平方根,我們先證明費馬(Fermat)小定理,而不將它當作已知結果。
若 p 是質數且 p∤a,則 ap−1≡1(modp)。
考慮 U(p) 上的映射 x↦ax。它把單位映為單位,並且是單射:若 ax≡ay,則乘以 a−1 可得 x≡y。有限集合到自身的單射也是雙射,所以此映射將 U(p) 的元素重新排列。
因此兩個乘積相等:
x=1∏p−1(ax)≡x=1∏p−1x,即ap−1(p−1)!≡(p−1)!(modp).(p−1)! 是單位的乘積,故本身也是單位,可以消去。於是得到 ap−1≡1。這裏不需要使用威爾遜定理。
設 p 是奇質數。若 p≡1(mod4),則 x=((p−1)/2)! 滿足 x2≡−1。若 p≡3(mod4),同餘式 x2≡−1(modp) 無解。
第一個結論是半階乘平方定理在 m 為偶數時的結果。
至於第二個結論,假設 x2≡−1。則 x≡0,所以可以應用費馬定理。由於 m 為奇數,我們得到 1≡xp−1=(x2)m≡(−1)m=−1。因此 1≡−1,即 p∣2;但 p 是奇數,這不可能。
合數模數:更多 1 的平方根
對合數 n,配對原理仍然適用於 U(n),失效的是依賴域的論證。模 8 時,四個單位 1,3,5,7 都是自逆的:32=9、52=25 和 72=49 都 ≡1(mod8)。U(12)={1,5,7,11} 的情況也一樣。在 U(24) 中,八個單位 1,5,7,11,13,17,19,23 都是自逆的;例如 52=25、112=121=5⋅24+1,以及 132=169=7⋅24+1。另須注意,當 n 是合數時,U(n) 中所有單位的乘積與 (n−1)! 是不同的量,因為 (n−1)! 包含非單位。
例題
例題 2.2.10
(p=7 時的威爾遜定理)
模 7 的逆元對為 2⋅4=8≡1 及 3⋅5=15≡1。自逆元素是 1 和 6,所以
6!≡1⋅6⋅(2⋅4)(3⋅5)≡6≡−1(mod7).這與整數計算 720=7⋅102+6 一致。
例題 2.2.11
(p=13 時的威爾遜定理及 −1 的平方根)
逆元對為:
2⋅7=14,3⋅9=27,4⋅10=40,5⋅8=40,6⋅11=66.它們各自都 ≡1(mod13),因為 14=13+1、27=26+1、40=39+1 和 66=65+1。連同自逆元素 1 和 12,可得 12!≡12≡−1,與動機部分得到的餘數 12 一致。
這裏 m=6,而 6!=720=13⋅55+5,所以 6!≡5。接著 52=25=26−1≡−1。因此 5 以及 13−5=8 都是模 13 的 −1 的平方根。
例題 2.2.12
(合數模數 n=4,9,15)
當 n=4:3!=6≡2(mod4)。剩餘既不是 0,也不是 −1≡3,因此 n=4 是例外。
當 n=9=32:平方數的情況使用 8! 中兩個不同因子 3 和 6。它們的乘積是 18=2⋅9,所以 9∣8!。事實上 40320=9⋅4480。
當 n=15=3⋅5:兩個不同因子 3 和 5 都出現在 14! 中,所以 14!≡0(mod15)。
例題 2.2.13
(模 15 時額外的 1 的平方根)
我們有 U(15)={1,2,4,7,8,11,13,14}。平方可得:
- 42=16≡1
- 112=121=8⋅15+1
- 142≡(−1)2=1
因此有四個自逆單位:1,4,11,14。其餘單位可配成 2⋅8=16≡1 及 7⋅13=91=6⋅15+1。
由配對原理,所有單位的乘積為
1⋅4⋅11⋅14=616=41⋅15+1≡1(mod15).結果是 1,而非 −1。
常見錯誤
反例模式
在有零因子時錯誤消去
錯誤說法。「由 (x−1)(x+1)≡0(modn) 可得 x≡±1。」
錯在何處。 沒有零因子的論證在整環中有效;在有零因子的環中,一般不能使用這個論證。模 15 取 x=4,則 (x−1)(x+1)=3⋅5=15≡0,但 4≡±1。模 8 取 x=3,則 2⋅4≡0。兩個非零剩餘類的乘積可以為零,所以兩個因子都不一定為零。
修正。 當 n 是質數時,這個推論成立,因為 Z/pZ 沒有零因子。對合數 n,必須用別的方法求 x2≡1 的根,例如分別在每個質數冪因子的模下求解,再把結果組合起來。
其餘兩個誤區與消去無關,而是關乎所計算的對象:是半階乘還是它的平方,是整數還是它的剩餘類。
反例模式
假設半階乘總是 $\pm1$
錯誤說法。「模 p 的半階乘 m! 總是 ±1。」
錯在何處。 模 13 時,我們算得 6!≡5,它既不是 1,也不是 12。總是等於 ±1 的只是 (m!)2。
錯誤說法。「既然 6!≡−1(mod7),便有 6!=−1。」
錯在何處。 整數 6! 等於 720。剩餘 6,或等價地 −1,只描述它模 7 的剩餘類。
習題
快速檢查
(設 p=5。計算 m! 並驗證 (m!)2≡(−1)m+1(mod5)。)
先計算 m=(p−1)/2。
解答 · 答案
這裏 m=2,且 2!=2,因此 22=4≡−1(mod5)。由於 m+1=3,預測的值是 (−1)3=−1,與計算一致。因為 5≡1(mod4),剩餘類 2 是 −1 的平方根;3 也是,因為 32=9≡−1。
快速檢查
(利用逆元配對驗證 p=11 時的威爾遜定理,然後計算 5!mod11。)
求出模 11 下由 2 至 9 每個剩餘的逆元。
解答
模 11 的逆元對為:
2⋅6=12,3⋅4=12,5⋅9=45,7⋅8=56.它們各自都 ≡1(mod11),因為 12=11+1、45=44+1 和 56=55+1。連同自逆元素 1 和 10,得到 10!≡10≡−1。
至於半階乘,m=5 且 5!=120=110+10,所以 5!≡−1。這與 (m!)2≡(−1)6=1 一致。這裏 m! 恰好是 −1;當 p=23 時它則是 +1。
快速檢查
(利用分類中平方數的情況,證明 24!≡0(mod25),並指出所用的兩個因子。)
使用 n=q2 且 q≥3 的情況。
解答
25=52,而最小質因數為 5≥3。因子 5 和 10 不同,且都小於 25,所以都出現在 24! 中。它們的乘積是 50=2⋅25,故 25∣24!,即 24!≡0(mod25)。
單用因子 5 並不足夠,因為它在 1,…,24 中只出現一次。
快速檢查
(計算 U(8) 中所有元素的乘積,並解釋為何它不是 −1。)
解答
U(8)={1,3,5,7},每個元素都是自逆的。乘積是 1⋅3⋅5⋅7=105=13⋅8+1≡1(mod8)。
質數情況的論證在這裏失效,因為 x2≡1 有四個根,而非兩個。另一方面,7!=5040=8⋅630≡0,正如分類結果所預測。
快速檢查
(解釋為何威爾遜定理需要約定 n≥2。)
解答 · 答案
當 n=1 時,任意兩個整數模 1 都同餘。因此 0!=1≡−1(mod1) 成立,但 1 並非質數。環 Z/1Z 是零環,其中 1=0。正向論證所需的條件(1=−1 或 p=2)及「質數」的概念均不適用於此。排除 n=1 才能保持等價命題成立。
快速檢查
(用排列論證證明費馬小定理,檢查邊界情況 p=2,並解釋為何證明 −1 沒有平方根的論證需要 p 為奇數。)
先證明乘以 a 在 U(p) 上是單射。
解答
一般證明。 設 p∤a。由於可用 a−1 消去,x↦ax 是 U(p) 上的單射,因此它是 U(p) 的一個排列。令兩邊乘積相等,得到 ap−1(p−1)!≡(p−1)!;消去單位 (p−1)!,便得 ap−1≡1。
邊界情況 p=2。 此時 U(2)={1},該排列是恆等映射;對奇數 a 有 a1≡1。定理仍然成立。
為何無根論證需要 p 為奇數。 該論證推出 1≡−1 並視之為矛盾。然而模 2 時 1≡−1 是成立的,而且 12≡−1(mod2)。所以 −1 確實有模 2 的平方根,矛盾也就不存在。
快速檢查
(從半階乘找出模 13 的 −1 的一個平方根,再找出所有平方根。)
先計算 6! 模 13,再利用 13 是質數。
解答
這裏 m=6,且 6!=720=13⋅55+5≡5。因此 52=25≡−1。
若 y2≡−1≡52,則 (y−5)(y+5)≡0。由於 13 是質數,沒有零因子,所以 y≡5 或 y≡8。檢查:82=64=65−1≡−1。因此模 13 的 −1 的平方根恰為 5 和 8。