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"

From Prime-Wiki
Jump to: navigation, search
(Changing notation to modern form and correcting converse)
(Adding to new subcategory)
 
Line 1: Line 1:
This article is about '''Proth's theorem'''.
 
 
 
Proth's theorem (1878) states:
 
Proth's theorem (1878) states:
  
Line 13: Line 11:
 
*[[Wikipedia:Proth's theorem|Wikipedia]]
 
*[[Wikipedia:Proth's theorem|Wikipedia]]
  
[[Category:Primality tests]]
+
[[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.

External links