Lucas-Lehmertest voor mersennegetallen
Dit artikel gaat over de Lucas-Lehmertest voor mersennegetallen. Er is ook een algemene Lucas-Lehmertest, voor alle natuurlijke getallen.
De Lucas-Lehmertest voor mersennegetallen is een algoritme om te bepalen of het mersennegetal  ( een priemgetal) een mersennepriemgetal is. De test is ontwikkeld door Édouard Lucas en later verbeterd door Derrick Henry Lehmer.

Algoritme
Laat  een mersennegetal zijn met  een priemgetal. Definieer nu de rij  als volgt:

De eerste termen van deze rij zijn 4, 14, 194, 37634, ... Nu geldt dat  een priemgetal is dan en slechts dan als

Anders is  een samengesteld getal.

Met FFT-implementatie heeft het algoritme een looptijd van .

Voorbeeld
Als voorbeeld nemen we .

 dus 31 is een priemgetal.

Zie ook
Algemene Lucas-Lehmertest
Lucas-Lehmer-Rieseltest

Getaltheorie
Priemgetaltest