Proth's theorem

In number theory, Proth's theorem is a theorem which forms the basis of a primality test for Proth numbers (sometimes called Proth Numbers of the First Kind). For Proth Numbers of the Second Kind, see Riesel numbers.

It states that for any integer p that is a Proth number (of the first kind) - an integer of the form k2ⁿ + 1 with k odd and k < 2ⁿ - and if there exists an integer a for which Euler's criterion is -1, thus:

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}},}$

then p is prime. In this case, p is called a Proth prime. The contrapositive is also true: if p is composite then no such a exists.

It might be noted that the presumption of k being odd does not restrict generality. So long as the condition that k < 2ⁿ is met, any factors of 2 in an even k may be factored out of k and into 2ⁿ, growing the latter while shrinking the former even further; the inequality condition remains true. Thus, k may always be reduced to an odd value, suitable for analyses.