Początkowo jest ustalona i równa 4, później jest modyfikowana 3−2 = 1 raz: s ← ((4 × 4) − 2) mod 7 = 0.
Ponieważ końcowa wartość wynosi 0, wnioskujemy, że M3 jest pierwsza.
Z drugiej strony, M11 = 2047 = 23 × 89 nie jest pierwsza. Powtórnie, jest ustalona i równa 4, ale teraz jest modyfikowana 11−2 = 9 razy: s ← ((4 × 4) − 2) mod 2047 = 14 s ← ((14 × 14) − 2) mod 2047 = 194 s ← ((194 × 194) − 2) mod 2047 = 788 s ← ((788 × 788) − 2) mod 2047 = 701 s ← ((701 × 701) − 2) mod 2047 = 119 s ← ((119 × 119) − 2) mod 2047 = 1877 s ← ((1877 × 1877) − 2) mod 2047 = 240 s ← ((240 × 240) − 2) mod 2047 = 282 s ← ((282 × 282) − 2) mod 2047 = 1736
Ponieważ końcowa wartość nie jest równa 0, wnioskujemy, że M11 = 2047 nie jest pierwsza. Mimo że M11 = 2047 posiada nietrywialne czynniki, test Lucasa-Lehmera nie daje żadnych wskazówek, jakie mogą one być.
Dowód Dowód poprawności testu przedstawiany tutaj jest prostszy niż oryginalny dowód podany przez Lehmera. Przywołajmy definicję
Naszym celem jest pokazanie, że jest pierwsza wtedy i tylko wtedy, gdy
Ciąg jest dany rekurencyjnie z rozwiązaniem w jawnej postaci.