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 integer a with 1<a<N such that a^(kp)=-1 (mod N) and GCD(a^k+1,N)=1,

where GCD is the greatest common divisor (i.e., a^k+1 and N are relatively prime). The underlying argument appears in Pocklington (1914/16, pp. 29-30) and Lehmer (1927, pp. 331-332).

See also

Pocklington's Theorem

Explore with Wolfram|Alpha

References

Lehmer, D. H. "Tests for Primality by the Converse of Fermat's Theorem." Bull. Amer. Math. Soc. 33, 327-340, 1927. https://doi.org/10.1090/S0002-9904-1927-04368-3.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 Resource. https://mathworld.wolfram.com/PocklingtonsCriterion.html

Subject classifications