沒人會用的判別法

 

英國數學家華林 (Edward Waring 1736 - 1798)

(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )

 

威爾遜定理

其實喜愛數學真的不會分職業的,約翰.威爾遜 (John Wilson 1741-1793) 爵士本身是一英國法官。原來其發現了數論中一個極為稀罕的關係,連逆定理也成立。有位外國數論專家曾說過:如果一個人不知道威爾遜定理 (Wilson's Theorem) ,那他就白學了數論。

但威爾遜並沒有對此發現大重視,若不是其朋友英國數學家華林 (Edward Waring 1736 - 1798),劍橋大學 (University of Cambridge) 的數學教授發表了他的研究結果,那麼又是一條費馬大定理 (Fermat's Last Theorem) ,十之八九被人遺忘,或在其子女替他整理遺物在被公開。

但是威爾遜爵士也好,好友華林也好,甚至是微積分共同發明人德國數學家萊布尼茨 (Gottfried Wilhelm von Leibniz 1646-1716),他比威爾遜更早知到這關係,同樣沒法驗證其發現。1770年華林在其代數學的著作中發表了威爾遜的發現,1771年法國數學家拉格朗日 (Joseph-Louis Lagrange 1736-1813) 便給出證明,正是萊布尼茨發表後一百年。其實說正確的應是「萊布尼茨定理」、「拉格朗日定理」而非「威爾遜定理」,但事情卻是這樣發生了,歷史便是這樣的了。現在亦有人稱這定理為威爾遜 - 拉格朗日定理 (Wilson -  Lagrange Theorem)。

 

下文便是解釋威爾遜爵士的發現:

取得從 1 到某素數的所有連續正整數的乘積,如取 1 * 2 * 3 * ...... * 11 ,記作 11! ( 11 的階乘 Factorial) 。顯然易見,11! 是可被 1 至 11 整除。現在我們看看 10! ,因 11 是素數,這數當然不會是 11 的倍數 ,如果是 10!+1 又怎樣? 看看 6! + 1 = 1 * 2 * 3 * 4 * 5 * 6 + 1 = 721 正是 7的倍數;4! + 1 = 1 * 2 * 3 * 4 + 1 = 25 正是 5 的倍數:原來這一性質只合用於素數,合數 則不可。

用數學的說法是:任一數 n ,若 (n-1)!+1=0 (mod n) 即 (n-1)!+1 是 n 的倍數,則 n 為素數。反之,定某素數 p ,(p-1)!+1 = 0 (mod p) 必成立,即 (p-1)!+1 是 p 的倍數。

 

這定理證明倒不太困難,但我只證其中一個方向:

我們看到若取 p=2, (2-1)! + 1 = 1! + 1 = 2,正是 2 的倍數。

現考慮奇素數 p,看看 (p-1)!,即 1 * 2 * 3 * ... * (p-1),由於若 p 為素數則 1 至 (p-1) 均於 p 互素 (Coprime)。是故對於當中每一個數 a (a 介乎 1 與 p-1 之間),必然存在一個 b (b 亦介乎 1 與 p-1 之間) 使 a*b = 1 (mod p),這個 b 是唯一的。(若 p 不是素數,對於某些與 p 不互素的數 a,則不存在對應的 b。)

然而,我們不排除一個可能性 a 與 b 為同一個數,即 a = b 或 a2 = 1 (mod p)。

換句話來說, p 整除 a2 - 1 = (a-1) * (a+1),由於 p 為素數,即 p 整除 (a-1) 或 (a+1),即 a = 1 或 (p-1) (mod p)。

所以在 1 至 (p-1) 當中除 1 和 (p-1)外,其餘的皆成雙成對,在模 p 下乘積為 1,故 (p-1)! + 1 = 1 * 1 * (p-1) + 1 = p-1 + 1 = p = 0 (mod p)。

這樣便證明到定理的一個方向。而另一方句的證明,則留給各位讀者細嘗了。

 

威爾遜商

或考慮 W(p) = [(p-1)! + 1] / p ,這稱為威爾遜商 (Wilson Quotient)。若某數的威爾遜商為整數,即該數為 1 或素數。

下表列出威爾遜定理的一些測試結果:

n   (n-1)! (n-1)!+1
[(n-1)!+1] 除以 n 的餘數
素性
2
1!=
1
2
0
素數
3
2!=
2
3
0
素數
4
3!=
6
7
1
合數
5
4!=
24
25
0
素數
6
5!=
120
121
1
合數
7
6!=
720
721
0
素數
8
7!=
5040
5041
1
合數
9
8!=
40320
40321
1
合數
10
9!=
362880
362881
1
合數
11
10!=
3628800
3628801
0
素數
12
11!=
39916800
39916801
1
合數
13
12!=
479001600
479001601
0
素數
14
13!=
6227020800
6227020801
1
合數
15
14!=
87178291200
871278291201
1
合數

大家可知要判斷 15 的素性 (Primality),先要弄到 14! 。若要判斷 101 的素性,要討取 100! ,可不易事。若要判斷更大的素數,工作量也是級數般上升。這一發現是重要,但卻沒有人會用這一素數的判別法吧。

 

一道公式

順便一言, 有沒有真的素數公式?即代入任何數字也可得出素數答案的公式?那當然是有的,但卻有點取巧。

其中,

只要 x  和 y  均取正值,答案必為素數,網友可自行驗算。

 

原因若何?原來這正和威爾遜定理相關。

由於大部份情況下, ,所以答案只會是 2 ;或當 時的

故上公式只會在特定的情況給出奇素數,即取 x 為威爾遜商的情況。

 

參考文獻及網址

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 61, 1987.

Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 142-143 and 168-169, 1996.

Weisstein, E. W. "Prime-Generating Polynomial." From MathWorld http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html.

Weisstein, E. W. "Wilson Quotient." From MathWorld. http://mathworld.wolfram.com/WilsonQuotient.html.

Weisstein, E. W. "Wilson's Theorem." From MathWorld. http://mathworld.wolfram.com/WilsonsTheorem.html.

馮克勤, 由整數談起, 長沙:湖南教育出版社, 頁 67, 1998