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

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

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

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

[math]\displaystyle{ D = P^2 - 4Q \neq 0. }[/math]

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

[math]\displaystyle{ V_p\equiv P\pmod{p} }[/math]

и, если символ Якоби

[math]\displaystyle{ \left(\frac{D}{p}\right) = \varepsilon \ne 0, }[/math]

то p делит U_p-ε.

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

Псевдопростое Люка — это составное число n, которое делит U_n-ε. (Ризель (англ. Riesel) добавляет условие: символ Якоби [math]\displaystyle{ \left(\tfrac{D}{n}\right)=-1 }[/math].)

В частном случае последовательности Фибоначчи, когда P = 1, Q = −1 и D = 5, первые псевдопростые числа Люка — это 323 и 377; [math]\displaystyle{ \left(\tfrac{5}{323}\right) }[/math] и [math]\displaystyle{ \left(\tfrac{5}{377}\right) }[/math] оба равны −1, 324-ое число Фибоначчи делится на 323, а 378-ое — делится на 377.

Сильным псевдопростым Люка называется нечетное составное число n с (n,D)=1, и n-ε=2^rs с s нечетным, удовлетворяющее одному из условий:

n делит U_s

n делит V_2^js

для некоторого j < r. Сильное псевдопростое Люка является также псевдопростым Люка.

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

n делит U_s и V_s, сравнимо с ±2 по модулю n

n делит V_2^js

для некоторого j < r. Сверхсильное псевдопростое Люка является также сильным псевдопростым Люка.

Комбинируя тест на псевдопростоту Люка с тестом простоты Ферма, скажем, по модулю 2, можно получить очень сильные вероятностные тесты простоты.

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

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

V_n сравним с P по модулю n,

где Q = ±1.

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

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

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

Было высказано предположение, что не существует четных псевдопростых чисел Фибоначчи

См. также

• Псевдопростое число

Литература

• Richard E. Crandall; Carl Pomerance. Prime numbers: A computational approach (неопр.). — Springer-Verlag, 2001. — С. 131—132. — ISBN 0-387-94777-9.
• Hans Riesel. Prime Numbers and Computer Methods for Factorization (англ.). — 2nd ed. — Birkhäuser, 1994. — Vol. 126. — P. 130. — (Progress in Mathematics). — ISBN 0-8176-3743-5.
• 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.
• Richard K. Guy. Unsolved Problems in Number Theory (неопр.). — Springer-Verlag, 2004. — С. 45. — ISBN 0-387-20860-7.

Ссылки

• Anderson, Peter G. Fibonacci Pseudoprimes, their factors, and their entry points.
• Anderson, Peter G. Fibonacci Pseudoprimes under 2,217,967,487 and their factors.
• Weisstein, Eric W. Fibonacci Pseudoprime (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Lucas Pseudoprime (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Strong Lucas Pseudoprime (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Extra Strong Lucas Pseudoprime (англ.) на сайте Wolfram MathWorld.