Proth's theorem

Statement

Existential version

Suppose $p$ is a Proth number, i.e., a number of the form $k\cdot 2^{n}+1$ where $k<2^{n}$ and $k$ is odd. Then, $p$ is a prime number (and hence a Proth prime) if and only if there exists $a$ such that:

$a^{(p-1)/2}\equiv -1{\pmod {p}}$

Note that one direction of implication ($p$ prime implying the existence of $a$) is true even for numbers that are not Proth numbers, so it is the other direction that is substantive.

Particular element version

Suppose $p$ is a Proth number, i.e., a number of the form $k\cdot 2^{n}+1$ where $k<2^{n}$ and $k$ is odd. Pick an element $a$ such that the Jacobi symbol $\left({\frac {a}{p}}\right)$ is -1. Then, $p$ is a prime number (and hence a Proth prime) if and only if:

$a^{(p-1)/2}\equiv -1{\pmod {p}}$

Related facts

• Pepin's primality test: This is a version for Fermat numbers. For Fermat numbers, we can choose $a=3$.

Proof

Fill this in later