Hvis man ikke finder nogen divisorer, må man lave en Lucas-Lehmer test. Sætning 4.1 siger at tallet er et primtal hvis det går op i .
Vi skal altså finde ud af om . Men hvis vi bare begynder at regne ud, får vi hurtigt nogle meget store tal ( ), hvilket vi ikke er interesseret i, da disse er langsomme at arbejde med.5.1
Derfor regner vi modulus , sådan at vi efter hvert trin reducerer modulus . Det kan vi gøre, fordi hvis
(5.1) | ||
så har vi ifølge sætning 2.5 at
| ||
(5.2) | ||
og vi kan så trække 2 fra på begge sider
| ||
(5.3) |
Hvis vi efter sidste trin får resten 0, ved vi at er et primtal. Vi demonstrere det ved at vise at virkeligt er et primtal. Processen skal så igennem trin. Ved hvert trin bruger man resten fra sidste trin, kvadrerer den og trækker 2 fra, og finder en ny rest:
0 |