Proth's theorem, published by the French mathematician Francois Proth in 1878 in the Comptes rendus de l'Academie des Sciences de Paris, gives a primality test for Proth numbers, integers of the form k times 2 to the n plus 1 where k is odd and less than 2 to the n. Based on Euler's criterion, it states that such a number p is prime if there exists an integer a such that a raised to the power (p minus 1)/2 is congruent to negative one modulo p. The test is efficient in practice because, when p is prime, roughly half of the values tried for a will succeed as a witness, so only one successful witness is needed to establish primality. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementFor a Proth number p = k 2^n + 1 with k odd and k < 2^n, p is prime if there exists an integer a with a^((p-1)/2) congruent to -1 modulo p. 2 Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Proth's theorem (Wikipedia)
Sources
1. Wikipedia: Proth's theorem
WikipediaLead section, statement-form referenceQuote, Lead section, statement-form reference
The theorem states that for any Proth number (of the first kind), p, p is prime if there exists an integer a for which Euler's criterion yields, 1, that is, a p − 1 2 ≡ − 1 ( mod p ) {2}}\equiv -1{\pmod {p}}} .
2. Proth's theorem (Wikipedia)
Introduction, second paragraph
for any Proth number (of the first kind), p, p is prime if there exists an integer a for which Euler's criterion yields
Wikidata, P577 publication date
1878-00-00T00:00:00Z
In Branch: Number Theory, Lead sentence
In number theory, Proth's theorem is a theorem which forms the basis of a primality test for Proth numbers known as Proth's test.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.