| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
Navigation
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Proth's theorem"
(link corr.) |
(typos fixed) |
||
| Line 1: | Line 1: | ||
This article is about '''Proth's theorem'''. | This article is about '''Proth's theorem'''. | ||
| − | + | Proth's theorem (1878) states: | |
Let <math>n = h*2^k+1</math> and <math>h<2^k</math>; then <math>n</math> is prime if (and only if) there is an integer <math>a</math> such that | Let <math>n = h*2^k+1</math> and <math>h<2^k</math>; then <math>n</math> is prime if (and only if) there is an integer <math>a</math> such that | ||
:<math>a^{(n-1)/2} \equiv -1 (mod\,n)</math>. | :<math>a^{(n-1)/2} \equiv -1 (mod\,n)</math>. | ||
| − | A prime of this form is known as [[Proth prime]]. | + | A prime of this form is known as a [[Proth prime]]. |
==External links== | ==External links== | ||
*[[Wikipedia:Proth's theorem|Wikipedia]] | *[[Wikipedia:Proth's theorem|Wikipedia]] | ||
[[Category:Primality tests]] | [[Category:Primality tests]] | ||
Revision as of 23:45, 23 June 2019
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.
