Proth's theorem

In number theory, Proth's theorem is a theorem which forms the basis of a primality test for Proth numbers (sometimes called Proth Numbers of the First Kind). For Proth Numbers of the Second Kind, see Riesel numbers.

It states ^{[1] [2]} that if p is a Proth number - an integer of the form k2ⁿ + 1 with k odd and k < 2ⁿ - and if there exists an integer a for which

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}},}$

then p is prime. In this case, p is called a Proth prime. The contrapositive is also true: if p is composite then no such a exists.

It might be noted that the presumption of k being odd does not restrict generality. So long as the condition that k < 2ⁿ is met, any factors of 2 in an even k may be factored out of k and into 2ⁿ, growing the latter while shrinking the former even further; the inequality condition remains true. Thus, k may always be reduced to an odd value, suitable for analyses.

Proth's Test

Only one such value of a need be found for the test to deterministically confirm primality. This is a practical test because if p is prime, any chosen a has about a 50 percent chance of working, and if p is not prime then no chosen a will work. Furthermore, since the calculation is mod p, only values of a smaller than p have to be taken into consideration.

Systematic naive variant

If p is composite then no base a will work to bear witness of primality. As such, we may check all base values [2,p-1] to verify compositeness (note that a=0 and a=1 will never work). If any one base a bears witness then primality is confirmed. If none do then compositeness is confirmed. This process, however, can be made more efficient.

In principle, since if p is prime, there is roughly a 50% chance of a chosen a of proving primality, we may make the process slightly more efficient by checking about one-half of all possible a values smaller than p. Once more than p/2 distinct values of a have been tested, compositeness is deterministic. This is because if p is prime then we expect half of all bases to bears witness; by the pigeonhole principle once more than half have been checked we can deduce that none will bear witness, and if no base value a will work then p is composite. If p is prime then at least one of the values checked would inevitably have bore witness, as would all remaining unchecked values. This variation of the test - akin to the deterministic variant of the Fermat primality test - is grossly inefficient and never employed.

Probabilistic Monte Carlo Variant

As 50% of bases a are expected to bear witness to primality, if p is indeed prime, we may form a Monte Carlo probabilistic test thus: if the test is repeatedly performed an m number of times, each iteration with a random a, each time failing to confirm primality, then we may infer that p is probably composite (contrary to the probably prime results typical of other Monte Carlo algorithms such as the Miller-Rabin test). An approximate upper bound error probability ${\displaystyle \varepsilon <\left({\frac {1}{2}}\right)^{m}}$ of a prime being falsely identified as composite can also be inferred. A composite will, however, never be falsely identified as prime. This probabilistic implementation is not typically performed; even though it is far more efficient than the deterministic test, it can be improved both in performance runtime and in accuracy.

Las Vegas Variant

In practice, a quadratic nonresidue of p is found and taken as the value of a, since if a is a quadratic nonresidue modulo p then the converse is also true, and the test is conclusive. For such an a the Legendre symbol is

${\displaystyle \left({\frac {a}{p}}\right)=-1.}$

For such a value of a the test is deterministic in both primeness and compositeness. The value of a may be found by systematically checking values in the interval [2, p-1], through random selection and checking, or by a more direct computation such as via a modified Euclid's algorithm.^{[ citation needed ]} If no quadratic nonresidual can be found then compositeness may be inferred. When a value of a is verified against the Legendre symbol as a valid candidate, it may be used in Proth's criteria to determine primeness or compositeness conclusively.

This formulation of the test is by far the most efficient - particularly where a quadratic nonresidual is calculated directly. Thus, in contrast to many Monte Carlo primality tests (randomized algorithms that can return a false positive or false negative), this deterministic variant of the primality testing algorithm is a Las Vegas algorithm, always returning the correct answer but with a randomly varying runtime. The check against Proth's criteria has a runtime on the order of a constant; the random variability in the overall test runtime is primality a result of the search for an appropriate a value.

Simplified forms

Given a Proth number of the form p = k2ⁿ + 1, particular forms of either p, k, or n have been identified that correspond to predetermined quadratic nonresidual values that are appropriate for use. It has been shown that:

• If p>3 and ${\displaystyle 3\!\!\not |\;k}$, then a=3 is always a quadratic nonresidual (candidate) and therefore a valid base to check, and so:

${\displaystyle 3^{\frac {p-1}{2}}\equiv _{p}-1}$ if and only if p is prime.

This is the basis of Pépin's test for Fermat numbers and their corresponding primes, wherein k=1 is indivisible by 3.

• If p>5 and ${\displaystyle p\equiv _{5}2,3}$, then a=5 is always a quadratic nonresidual (candidate) and therefore a valid base to check, and so:

${\displaystyle 5^{\frac {p-1}{2}}\equiv _{p}-1}$ if and only if p is prime.

Alternative Testing Results

Given a Proth number p = k2ⁿ + 1, let us choose an arbitrary a value. Evaluate Proth's criteria:

${\displaystyle a^{\frac {p-1}{2}}\equiv b{\pmod {p}}}$,

There are generally five distinct outcomes.

Conclusive primality of p:

• b = -1, in which case Proth's criteria is met and p is confirmed prime, as per Proth's theorem.

Inconclusive result:

• b = 1, in which case the test is inconclusive and must be tried again with a new a value.

This condition is what requires reiteration and makes the test probabilistic, as if p were prime then b = ±1 occurs with roughly equal probability, though the b = 1 condition may still be met with composite p.

Conclusive compositeness of p, as per Euler's criterion and the Legendre symbol, which offer early exit conditions when b ≠ ±1:

• b² = 1, with nontrivial divisors of p being GCD(b ± 1, p).
• b² ≠ 1, where p is proven composite by Fermat's test, base a.
• b = 0, where p has a nontrivial divisor GCD(a, p).

Where GCD(a,b) is the greatest common divisor between integers a and b.

Numerical examples

Examples of the theorem include:

• for p = 3 = 1(2¹) + 1, we have that 2^(3-1)/2 + 1 = 3 is divisible by 3, so 3 is prime.
• for p = 5 = 1(2²) + 1, we have that 3^(5-1)/2 + 1 = 10 is divisible by 5, so 5 is prime.
• for p = 13 = 3(2²) + 1, we have that 5^(13-1)/2 + 1 = 15626 is divisible by 13, so 13 is prime.
• for p = 9, which is not prime, there is no a such that a^(9-1)/2 + 1 is divisible by 9.

The fact that p=9 is not prime can be deterministically verified by checking that no such a (in mod 9) exists. This may be done by systematically checking each value of a from 2 to 8 (a=0 and a=1 will never work). It is however sufficient to check values 2 to 5, or one-half of all possible values under 9. If 9 were a prime then by the pigeonhole principle, at lease one of these values of a will confirm primality, since it is expected that half of them would.

Alternatively, if we employ the deterministic variant wherein the quadratic nonresidual is directly computed, the work requires fewer iterations to confirm both compositeness and primality.

• for p = 97 = 3(2⁵) + 1, we have a quadratic nonresidual of a=5, and that 5^(97-1)/2 + 1 = 3552713678800500929355621337890626 is divisible by 97, so 97 is prime.
• for p = 1537 = 3(2⁹) + 1, we have a quadratic nonresidual of a=5, and that 5^(1537-1)/2 + 1 = 1052 (mod 1537) is not divisible by 1537, so 1537=29x53 is not prime.

In each of the previous two examples, an appropriate value of a was directly computed using a quadratic nonresidual computation such that the results of the test would be conclusive - a valid quadratic nonresidual in both the prime and composite cases. It was not necessarily to systematically search for an a to witness the prime case, or to reiterate the test a sufficient number of times for the composite. If a quadratic nonresidual cannot be found, or if one does not exist, we may take this as confirmation of compositeness.

Prime Search

The first Proth primes are (sequence A080076 in the OEIS ):

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ….

The largest known Proth prime as of 2016 ^[update] is ${\displaystyle 10223\cdot 2^{31172165}+1}$, and is 9,383,761 digits long. ^[3] It was found by Peter Szabolcs in the PrimeGrid volunteer computing project which announced it on 6 November 2016. ^[4] It is the 11th-largest known prime number as of January 2024, it was the largest known non-Mersenne prime until being surpassed in 2023, ^[5] and is the largest Colbert number.^{[ citation needed ]} The second largest known Proth prime is ${\displaystyle 202705\cdot 2^{21320516}+1}$, found by PrimeGrid. ^[6]

Special cases

When k=n, the number takes the form of p = n2ⁿ + 1, and if we may relax the condition requiring that k (or n) is odd, these are known as Cullen numbers, with corresponding Cullen primes.

Proof

The proof for this theorem uses the Pocklington-Lehmer primality test, a corollary to the main theorem of the article. It is a relatively simple special case to prove Proth's theorem from it. It also closely resembles the proof of Pépin's test. The proof can be found on page 52 of the book by Ribenboim in the references.

History

François Proth (1852–1879) published the theorem in 1878. ^{[7] [8]}

See also

• Pépin's test (the special case k = 1, where one chooses a = 3)
• Sierpinski number

References

1. Paulo Ribenboim (1996). The New Book of Prime Number Records . New York, NY: Springer. p.  52. ISBN   0-387-94457-5.
2. Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization (2 ed.). Boston, MA: Birkhauser. p.  104. ISBN   3-7643-3743-5.
3. Chris Caldwell, The Top Twenty: Proth, from The Prime Pages.
4. "World Record Colbert Number discovered!".
5. Chris Caldwell, The Top Twenty: Largest Known Primes, from The Prime Pages.
6. Caldwell, Chris K. "The Top Twenty: Largest Known Primes".
7. François Proth (1878). "Theoremes sur les nombres premiers". Comptes rendus de l'Académie des Sciences de Paris. 87: 926.
8. Leonard Eugene Dickson (1966). History of the Theory of Numbers. Vol. 1. New York, NY: Chelsea. p. 92.

External links

• Weisstein, Eric W. "Proth's Theorem". MathWorld .