Contents

Proth's theorem

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

then pisprime. In this case p is called a Proth prime. This is a practical test because if p is prime, any chosen a has about a 50 percent chance of working, furthermore, since the calculation is mod p, only values of a smaller than p have to be taken into consideration.

In practice, however, a quadratic nonresidueofp is found via a modified Euclid's algorithm^{[citation needed]} 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 symbolis

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

Thus, in contrast to many Monte Carlo primality tests (randomized algorithms that can return a false positive), the primality testing algorithm based on Proth's theorem is a Las Vegas algorithm, always returning the correct answer but with a running time that varies randomly. Note that if a is chosen to be a quadratic nonresidue as described above, the runtime is constant, save for the time spent on finding such a quadratic nonresidue. Finding such a value is very fast compared to the actual test.

Numerical examples[edit]

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 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 11-th 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]

Proof[edit]

The proof for this theorem uses the Pocklington-Lehmer primality test, and 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[edit]

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

See also[edit]

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

References[edit]

External links[edit]

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