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

Псевдопростое число — натуральное число, обладающеенекоторыми свойствами простых чисел, являясь тем не менее составным. Взависимости от рассматриваемых свойств существует несколько различныхтипов псевдопростых чисел.
 Существование псевдопростых является препятствием для тестов простоты,пытающихся использовать те или иные свойства простых чисел дляопределения простоты данного числа.

ПсевдопростыеФерма


 Составное число n называется псевдопростым Ферма пооснованию a, если a и n взаимно просты иan11(modn).
 Псевдопростые Ферма по основанию 2 образуют последовательность:

 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277,4033, \ldots
 а по основанию 3 — последовательность:

 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701,2821, \ldots
 Число, являющееся псевдопростым Ферма по каждому взаимно простому с нимоснованию, называется числом Кармайкла.

Псевдопростые Эйлера —Якоби


 Нечётное составное число n называется псевдопростымЭйлера — Якоби по основанию a, если оно удовлетворяетсравнению

a(n1)/2(an)(modn),
 где (an) — символ Якоби. Так как из этогосравнения следует, что an11(modn), то всякоепсевдопростое Эйлера — Якоби также является псевдопростым Ферма (потому же основанию).
 Псевдопростые Эйлера — Якоби по основанию 2 образуютпоследовательность:

 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481,10585, \ldots
 а по основанию 3 — последовательность:

 121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457,15841, \ldots

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



Основная статья: Псевдопростое число Фибоначчи

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



Основная статья: Псевдопростое число Люка

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


 Составное число q называется псевдопростым Перрина, еслионо делит q-е число Перрина P(q), задаваемоерекуррентным соотношением:

P(0) = 3, P(1) = 0, P(2) = 2,
 и

P(n) = P(n − 2) + P(n − 3) forn \textgreater 2.

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


 Псевдопростое число, прошедшее трёхшаговый тест принадлежности квозможно простым числам, разработанный Джоном Грантамом (Jon Grantham) в1996-м году.

ПсевдопростыеКаталана


 Нечётное составное число n, удовлетворяющее сравнению

(1)n12Cn122(modn),
 где Cm — m-ое число Каталана. Сравнениеверно для любого нечётного простого числа n.
 Известно только три псевдопростых чисел Каталана: 5907, 1194649, и12327121 , причём два последних из них являются квадратами простыхчисел Вифериха. В общем случае, если p — простое числоВифериха, то p2 — псевдопростое Каталана.