Loading AI tools
Из Википедии, свободной энциклопедии
Псевдопростое число — натуральное число, обладающее некоторыми свойствами простых чисел, являясь тем не менее составным. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел.
Существование псевдопростых является препятствием для тестов простоты, пытающихся использовать те или иные свойства простых чисел для определения простоты данного числа.
Составное число n называется псевдопростым Ферма по основанию a, если a и n взаимно просты и .[1]
Псевдопростые Ферма по основанию 2 образуют последовательность:
а по основанию 3 — последовательность:
Число, являющееся псевдопростым Ферма по каждому взаимно простому с ним основанию, называется числом Кармайкла.
Нечётное составное число n называется псевдопростым Эйлера — Якоби по основанию a, если оно удовлетворяет сравнению[2]
где — символ Якоби. Так как из этого сравнения следует, что то всякое псевдопростое Эйлера — Якоби также является псевдопростым Ферма (по тому же основанию).
Псевдопростые Эйлера — Якоби по основанию 2 образуют последовательность:
а по основанию 3 — последовательность:
Составное число q называется псевдопростым Перрина, если оно делит q-е число Перрина P(q), задаваемое рекуррентным соотношением:
и
Псевдопростое число, прошедшее трёхшаговый тест принадлежности к возможно простым числам, разработанный Джоном Грантамом (Jon Grantham) в 1996-м году.[3][4]
Нечётное составное число n, удовлетворяющее сравнению
где Cm — m-ое число Каталана. Сравнение верно для любого нечётного простого числа n.
Известно только три псевдопростых чисел Каталана: 5907, 1194649, и 12327121 (последовательность A163209 в OEIS), причём два последних из них являются квадратами простых чисел Вифериха. В общем случае, если p — простое число Вифериха, то p2 — псевдопростое Каталана.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.