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

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

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

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

D=P^{2}-4Q\neq 0.

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

V_{p}\equiv P{\pmod {p}}

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

\left({\frac {D}{p}}\right)=\varepsilon \neq 0,

то p делит U _p-ε .

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

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

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

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

n делит U _s

n делит V _{2
^j

s}

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

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

n делит U _s и V _s , сравнимо с ±2 по модулю n

n делит V _{2
^j

s}

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

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

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

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

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

где Q = ±1.

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

Нечетное составное целое n , являющееся также числом Кармайкла
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.

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

См. также

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

Примечания

Robert Baillie; Samuel S. Wagstaff, Jr. (англ.) // (англ.) ( : journal. — 1980. — October ( vol. 35 , no. 152 ). — P. 1391—1417 . — doi : . 6 сентября 2006 года.
Somer, Lawrence. On Even Fibonacci Pseudoprimes // Applications of Fibonacci Numbers (неопр.) / G. E. Bergum et al.. — Dordrecht: (англ.) ( , 1991. — Т. 4. — С. 277—288.

Литература

Richard E. Crandall ; Carl Pomerance. (неопр.) . — Springer-Verlag , 2001. — С. —132. — ISBN 0-387-94777-9 .
(англ.) ( . Prime Numbers and Computer Methods for Factorization (англ.) . — 2nd ed. — (англ.) ( , 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 .