Тест Люка — Лемера — ефективний тест простоти для чисел Мерсенна. Завдяки цьому тесту найбільшими відомими простими числами завжди були прості числа Мерсенна, причому навіть до появи комп'ютерів^[1].

Тест був запропонований французьким математиком Люка 1878 року і доповнений американським математиком Лемером^[en] 1930 року. Отриманий тест носить ім'я двох вчених, які спільно відкрили його, навіть не зустрічаючись за життя. 1952 року Робінсон за підтримки Лемера провів обчислення на комп'ютері SWAC з використанням тесту Люка — Лемера, результатом якого стало відкриття простих чисел ${\displaystyle M_{521))$ і ${\displaystyle M_{607))$. Пізніше того ж року були відкриті ${\displaystyle M_{1279))$, ${\displaystyle M_{2203))$ і ${\displaystyle M_{2281))$^[1].

Тест Люка — Лемера базується на тому спостереженні, що простота числа Мерсенна ${\displaystyle M_{q}=2^{q}-1}$ тягне простоту числа ${\displaystyle q}$, і в наступному твердженні:

Для встановлення простоти ${\displaystyle M_{p))$ послідовність чисел ${\displaystyle L_{0},L_{2},\ldots ,L_{q-2))$ обчислюється по модулю числа ${\displaystyle M_{q))$ (тобто обчислюються не власне числа ${\displaystyle L_{k))$, довжина яких росте експоненціально, а остачі від ділення ${\displaystyle L_{k))$ на ${\displaystyle M_{q))$, довжина яких обмежена p бітами). Останнє число в цій послідовності ${\displaystyle L_{q-2}{\bmod {M))_{q))$ називається вирахуванням Люка — Лемера. Таким чином, число Мерсенна ${\displaystyle M_{q))$ є простим тоді і тільки тоді, коли число ${\displaystyle q}$ просте, і вирахування Люка — Лемера дорівнює нулю.

Можливими значеннями ${\displaystyle L_{0))$ є: 4, 10, 52, 724, 970, 10084, …

Обчислювальна складність тесту для числа ${\displaystyle M_{q}=2^{q}-1}$ дорівнює ${\displaystyle O(q^{3})}$^[2], оскільки в процесі тесту виконується ${\displaystyle O(q)}$ піднесення до квадрату та вирахувань по модулю ${\displaystyle M_{q))$. Довжина ${\displaystyle M_{q))$ становить ${\displaystyle q}$ біт, причому найпростіший алгоритм множення чисел має складність ${\displaystyle O(q^{2})}$. Для прискорення тесту слід використовувати алгоритми швидкого множення великих цілих чисел, наприклад, алгоритм Шьонхаге — Штрассена. Складність тесту в такому випадку становитиме ${\displaystyle O(q^{2}\log {q}\log {\log {q)))}$.

Розглянемо виконання тесту для числа Мерсенна ${\displaystyle M_{13}=8191}$.

${\displaystyle L_{0}=4}$

${\displaystyle L_{1}=4^{2}-2\mod {8191}=14}$

${\displaystyle L_{2}=14^{2}-2\mod {8191}=194}$

${\displaystyle L_{3}=194^{2}-2\mod {8191}=4870}$

${\displaystyle L_{4}=4870^{2}-2\mod {8191}=3953}$

${\displaystyle L_{5}=3953^{2}-2\mod {8191}=5970}$

${\displaystyle L_{6}=5970^{2}-2\mod {8191}=1857}$

${\displaystyle L_{7}=1857^{2}-2\mod {8191}=36}$

${\displaystyle L_{8}=36^{2}-2\mod {8191}=1294}$

${\displaystyle L_{9}=1294^{2}-2\mod {8191}=3470}$

${\displaystyle L_{10}=3470^{2}-2\mod {8191}=128}$

${\displaystyle L_{11}=128^{2}-2\mod {8191}=0}$

Отже, число ${\displaystyle M_{13}=8191}$ — просте.

Теорема: Нехай ${\displaystyle q}$ — просте число, причому ${\displaystyle q\geqslant {3))$. Визначимо послідовність ${\displaystyle L_{n))$ таким чином:

${\displaystyle L_{0}=4,}$

${\displaystyle L_{n+1}=({L_{n))^{2}-2)\mod (2^{q}-1).}$

Тоді ${\displaystyle 2^{q}-1}$ — просте тоді і тільки тоді, коли ${\displaystyle L_{q-2}=0}$.

Доведення теореми засновано на властивостях послідовностей Люка ${\displaystyle U_{n}=U_{n}(4,1)}$ і ${\displaystyle V_{n}=V_{n}(4,1)}$:

${\displaystyle U_{0}=0,U_{1}=1,U_{n+1}=4U_{n}-U_{n-1))$

${\displaystyle V_{0}=2,V_{1}=4,V_{n+1}=4V_{n}-V_{n-1))$

Такі властивості доводяться по індукції:

${\displaystyle V_{n}=U_{n+1}-U_{n-1))$

${\displaystyle U_{n}={\tfrac {1}{\sqrt {12))}((2+{\sqrt {3)))^{n}-(2-{\sqrt {3)))^{n})}$

${\displaystyle V_{n}=(2+{\sqrt {3)))^{n}+(2-{\sqrt {3)))^{n))$

${\displaystyle U_{m+n}=U_{m}U_{n+1}-U_{m-1}U_{n))$

Лема: Нехай ${\displaystyle p}$ — просте і ${\displaystyle e\geqslant 1}$, тоді справедливе наступне твердження. Якщо ${\displaystyle U_{n}\equiv 0{\pmod {p^{e))))$, то ${\displaystyle U_{np}\equiv 0{\pmod {p^{e+1))))$.

Доказ леми: Покладемо ${\displaystyle U_{n}=bp^{e))$, ${\displaystyle U_{n+1}=a}$. Використовуємо вище описані властивості, щоб отримати значення для ${\displaystyle U_{2n))$ і ${\displaystyle U_{2n+1))$:

${\displaystyle U_{2n}=bp^{e}(2a-4bp^{e})\equiv 2aU_{n}{\pmod {p^{e+1))))$, в той час як ${\displaystyle U_{2n+1}=U_{n+1}^{2}-U_{n}^{2}\equiv {a}^{2}{\pmod {p^{e+1))))$.

Тим же способом отримаємо:

${\displaystyle U_{3n}=U_{2n+1}U_{n}-U_{2n}U_{n-1}\equiv (3a^{2})U_{n}{\pmod {p^{e+1))))$ і ${\displaystyle U_{3n+1}=U_{2n+1}U_{n+1}-U_{2n}U_{n}\equiv {a}^{3}{\pmod {p^{e+1))}.}$

Інакше кажучи,

${\displaystyle U_{kn}\equiv (ka^{k-1})U_{n}{\pmod {p^{e+1))))$ і ${\displaystyle U_{kn+1}\equiv {a^{k)){\pmod {p^{e+1))))$,

звідки випливає твердження леми, якщо взяти ${\displaystyle k=p}$.

Далі, розкривається вираз послідовностей за формулою біному Ньютона:

${\displaystyle U_{n}=\sum _{k}{\binom {n}{2k+1))2^{n-2k-1}3^{k},}$

${\displaystyle V_{n}=\sum _{k}{\binom {n}{2k))2^{n-2k+1}3^{k}.}$

Тепер, якщо ми покладемо ${\displaystyle n=p}$, де ${\displaystyle p}$ — просте число, більше 2, і врахуємо, що ${\displaystyle {\tbinom {n}{k))}$ кратне ${\displaystyle p}$ за винятком тих випадків, коли ${\displaystyle k=0}$ і ${\displaystyle k=n}$, ми отримаємо:

${\displaystyle U_{p}\equiv 3^{(p-1)/2}{\pmod {p))}$, ${\displaystyle V_{p}\equiv 4{\pmod {p))}$.

Якщо ${\displaystyle p\neq 3}$ теорема Ферма стверджує, що ${\displaystyle 3^{p-1}\equiv 1{\pmod {p))}$. Тому ${\displaystyle (3^{(p-1)/2}-1)(3^{(p-1)/2}+1)\equiv 0{\pmod {p))}$, тобто ${\displaystyle 3^{(p-1)/2}\equiv \pm 1{\pmod {p))}$. Якщо ${\displaystyle U_{p}\equiv {-1}{\pmod {p))}$, то

${\displaystyle U_{p+1}=4U_{p}-U_{p-1}=4U_{p}+V_{p}-U_{p+1}\equiv {-U_{p+1)){\pmod {p)),}$

тобто ${\displaystyle U_{p+1}=0{\pmod {p))}$. У той же спосіб отримується результат, що ${\displaystyle U_{p-1}=0{\pmod {p))}$, якщо ${\displaystyle U_{p}=1}$. Отже доведено, що для будь-якого простого числа, існує ціле число ${\displaystyle \mid \varepsilon (p)\mid \leqslant 1}$ таке, що ${\displaystyle U_{p+\varepsilon (p)}=0{\pmod {p))}$.

Лема: Якщо ${\displaystyle N}$ — додатне ціле число, і ${\displaystyle m=m(N)}$ — найменше число таке, що ${\displaystyle U_{m(N)}\equiv 0{\pmod {N))}$, то ми маємо:

${\displaystyle U_{n}\equiv 0{\pmod {N))}$ тоді і тільки тоді, коли ${\displaystyle n}$ кратне ${\displaystyle m(N)}$.

Доведення: Зауважимо, що послідовність ${\displaystyle U_{n},U_{n+1},U_{n+2},...}$ збігається з послідовністю ${\displaystyle aU_{0},aU_{1},aU_{2},...}$ по модулю ${\displaystyle M}$, де число ${\displaystyle a=U_{m+1}\mod N}$ взаємно просте з ${\displaystyle N}$, так як: ${\displaystyle \gcd {(U_{n},U_{n+1})}=1}$.

Доведення теореми: По індукції маємо

${\displaystyle L_{n}=V_{2^{n))\mod (2^{q}-1)}$.

Більш того, з ${\displaystyle 2U_{n+1}=4U_{n}+V_{n))$ слідує, що ${\displaystyle \gcd {(U_{n},V_{n})}\leqslant 2}$. Звідси слід, що ${\displaystyle U_{n))$ і ${\displaystyle V_{n))$ не мають загальних непарних дільників. Якщо ${\displaystyle L_{q-2}=0}$, то для ${\displaystyle U_{2^{q-1))}$ і ${\displaystyle U_{2^{q-2))}$ можна записати:

${\displaystyle U_{2^{q-1))=U_{2^{q-2))V_{2^{q-2))\equiv 0{\pmod {2^{q}-1))}$

${\displaystyle U_{2^{q-2))\not \equiv 0{\pmod {2^{q}-1))}$

Тепер, якщо ${\displaystyle m=m(2^{q}-1)}$, то ${\displaystyle m}$ повинно бути дільником числа ${\displaystyle 2^{q-2))$, але не повинно ділити ${\displaystyle 2^{q-2))$, тому ${\displaystyle m=2^{q-1))$. Доведемо, що ${\displaystyle n=2^{q}-1}$. Нехай ${\displaystyle n={p_{1))_{1}^{e}...{p_{r))_{r}^{e))$. Числа ${\displaystyle p_{j))$ більше 3, так як ${\displaystyle n}$ непарне і виконується ${\displaystyle n=2^{q}-1\equiv (-1)^{q}-1=-2{\pmod {3))}$, ${\displaystyle q}$ — просте за умовою. Використовуючи раніше доведені леми, отримаємо ${\displaystyle U_{t}\equiv 0{\pmod {2^{q}-1))}$, де

${\displaystyle t=\mathrm {lcm} ({p_{1))^{e_{1}-1}(p_{1}+\varepsilon _{1}),\dots ,{p_{r))^{e_{r}-1}(p_{r}+\varepsilon _{r}))}$

де ${\displaystyle \varepsilon _{j}=\pm 1}$. Звідси випливає, що ${\displaystyle t}$ кратне ${\displaystyle m=2^{q}-1}$. Покладемо ${\displaystyle n_{0}=\prod _{j=1}^{r}{p_{j))^{e_{j}-1}(p_{j}+\varepsilon _{j})}$; ${\displaystyle n_{0}\leqslant \prod _{j=1}^{r}{p_{j))^{e_{j}-1}(p_{j}+1/5p_{j})=(6/5)^{r}n}$. Так як ${\displaystyle p_{j}+\varepsilon _{j))$ — парне, ${\displaystyle t\leqslant {n_{0))/2^{r-1))$. Використовуємо раніше доведені факти і отримаємо ${\displaystyle m\leqslant {t}\leqslant 2(3/5)^{r}m<4(3/5)^{r}m<3m}$; отже ${\displaystyle r\leqslant 2}$ і ${\displaystyle t=m}$ або ${\displaystyle t=2m}$. Зауважимо, що ${\displaystyle t}$ — ступінь двійки. Звідси випливає, що ${\displaystyle e_{1}=1}$ і ${\displaystyle e_{r}=1}$. Якщо ${\displaystyle n}$ — складене, то має бути ${\displaystyle n=2^{q}-1=(2^{k}+1)(2^{l}-1)}$, де ${\displaystyle 2^{k}+1}$ і ${\displaystyle 2^{l}-1}$ — прості числа. Подальше розкладання на прості числа, якщо ${\displaystyle q}$ — непарне, неможливо, тому ${\displaystyle n}$ — просте.

Навпаки, припустимо, що ${\displaystyle n=2^{q}-1}$ — просте. Покажемо, що ${\displaystyle V_{2^{q}-2}\equiv 0{\pmod {n))}$. Для цього достатньо показати, що ${\displaystyle V_{2^{q}-1}\equiv {-2}{\pmod {n))}$, так як ${\displaystyle V_{2^{q}-1}=(V_{2^{q}-2}-2)^{2))$.

${\displaystyle V_{2^{q}-1}=\left({\frac ((\sqrt {2))+{\sqrt {6))}{2))\right)^{n+1}+\left({\frac ((\sqrt {2))-{\sqrt {6))}{2))\right)^{n+1}=2^{-n}\sum _{k}{\binom {n+1}{2k)){\sqrt {2))^{n+1-2k}{\sqrt {6))^{2k}=2^{(1-n)/2}\sum _{k}{\binom {n+1}{2k))3^{k}.}$

Так як ${\displaystyle n}$ — просте, то біноміальний коефіцієнт ${\displaystyle {\tbinom {n+1}{2k))={\tbinom {n}{2k))+{\tbinom {n}{2k-1))}$ ділиться на ${\displaystyle n}$ крім тих випадків, коли ${\displaystyle k=0}$ чи ${\displaystyle k=(n+1)/2}$. Отже:

${\displaystyle 2^{(n-1)/2}V_{2^{q}-1}\equiv {1+3^{(n+1)/2)){\pmod {n))}$.

Тут ${\displaystyle 2\equiv (2^{(q+1)/2})^{2}{\pmod {n))}$, тому ${\displaystyle 2^{(n-1)/2}\equiv {(2^{(q+1)/2})}^{n-1}\equiv 1{\pmod {n))}$ за малої теореми Ферма. Нарешті, використовуючи найпростіший випадок квадратичного закону взаємності, покажемо, що ${\displaystyle 3^{(n-1)/2}\equiv {-1}{\pmod {n))}$, так як ${\displaystyle n\mod {3}=1}$ і ${\displaystyle n\mod {4}=3}$. Це значить, що ${\displaystyle V_{2^{q}-1}\equiv {-2))$, так що ${\displaystyle V_{2^{q}-2}\equiv 0}$. ^[3]

Lucas–Lehmer(p)
    var s = 4
    var M = 2p — 1
    repeat p — 2 times:
        s = ((s × s) — 2) mod M
    if s = 0 return PRIME else return COMPOSITE

Для чисел виду ${\displaystyle k2^{n}-1}$, де ${\displaystyle 2^{n}>k}$ існує модифікація цього тесту^[en], розроблена Хансом Різелем^[en]. Можливо узагальнення тесту для чисел виду ${\displaystyle A2^{2n}+B2^{n}-1}$^[4]. Також існує більш загальний варіант — тест Люка, який застосовний для будь-якого натурального числа ${\displaystyle N}$, якщо відоме розкладання на прості множники числа ${\displaystyle N-1}$.

Завдяки тесту Люка — Лемера прості числа Мерсенна утримують лідерство як найбільші відомі прості числа^[5]. Саме тест Люка — Лемера лежить в основі проекту розподілених обчислень GIMPS, що шукає нові прості числа Мерсенна.

• Тест простоти
• Тест простоти Люка
• Числа Мерсенна
• Тест Люка — Лемера — Різеля^[en]

• Weisstein, Eric W. Lucas-Lehmer Test(англ.) на сайті Wolfram MathWorld.
• А.Н.Рудаков. Числа Фібоначчі і простота числа 2¹²⁷-1 // 4 (третя серія). — Математична просвіта, 2000.
• Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — Addison-Wesley Professional, 1997. — С. 389-394. — ISBN 978-0201896848.
• Paulo Ribenboim. The Little Book of Bigger Primes. — Springer, 2004. — С. 75-80. — ISBN 978-0387201696.
• Eric Bach; Jeffrey Shallit. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 273-275. — ISBN 978-0262024051.