Proth's theorem

Proth's theorem (1878) states:

Let $p=k\ast 2^n+1$ and $k<2^n$; then $p$ is prime if there is an integer $a$ such that

$a^{(p-1)/2}\equiv -1(\mathrm{mod}p)$.

Furthermore, if $a$ is a quadratic non-residue modulo $p$, then the converse is also true.

A prime $p$ of this form is known as a Proth prime.

External links

• Wikipedia