TOPICS
Search

Pocklington's Theorem


Let n-1=FR where F is the factored part of a number

 F=p_1^(a_1)...p_r^(a_r),
(1)

where (R,F)=1, and R<sqrt(n).

Pocklington's theorem, also known as the Pocklington-Lehmer test, then says that if there exists a b_i for i=1, ..., r such that

 b_i^(n-1)=1 (mod n)
(2)

and

 GCD(b_i^((n-1)/p_i)-1,n)=1,
(3)

then n is prime.


See also

Pocklington's Criterion

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Pocklington's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PocklingtonsTheorem.html

Subject classifications