Псевдопростое число Люка

 В теории чисел классы псевдопростых чисел Люка ипсевдопростых чисел Фибоначчи состоят из чисел Люка, прошедшихнекоторые тесты, которым удовлетворяют все простые числа.

Базовоесвойство


 Рассмотрим последовательности ЛюкаUn(P,Q) иVn(P,Q), где целые числаP и Q удовлетворяют условию:

D=P24Q0.
 Тогда, если p — простое число, большее 2, то

VpP(modp)
 и, если символ Якоби

(Dp)=ε0,
 то p делит Up-ε.

ПсевдопростыеЛюка


Псевдопростое Люка — это составное число n, котороеделит Un-ε. (Ризель добавляет условие: символЯкоби (Dn)=1.)
 В частном случае последовательности Фибоначчи, когда P = 1,Q = −1 и D = 5, первые псевдопростые числа Люка — это323 и 377; (5323) и (5377)оба равны −1, 324-ое число Фибоначчи делится на 323, а 378-ое —делится на 377.
Сильным псевдопростым Люка называется нечетное составное числоn с (n,D)=1, и n-ε=2rs с sнечетным, удовлетворяющее одному из условий:

n делит Us
n делитV2j\emphs
 для некоторого j \textless r. Сильное псевдопростое Люкаявляется также псевдопростым Люка.
Сверхсильным псевдопростым Люка называется сильноепсевдопростое Люка для множества параметров (P,Q), гдеQ = 1, удовлетворяющее одному из слегка модифицированных условий:

n делит Us иVs, сравнимо с ±2 по модулю n
n делитV2j\emphs
 для некоторого j \textless r. Сверхсильное псевдопростоеЛюка является также сильным псевдопростым Люка.
 Комбинируя тест на псевдопростоту Люка с тестом простоты Ферма, скажем,по модулю 2, можно получить очень сильные вероятностные тесты простоты.

ПсевдопростыеФибоначчи


Псевдопростое Фибоначчи — это составное число, n длякоторого

Vn сравним с P по модулю n,
 где Q = ±1.
Сильное псевдопростое Фибоначчи может быть определено каксоставное число, являющееся псевдопростым числом Фибоначчи для любогоP. Из определения следует (см. Мюллер (Müller) и Освальд(Oswald)), что :

  1. Нечетное составное целое n, являющееся также числом Кармайкла
  2. 2(pi + 1) (n − 1) или 2(pi + 1) (npi) для любого простого pi, делящего n.

 Наименьшее сильное псевдопростое число Фибоначчи — это443372888629441, имеющее делители 17, 31, 41, 43, 89, 97, 167 и 331.
 Было высказано предположение, что не существует четных псевдопростыхчисел Фибоначчи