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

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

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

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

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

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

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

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

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

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

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

В частном случае последовательности Фибоначчи , когда P = 1, Q = −1 и D = 5, первые псевдопростые числа Люка — это 323 и 377; ${\displaystyle \left({\tfrac {5}{323}}\right)}$ и ${\displaystyle \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)), что :

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. (неопр.) . — 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 .

Ссылки

• Anderson, Peter G.
• Anderson, Peter G.
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .