Proth's theorem

This article is about Proth's theorem.

Proth's theorem (1878) states:

Let ${\displaystyle n=h\ast 2^k+1}$ and ${\displaystyle h<2^k}$; then ${\displaystyle n}$ is prime if (and only if) there is an integer ${\displaystyle a}$ such that

${\displaystyle a^{(n-1)/2}\equiv -1(modn)}$.

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

External links

• Wikipedia