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

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

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

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

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

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

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

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

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

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

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

${\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, … (последовательность в OEIS )

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

121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, … (последовательность в 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-м году.

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

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

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

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

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

См. также

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

Примечания

Ссылки

• Aebi, C.; Cairns, G. (неопр.) // (англ.) ( . — 2008. — Т. 63 , № 4 . — С. 153—164 . — doi : .
• . Research in Scientific Computing in Undergraduate Education.