Псевдопростое число Люка
В теории чисел классы псевдопростых чисел Люка и псевдопростых чисел Фибоначчи состоят из чисел Люка, прошедших некоторые тесты, которым удовлетворяют все простые числа.
Базовое свойство
[править | править код]Рассмотрим последовательности Люка Un(P,Q) и Vn(P,Q), где целые числа P и Q удовлетворяют условию:
Тогда, если p — простое число, большее 2, то
и, если символ Якоби
то p делит Up-ε.
Псевдопростые Люка
[править | править код]Псевдопростое Люка[1] — это составное число n, которое делит Un-ε. (Ризель (англ. Riesel) добавляет условие: символ Якоби .)
В частном случае последовательности Фибоначчи, когда 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.
Было высказано предположение, что не существует четных псевдопростых чисел Фибоначчи[2]
См. также
[править | править код]Примечания
[править | править код]- ↑ Robert Baillie; Samuel S. Wagstaff, Jr. Lucas Pseudoprimes (англ.) // Mathematics of Computation[англ.] : journal. — 1980. — October (vol. 35, no. 152). — P. 1391—1417. — doi:10.1090/S0025-5718-1980-0583518-6. Архивировано 6 сентября 2006 года.
- ↑ Somer, Lawrence. On Even Fibonacci Pseudoprimes // Applications of Fibonacci Numbers (неопр.) / G. E. Bergum et al.. — Dordrecht: Kluwer[англ.], 1991. — Т. 4. — С. 277—288.
Литература
[править | править код]- 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.
Для улучшения этой статьи желательно:
|