Псевдопросте число — натуральне число, що має деякі властивості простих чисел, але при цьому є складеним. Залежно від розглянутих властивостей існує кілька типів псевдопростих чисел.
Існування псевдопростих є перешкодою для перевірок простоти, які намагаються використовувати ті чи інші властивості простих чисел для визначення простоти даного числа.
Псевдопрості Ферма Складене число n називається псевдопростим Ферма за основою a, якщо a та n взаємно прості й .
Псевдопрості Ферма за основою 2 утворюють послідовність:
341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, … ()
а за основою 3 — послідовність:
91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, … ()
Число, що є псевдопрости Ферма за кожною взаємно простою з ним основою, називається числом Кармайкла.
Псевдопрості Ейлера — Якобі Непарне складене число n називається псевдопростим Ейлера — Якобі за основою a, якщо воно задовольняє порівнянню
де — символ Якобі. Оскільки з цього порівняння випливає, що то будь-яке псевдопросте Ейлера — Якобі також є псевдопростим Ферма (за тією ж основою).
Псевдопрості Ейлера — Якобі за основою 2 утворюють послідовність:
561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, … ()
а за основою 3 — послідовність:
121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, … ()
Псевдопрості Фібоначчі
Псевдопрості Люка
Псевдопрості Перрена Складене число 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, що задовольняє порівнянню
де Cm — m-те число Каталана. Порівняння істинне для будь-якого непарного простого числа n.
Відомо тільки три псевдопростих числа Каталана: 5907, 1194649, і 12327121 (), причому два останніх з них є квадратами простих чисел Віфериха. У загальному випадку, якщо p — просте число Віфериха, то p2 — псевдопросте Каталана.
Див. також Тест Соловея — Штрассена Тест Міллера — Рабіна Сильне псевдопросте число Псевдопрості числа Ферма
Примітки
Посилання
Catalan pseudoprimes. Research in Scientific Computing in Undergraduate Education.