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

Составное число n называется псевдопростым Ферма по основанию a, если a и n взаимно просты и ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$.[1]

Псевдопростые Ферма по основанию 2 образуют последовательность:

341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, … (последовательность A001567 в OEIS)

а по основанию 3 — последовательность:

91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, … (последовательность A005935 в OEIS)

Число, являющееся псевдопростым Ферма по каждому взаимно простому с ним основанию, называется числом Кармайкла.

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

${\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}},}$

где ${\displaystyle \left({\frac {a}{n}}\right)}$ — символ Якоби. Так как из этого сравнения следует, что ${\displaystyle a^{n-1}\equiv 1{\pmod {n}},}$ то всякое псевдопростое Эйлера — Якоби также является псевдопростым Ферма (по тому же основанию).

Псевдопростые Эйлера — Якоби по основанию 2 образуют последовательность:

561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, … (последовательность A047713 в OEIS)

а по основанию 3 — последовательность:

121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, … (последовательность A048950 в OEIS)

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

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

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

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

и

P(n) = P(n − 2) + P(n − 3) for n > 2.

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

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

${\displaystyle (-1)^{\frac {n-1}{2}}\cdot C_{\frac {n-1}{2}}\equiv 2{\pmod {n}},}$

где C_m — m-ое число Каталана. Сравнение верно для любого нечётного простого числа n.

Известно только три псевдопростых чисел Каталана: 5907, 1194649, и 12327121 (последовательность A163209 в OEIS), причём два последних из них являются квадратами простых чисел Вифериха. В общем случае, если p — простое число Вифериха, то p² — псевдопростое Каталана.

• Тест Соловея — Штрассена
• Тест Миллера — Рабина
• Сильное псевдопростое число
• Псевдопростые числа Ферма

• Aebi, C.; Cairns, G. Catalan numbers, primes and twin primes (неопр.) // Elemente der Mathematik. — 2008. — Т. 63, № 4. — С. 153—164. — doi:10.4171/EM/103.
• Catalan pseudoprimes. Research in Scientific Computing in Undergraduate Education.