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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Псевдопростые Ферма[править | править вики-текст]

Составное число n называется псевдопростым Ферма по основанию a, если a и n взаимнопросты и a^{n-1} \equiv 1\pmod{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]

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) for n > 2.

Псевдопростые Фробениуса[править | править вики-текст]

Псевдопростое число, прошедшее трёхшаговый тест принадлежности к возможно простым числам, разработанный Джоном Грантамом (Jon Grantham) в 1996-ом году.[3][4]

Псевдопростые Каталана[править | править вики-текст]

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

 (-1)^{\frac{n-1}{2}} \cdot C_{\frac{n-1}{2}} \equiv 2 \pmod 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. Weisstein, Eric W. Frobenius pseudoprime (англ.) на сайте Wolfram MathWorld.
  4. Jon Grantham (2001). «Frobenius pseudoprimes». Mathematics of Computation 70 (234): 873–891. DOI:10.1090/S0025-5718-00-01197-2.

Ссылки[править | править вики-текст]