Topics Register • News • History • How to • Sequences statistics • Template prototypes

Proth's theorem

Let $\displaystyle{ n = h*2^k+1 }$ and $\displaystyle{ h\lt 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 (mod\,n) }$.