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(\mathrm{mod}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 $(\frac{a}{p})$ is -1. Then, $p$ is a prime number (and hence a Proth prime) if and only if:

$a^{(p-1)/2}\equiv -1(\mathrm{mod}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