Proth's theorem

In number theory, Proth's theorem is a theorem which forms the basis of a primality test for Proth numbers known as Proth's test. Proth numbers, sometimes called Proth Numbers of the First Kind, are those integers p which take the form p = k2ⁿ + 1 with an odd k where k < 2ⁿ. For Proth Numbers of the Second Kind, see related topic Riesel numbers.

The theorem states that for any Proth number (of the first kind), p, then p is prime if there exists an integer a for which Euler's criterion yields –1, that is,

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

In this case, p is called a Proth prime. The contrapositive is also true: if p is Proth 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.