21-08-2023
Критерий Поклингтона — детерминированный тест на простоту. Критерий Поклингтона позволяет определять, является ли данное число простым .
Пусть где q - простое число, . Если существует такое целое число , что и НОД, то каждый простой делитель числа имеет вид при некотором натуральном
Пусть n - натуральное число. Пусть число n -1 имеет простой делитель q, причем . Если найдётся такое целое число a, что выполняются следующие два условия:
то n - простое число.
Предположим, что n является составным числом. Тогда существует простое число p - делитель n, причем . Заметим, что , следовательно q и p -1 - взаимнопросты. Следовательно, существует некоторое целое число u, такое, что . Но в таком случае (в силу условия 1)). Но таким образом получено противоречие условию 2). Следовательно, n является простым числом.
Теорема Поклингтона является отличным тестом на простоту при условии, что n-1 делится на простое число , а также если q можно найти и доказать его простоту. Иначе, этим критерием пользоваться нельзя. Так же стоит отметить, что этот критерий является вероятностым только в том смысле, что случайно выбранное число a может либо удовлетворять условию НОД , либо не удовлетворять ему. Однако, как только найдено такое a, критерий доказывает, что n - простое число. В отличие от вероятностных тестов (таких, например, как тест Миллера-Рабина, тест Соловея-Штрассена и др.) заключение теста Поклингтона - вполне определенное.
Докажем, что число n=31 является простым. Найдём простой делитель числа n-1, т.е. 30. Им является q=5, причём . Число a=2 удовлетворяет обоим критериям:
Следовательно число 31 простое по критерию Поклингтона
Критерий Поклингтона.