| 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.) |
(Adding to new subcategory) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | + | Proth's theorem (1878) states: | |
| − | + | Let <math>p = k*2^n+1</math> and <math>k < 2^n</math>; then <math>p</math> is prime if there is an integer <math>a</math> such that | |
| + | :<math>a^{(p-1)/2} \equiv -1\pmod{p}</math>. | ||
| − | + | Furthermore, if <math>a</math> is a [[quadratic residue|quadratic non-residue]] modulo <math>p</math>, then the converse is also true. | |
| − | |||
| − | A prime of this form is known as [[Proth prime]]. | + | A prime <math>p</math> of this form is known as a [[Proth prime]]. |
==External links== | ==External links== | ||
*[[Wikipedia:Proth's theorem|Wikipedia]] | *[[Wikipedia:Proth's theorem|Wikipedia]] | ||
| − | [[Category: | + | |
| + | [[Category:Deterministic primality tests]] | ||
Latest revision as of 01:16, 11 August 2024
Proth's theorem (1878) states:
Let [math]\displaystyle{ p = k*2^n+1 }[/math] and [math]\displaystyle{ k \lt 2^n }[/math]; then [math]\displaystyle{ p }[/math] is prime if there is an integer [math]\displaystyle{ a }[/math] such that
- [math]\displaystyle{ a^{(p-1)/2} \equiv -1\pmod{p} }[/math].
Furthermore, if [math]\displaystyle{ a }[/math] is a quadratic non-residue modulo [math]\displaystyle{ p }[/math], then the converse is also true.
A prime [math]\displaystyle{ p }[/math] of this form is known as a Proth prime.
