TOPICS
Search

Pocklington's Criterion


Let p be an odd prime, k be an integer such that pk and 1<=k<=2(p+1), and

 N=2kp+1.

Then the following are equivalent

1. N is prime.

2. There exists an a such that GCD(a^k+1,N)=1,

where GCD is the greatest common divisor (i.e., a^k+1 and N are relatively prime). This is a modified version of the original theorem due to Lehmer.


See also

Pocklington's Theorem

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Pocklington's Criterion

Cite this as:

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

Subject classifications