Proth's theorem, published by the French mathematician François 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.
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
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
History
François Proth (1852-1879) published the theorem in 1878.
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.