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

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

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

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

Складене число n називається псевдопростим Ферма за основою a, якщо a та 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]

де  символ Якобі. Оскільки з цього порівняння випливає, що то будь-яке псевдопросте Ейлера — Якобі також є псевдопростим Ферма (за тією ж основою).

Псевдопрості Ейлера — Якобі за основою 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).[3]

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

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

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

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

Див. також

Примітки

  1. Weisstein, Eric W. Fermat Pseudoprime(англ.) на сайті Wolfram MathWorld.
  2. Weisstein, Eric W. Euler-Jacobi Pseudoprime(англ.) на сайті Wolfram MathWorld.
  3. Jon Grantham. Frobenius pseudoprimes // Mathematics of Computation : journal.  2001. Vol. 70, no. 234 (23 February). P. 873—891. DOI:10.1090/S0025-5718-00-01197-2.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.