盧卡斯定理

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

對於自然數 n ，設 n-1 = q₁^u1q₂^u2...q_t^ut，若有 a 使得，

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

　

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

　

例：判別 4093 是否素數。

取 a=2 來驗證。

答：4092 =4093-1 = (2²)*(3)*(11)*(31) ，2⁴⁰⁹²=1 (mod 4093)，2^4092/2=-1 (mod 4093)，2^4092/3=-360 (mod 4093)，

2^4092/11=3024 (mod 4093)，2^4092/31=1121 (mod 4093)，因此 4093 是素數。

　

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

　

普羅絲定理

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

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

但 a^m 不等於 1 (mod n)，則 n 為素數。

　

例：判別 823001 是否素數。

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

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

　

波克林頓定理

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

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

a_i^n-1 = 1 (mod n)及 (a_i^(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 時還假定 lF₁ + 1不整除 n，其中 l = 1 至 m-1，如果

n < (mF₁ + 1) [2F₁² + (r-m)F₁ + 1]

上式的 r 和 s 由 R₁ 和 F₁ 決定：

R₁= 2 F₁ s + r，r 介乎 1 至 2 F₁ 之間

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

　

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

答：令 n-1 = F₁ R₁，其中 F₁ = 3333330 = 2 * 3² * 5 * 7 * 11 * 13 * 37，R₁= 2 F₁ s + r，得 s = 500000， r = 3666667， r < 2 F₁。計算 r² - 8s 為 1344450488889，這是 7 的倍數，卻不是 49 的倍數，故不是平方數。取 m = 1，這時有：

(mF₁ + 1) [2F₁² + (r-m)F₁ + 1] = 3333331 * (2*3333330² + 3666666*3333330 + 1)

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

而且 3^n-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)更具效率。