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

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

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

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

Складене число n називається псевдопростим Ферма за основою a, якщо a та n взаємно прості й $a^{n-1}\equiv 1(\mathrm{mod}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, якщо воно задовольняє порівнянню

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

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

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

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

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

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

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

де C_m — m-те число Каталана. Порівняння істинне для будь-якого непарного простого числа n.

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

Див. також

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

Посилання

• Шаблон:Стаття
• Catalan pseudoprimes. Research in Scientific Computing in Undergraduate Education.