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

Proth's theorem

From Prime-Wiki
Revision as of 23:45, 23 June 2019 by Dylan14 (talk | contribs) (typos fixed)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

This article is about Proth's theorem.

Proth's theorem (1878) states:

Let [math]\displaystyle{ n = h*2^k+1 }[/math] and [math]\displaystyle{ h\lt 2^k }[/math]; then [math]\displaystyle{ n }[/math] is prime if (and only if) there is an integer [math]\displaystyle{ a }[/math] such that

[math]\displaystyle{ a^{(n-1)/2} \equiv -1 (mod\,n) }[/math].

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

External links