TOPICS

Proth's Theorem

For N=k·2^n+1 with k odd and 2^n>k, if there exists an integer a such that

a^((N-1)/2)=-1 (mod N),

then N is prime. A prime of this form is known as a Proth prime.

See also

Proth Prime

Explore with Wolfram|Alpha

Cite this as:

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

Subject classifications