Pocklington's Criterion

Let $p$ be an Odd Prime, $k$ be an Integer such that $p\notdiv k$ and $1\leq k\leq 2(p+1)$, and

$$N\equiv 2kp+1.$$

Then the following are equivalent

1. $N$ is Prime.

2. $\mathop{\rm GCD}\nolimits (a^k+1,N)=1$.

This is a modified version of the original theorem due to Lehmer.

References

Pocklington, H. C. ``The Determination of the Prime or Composite Nature of Large Numbers by Fermat's Theorem.'' Proc. Cambridge Phil. Soc. 18, 29-30, 1914/16.