info prev up next book cdrom email home

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

\begin{displaymath}
N\equiv 2kp+1.
\end{displaymath}

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.




© 1996-9 Eric W. Weisstein
1999-05-25