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

Псевдопросте число — натуральне число, що має деякі властивості простих чисел, але при цьому є складеним. Залежно від розглянутих властивостей існує кілька типів псевдопростих чисел.

Існування псевдопростих є перешкодою для перевірок простоти, які намагаються використовувати ті чи інші властивості простих чисел для визначення простоти даного числа.

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

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

Псевдопрості Ферма за основою 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, якщо воно задовольняє порівнянню

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

де $\left({\frac {a}{n}}\right)$ — символ Якобі. Оскільки з цього порівняння випливає, що $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) для n > 2.

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

Псевдопросте число, що пройшло трикроковий тест належності до ймовірно простих чисел, розроблений 1996 року Джоном Ґрантамом (Jon Grantham).

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

Непарне складене число n, що задовольняє порівнянню

$(-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 (4 April). — С. 153—164. — DOI:10.4171/EM/103.
• Catalan pseudoprimes. Research in Scientific Computing in Undergraduate Education.