Критерий Поклингтона

---

Критерий Поклингтона — детерминированный тест на простоту, разработанный Генри Поклингтоном^[англ.] и Дерриком Генри Лехмером. Критерий Поклингтона позволяет определять, является ли данное число простым.

Пусть ${\displaystyle n=q^{k}R+1}$ где q — простое число, ${\displaystyle k\geqslant 1}$. Если существует такое целое число ${\displaystyle a}$, что ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$ и НОД${\displaystyle (a^{{(n-1)}/q}-1,n)=1}$, то каждый простой делитель ${\displaystyle p}$ числа ${\displaystyle n}$ имеет вид ${\displaystyle p=q^{k}r+1}$ при некотором натуральном ${\displaystyle r}$.

---