不斷改進的方法

盧卡斯定理

雖然費馬小定理 (Fermat's Little Theorem) 的逆命題存在一些瑕疵,使人們以之來作素性 (Primality) 判別存在困難。但其優美的本性不會為數學家所遺棄,1876年法國數學家盧卡斯 (Edouard Lucas 1842-1891) 利用費馬小定理的逆命題,得出下列結論,我們稱為盧卡斯定理 (Lucas Theorem)。

對於自然數 n ,設 n-1 = q1u1q2u2...qtut,若有 a 使得,

an-1 = 1 (mod n) 而對於所有 i , a(n-1)/qi 不等於 1 (mod n)。則 n 為素數。

 

證:設 a 對模 n 的指數 是 e,ae = 1 (mod n)。由歐拉定理 (Euler Theorem) 中得知, e 整除 j(n),即不大於 n 且與 n 互素的整數個數。由題而知,e 整除 n-1,但不整除 (n-1)/qi ,i = 1 至 t。即 qiui 整除 e,i = 1 至 t。即 n-1 整除 e。故有 n-1 整除 j(n),即 n 是素數

 

例:判別 4093 是否素數。

取 a=2 來驗證。

答:4092 =4093-1 = (22)*(3)*(11)*(31) ,24092=1 (mod 4093),24092/2=-1 (mod 4093),24092/3=-360 (mod 4093),

24092/11=3024 (mod 4093),24092/31=1121 (mod 4093),因此 4093 是素數。

 

用盧卡斯定理來處理大數便見困難,我們雖云待判的奇數減去 1 以後,是一偶數,易於分解。但這對數百數位 、數千數位以的大數而言,卻不是那一回事。故後來出現了一些改進。

 

普羅絲定理

盧卡斯定理來處理大數分解也不盡完美,因我們未必可掌握 n-1 的所有素因子。於是普羅絲 (Proth) 把盧卡斯定理改良,而成了普羅絲定理 (Proth's Theorem)。

設 n 為奇數,若 n-1 = mq,其中 q 是一個奇素數且 2q+1 大於 n 的平方根,又若有 a 使 an-1=1(mod n) ,

但 am 不等於 1 (mod n),則 n 為素數。

 

例:判別 823001 是否素數。

答:令 n = 823001 ,n-1 = 823000 = 823*1000,a = 2。 令 m = 1000及 q = 823,則 2q+1 = 1647 > 907.19 ( n 的平方根)。

2n-1 = 1 (mod n),21000 不等於 1 (mod 823001),數值答案從略。從普羅絲定理可知 823001 是素數。

 

波克林頓定理

在1914年,波克林頓 (Pocklington) 進一步的把普羅絲的結果改進,得到下列的定理,即波克林頓定理 (Pocklington's Theorem) 。

對自然數 n ,設 n-1= F*R ,其中 F 是 n-1 的已分解部份,即已知其素因子及乘冪;R 是未分解的部份,可能是合數或素數,或已知是合數而未能分解任何因子出來,(F,R) = 1。若對 F 的每一素因子 qi,存在 ai 使

ain-1 = 1 (mod n)及 (ai(n-1)/qi-1 , n) = 1,則 n 的每一個素因子 p 都滿足 p=1 (mod F)。

再者,若奇數 n 滿足上式,且 F 大於 n 的平方根,則 n 是素數。

 

雷默與卜利爾哈特

以後,美國數學家 D.H.雷默 (Derrick Henry Lehmer 1905-1991)及其學生卜利爾哈特 (John David Brillhart, 1930- ) 等均在上式上加以改良,得到一些有用的結果。

設 n 是奇數且滿足波克林頓定理的要求,m 不少於 1,當 m > 1 時還假定 lF1 + 1不整除 n,其中 l = 1 至 m-1,如果

n < (mF1 + 1) [2F12 + (r-m)F1 + 1]

上式的 r 和 s 由 R1 和 F1 決定:

R1= 2 F1 s + r,r 介乎 1 至 2 F1 之間

則若 s = 0 或 r2 - 8s 不是一平方數,n 便是素數,反之亦然。

 

例:在 1904 年出版的一本數學難題書中問到底 1111111111111111111 ,這合共 19 個位的純元數 (Repunit) 是不是素數?

答:令 n-1 = F1 R1,其中 F1 = 3333330 = 2 * 32 * 5 * 7 * 11 * 13 * 37,R1= 2 F1 s + r,得 s = 500000, r = 3666667, r < 2 F1。計算 r2 - 8s 為 1344450488889,這是 7 的倍數,卻不是 49 的倍數,故不是平方數。取 m = 1,這時有:

(mF1 + 1) [2F12 + (r-m)F1 + 1] = 3333331 * (2*33333302 + 3666666*3333330 + 1)

= 3333331 * (103333326 * 3333330+1) = 3333331 * 34444385555581 > n。

而且 3n-1 = 1 (mod n),但 3(n-1)/2 、3(n-1)/3 、3(n-1)/5 、3(n-1)/7、3(n-1)/11 、3(n-1)/13、3(n-1)/31 均不為 1 (mod n),於是判定 n 是素數。

 

總結

以後數學家更開拓利用 n+1 或其他含 n 之多項式作判別工具,使素數判別更具效率。因其原理相當複雜,本文不加敘述。

本文列寫的方法本質是有下列兩點:

1. 從 n-1、n+1或其他含 n之多項式 入手,因其是偶合數,要分解的話比分解奇數易得多。

2. 我們不須把目標數字完全分解,也能判斷其素性。

這無疑比埃拉托斯特尼篩法 (Sieve of Eratosthenes)更具效率。