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 is also named after the French mathematician and original publisher of the theorem, François Proth

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.