盧卡斯-萊默檢驗

盧卡斯-萊默檢驗是一種高效的確定性 素性檢驗，用於確定 梅森數 是否為素數。由於已知梅森數只有在素數下標時才可能是素數，因此可以將注意力限制為形如 的梅森數，其中 是一個 奇素數。

考慮以下遞推方程

(1)

其中 。例如，忽略同餘，此迭代的前幾個項為 4, 14, 194, 37634, 1416317954, ... (OEIS A003010)。

結果表明， 是素數 當且僅當 ，且值 稱為 的盧卡斯-萊默剩餘。

例如，對於 獲得的序列為 4, 14, 67, 42, 111, 0，因此 是素數。

對於素數 ，前幾個盧卡斯-萊默剩餘為 1, 0, 0, 0, 1736, 0, 0, 0, 6107895, 458738443, 0, 117093979072, ... (OEIS A095847)。

此檢驗也可以擴充套件到任意 整數。在普拉特 (1975) 的工作之前，盧卡斯-萊默檢驗一直被純粹視為一種啟發式方法，在很多時候都有效 (Knuth 1969)。普拉特 (1975) 表明，透過將萊默的素性啟發式方法遞迴地應用於 的因子，可以使之成為一種非確定性程式，從而產生一種素性證明，即後來的 普拉特證書。

盧卡斯-萊默檢驗的廣義版本允許

(2)

其中 是不同的 素因子， 是它們各自的 冪。如果存在一個 盧卡斯序列 使得

(3)

對於 , ..., 並且

(4)

那麼 是一個 素數。這簡化為 梅森數 的傳統盧卡斯-萊默檢驗。