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"
(typos fixed) |
(Changing notation to modern form and correcting converse) |
||
Line 3: | Line 3: | ||
Proth's theorem (1878) states: | Proth's theorem (1878) states: | ||
− | Let <math> | + | 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^{( | + | :<math>a^{(p-1)/2} \equiv -1\pmod{p}</math>. |
− | A prime of this form is known as a [[Proth prime]]. | + | Furthermore, if <math>a</math> is a [[quadratic residue|quadratic non-residue]] modulo <math>p</math>, then the converse is also true. |
+ | |||
+ | 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:Primality tests]] | [[Category:Primality tests]] |
Revision as of 18:15, 28 September 2023
This article is about Proth's theorem.
Proth's theorem (1878) states:
Let
.
Furthermore, if
A prime