Тести на простоту, Детальна інформація

Свідками Ферма є числа 2, 3, 5, 6, 7, 8, 9, 10, 12, 13.

Брехунцями Ферма є числа 1, 4, 11, 14.

Тест Ферма зручно використовувати для перевірки числа n на складеність, оскільки для більшості натуральних чисел кількість свідків більша за кількість брехунців. Але існують складені числа, які є псевдопростими за довільною основою (взаємно простою з заданим числом). Такі числа називаються числами Кармайкла і найменше з них дорівнює 561 = 3 * 11 * 17.

Означення. Число n називається числом Кармайкла, якщо воно складене та для довільного a, 1 \xF0A3 a \xF0A3 n – 1, НСД(a, n) = 1, має місце рівність:

an-1 \xF0BA 1 (mod n)

Критерій Корсельта. Для того щоб складене число n було числом Кармайкла, необхідно і достатньо виконання двох умов:

n не ділиться на квадрат простого числа

n – 1 ділиться на p – 1 для всякого простого дільника p числа n.

Приклад. Простими дільниками числа 561 є 3, 11, 17. При цьому жоден з них не входить до розкладу навіть двічі, а число 560 ділиться на 2, 10 та 16:

560 : 2 = 280, 560 : 10 = 56, 560 : 16 = 35

Твердження. Кожне число Кармайкла є добутком хоча б трьох простих чисел.

Приклад. Числа Кармайкла в межі до 100000:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361.

Теорема (Чернік, 1939). Якщо p = 6m + 1, q = 12m + 1, r = 18m + 1 є простими числами, то число pqr є числом Кармайкла.

Приклад. Якщо покласти m = 1, то отримаємо p = 7, q = 13, r = 19 – всі прості числа. Отже n = 7 * 13 * 19 = 1729 – число Кармайкла.

Річард Пінч, провівши велику кількість обчислень, виявив, що кількість чисел Кармайкла у натуральному ряді до 1012 дорівнює 8241, до 1013 – 19279, до 1014 – 44706, до 1015 – 105212. З іншого боку декількома авторами наводилася верхня межа для C(n) – кількість чисел Кармайкла від 1 до n. Одна з них (і яка на сьогодні вважається найбільш точною):

C(n) \xF0A3 n1 – {1 + o(1)} log log log n / log log n

Теорема (Чіполла, 1904). Існує нескінченно багато складених псевдопростих чисел за основою b.

, то b2p \xF0BA 1 (mod yp).

.

Оскільки yp – 1 - парне, а також за теоремою Ферма bp-1 \xF0BA 1 (mod p) (вираз bp-1 - 1 ділиться на p), то yp – 1 \xF0BA 0 (mod 2p).

\xF0BA 1 (mod yp).

Всі числа yp є псевдопростими за основою b.

= 341 = 11 * 31.

Оскільки 2340 \xF0BA\xF0201 (mod 341), то складене число 341 є псевдопростим за основою 2.

Тест Соловай - Штрасена

Тест Соловай – Штрасена базується на критерії Ейлера: якщо n – просте, то

(mod n)

для всіх значень a, для яких НСД(a, n) = 1.

Означення. Нехай n – непарне складене число, a – ціле число, 1 \xF0A3 a \xF0A3 n – 1.