В теории чисел классы псевдопростых чисел Люка и псевдопростых чисел Фибоначчи состоят из чисел Люка, прошедших некоторые тесты, которым удовлетворяют все простые числа.
Базовое свойство
Рассмотрим последовательности Люка Un(P,Q) и Vn(P,Q), где целые числа P и Q удовлетворяют условию:
D = P 2 − 4 Q ≠ 0. {displaystyle D=P^{2}-4Q eq 0.}Тогда, если p — простое число, большее 2, то
V p ≡ P ( mod p ) {displaystyle V_{p}equiv P{pmod {p}}}и, если символ Якоби
( D p ) = ε ≠ 0 , {displaystyle left({frac {D}{p}} ight)=varepsilon eq 0,}то p делит Up-ε.
Псевдопростые Люка
Псевдопростое Люка — это составное число n, которое делит Un-ε. (Ризель (англ. Riesel) добавляет условие: символ Якоби ( D n ) = − 1 {displaystyle left({ frac {D}{n}} ight)=-1} .)
В частном случае последовательности Фибоначчи, когда P = 1, Q = −1 и D = 5, первые псевдопростые числа Люка — это 323 и 377; ( 5 323 ) {displaystyle left({ frac {5}{323}} ight)} и ( 5 377 ) {displaystyle left({ frac {5}{377}} ight)} оба равны −1, 324-ое число Фибоначчи делится на 323, а 378-ое — делится на 377.
Сильным псевдопростым Люка называется нечетное составное число n с (n,D)=1, и n-ε=2rs с s нечетным, удовлетворяющее одному из условий:
n делит Us n делит V2jsдля некоторого j < r. Сильное псевдопростое Люка является также псевдопростым Люка.
Сверхсильным псевдопростым Люка называется сильное псевдопростое Люка для множества параметров (P,Q), где Q = 1, удовлетворяющее одному из слегка модифицированных условий:
n делит Us и Vs, сравнимо с ±2 по модулю n n делит V2jsдля некоторого j < r. Сверхсильное псевдопростое Люка является также сильным псевдопростым Люка.
Комбинируя тест на псевдопростоту Люка с тестом простоты Ферма, скажем, по модулю 2, можно получить очень сильные вероятностные тесты простоты.
Псевдопростые Фибоначчи
Псевдопростое Фибоначчи — это составное число, n для которого
Vn сравним с P по модулю n,где Q = ±1.
Сильное псевдопростое Фибоначчи может быть определено как составное число, являющееся псевдопростым числом Фибоначчи для любого P. Из определения следует (см. Мюллер (Müller) и Освальд (Oswald)), что :
Наименьшее сильное псевдопростое число Фибоначчи — это 443372888629441, имеющее делители 17, 31, 41, 43, 89, 97, 167 и 331.
Было высказано предположение, что не существует четных псевдопростых чисел Фибоначчи