В теории чисел классы псевдопростых чисел Люка и псевдопростых чисел Фибоначчи состоят из чисел Люка, прошедших некоторые тесты, которым удовлетворяют все простые числа.
Базовое свойство Рассмотрим последовательности Люка Un(P,Q) и Vn(P,Q), где целые числа P и Q удовлетворяют условию:
Тогда, если p — простое число, большее 2, то
и, если символ Якоби
то p делит Up-ε.
Псевдопростые Люка Псевдопростое Люка — это составное число n, которое делит Un-ε. (Ризель () добавляет условие: символ Якоби .)
В частном случае последовательности Фибоначчи, когда P = 1, Q = −1 и D = 5, первые псевдопростые числа Люка — это 323 и 377; и оба равны −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)), что :
Нечетное составное целое n, являющееся также числом Кармайкла 2(pi + 1) | (n − 1) или 2(pi + 1) | (n − pi) для любого простого pi, делящего n.
Наименьшее сильное псевдопростое число Фибоначчи — это 443372888629441, имеющее делители 17, 31, 41, 43, 89, 97, 167 и 331.
Было высказано предположение, что не существует четных псевдопростых чисел Фибоначчи
См. также Псевдопростое число
Примечания
Литература
Müller, Winfried B. and Alan Oswald. «Generalized Fibonacci Pseudoprimes and Probable Primes». In G.E. Bergum et al., eds. Applications of Fibonacci Numbers. Volume 5. Dordrecht: Kluwer, 1993. 459—464.
Ссылки Anderson, Peter G. Fibonacci Pseudoprimes, their factors, and their entry points. Anderson, Peter G. Fibonacci Pseudoprimes under 2,217,967,487 and their factors.
Категория:Целочисленные последовательности Категория:Теория чисел Категория:Псевдопростые числа