AProth number is anatural numberN of the form${\displaystyle N=k\times 2^n+1}$ wherek andn are positiveintegers,k isodd and${\displaystyle 2^n>k}$. AProth prime is a Proth number that isprime. They are named after the French mathematicianFrançois Proth.^[2] The first few Proth primes are

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857 (OEIS: A080076).

It is still an open question whether an infinite number of Proth primes exist. It was shown in 2022 that the reciprocal sum of Proth primes converges to a real number near 0.747392479, substantially less than the value of 1.093322456 for the reciprocal sum of Proth numbers.^[1]

The primality of Proth numbers can be tested more easily than many other numbers of similar magnitude.

A Proth number takes the form${\displaystyle N=k\times 2^n+1}$ wherek andn are positive integers,${\displaystyle k}$ is odd and${\displaystyle 2^n>k}$. A Proth prime is a Proth number that is prime.^[2][3] Without the condition that${\displaystyle 2^n>k}$, all odd integers larger than 1 would be Proth numbers.^[4]

The primality of a Proth number can be tested withProth's theorem, which states that a Proth number${\displaystyle p}$ is prime if and only if there exists an integer${\displaystyle a}$ for which

${\displaystyle a^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p).}$^[3][5]

This theorem can be used as a probabilistic test of primality, by checking for many random choices of${\displaystyle a}$ whether${\displaystyle a^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p).}$ If this fails to hold for several random${\displaystyle a}$, then it is very likely that the number${\displaystyle p}$ iscomposite.^{[citation needed]}This test is aLas Vegas algorithm: it never returns afalse positive but can return afalse negative; in other words, it never reports a composite number as "probably prime" but can report a prime number as "possibly composite".

In 2008, Sze created adeterministic algorithm that runs in at most${\displaystyle \tilde{O}((k\log k+\log N)(\log N{)}^2)}$ time, where Õ is thesoft-O notation. For typical searches for Proth primes, usually${\displaystyle k}$ is either fixed (e.g. 321 Prime Search or Sierpinski Problem) or of order${\displaystyle O(\log N)}$ (e.g. Cullen prime search). In these cases algorithm runs in at most${\displaystyle \tilde{O}((\log N{)}^3)}$, or${\displaystyle O((\log N{)}^{3+ϵ})}$ time for all${\displaystyle ϵ>0}$. There is also an algorithm that runs in${\displaystyle \tilde{O}((\log N{)}^{24/7})}$ time.^[2][6]

Fermat numbers are a special case of Proth numbers, whereink=1. In such a scenarioPépin's test proves that only basea=3 need to be checked to deterministically verify or falsify the primality of a Fermat number.

As of 2022^[update], the largest known Proth prime is${\displaystyle 10223\times 2^{31172165}+1}$. It is 9,383,761 digits long.^[7] It was found by Szabolcs Peter in thePrimeGrid volunteer computing project which announced it on 6 November 2016.^[8] It is also the third largest known non-Mersenne prime.^[9]

The projectSeventeen or Bust, searching for Proth primes with a certain${\displaystyle t}$ to prove that 78557 is the smallestSierpinski number (Sierpinski problem), has found 11 large Proth primes by 2007. Similar resolutions to theprime Sierpiński problem andextended Sierpiński problem have yielded several more numbers.

Since divisors ofFermat numbers${\displaystyle F_n=2^{2^n}+1}$ are always of the form${\displaystyle k\times 2^{n+2}+1}$, it is customary to determine if a new Proth prime divides a Fermat number.^[10]

As of January 2025,PrimeGrid is the leading computing project for searching for Proth primes. Its main projects include:

• general Proth prime search
• 321 Prime Search (searching for primes of the form${\displaystyle 3\times 2^n+1}$, also calledThabit primes of the second kind)
• 27121 Prime Search (searching for primes of the form${\displaystyle 27\times 2^n+1}$ and${\displaystyle 121\times 2^n+1}$)
• Cullen prime search (searching for primes of the form${\displaystyle n\times 2^n+1}$)
• Sierpinski problem (and their prime and extended generalizations) – searching for primes of the form${\displaystyle k\times 2^n+1}$ wherek is in this list:

k ∈ {21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 209611, 222113, 225931, 227723, 229673, 237019, 238411}

As of June 2023, the largest Proth primes discovered are:^[11]

AProth number of the second kind is anatural numberN of the form${\displaystyle N=k\times 2^n-1}$ wherek andn are positiveintegers,k isodd and${\displaystyle 2^n>k}$. AProth prime of the second kind is a Proth number of the second kind that isprime. The first few Proth primes of the second kind are

3, 7, 11, 23, 31, 47, 79, 127, 191, 223, 239, 383, 479, 607, 863, 991, 1087, 1151, 1279, 1471, 1663, 2111, 2239, 2687, 2879, 3391, 3583, 3967, 5119, 5503, 6143, 6271, 6911, 7039, 8191, 8447, 8831, 9343 (OEIS: A112715).

The largest Proth primes of the second kind can be primality testing use theLucas–Lehmer–Riesel test.

As of January 2025,PrimeGrid is the leading computing project for searching for Proth primes of the second kind. Its main projects include:

• general Proth prime of the second kind search
• 321 Prime Search (searching for primes of the form${\displaystyle 3\times 2^n-1}$, also calledThabit primes)
• 27121 Prime Search (searching for primes of the form${\displaystyle 27\times 2^n-1}$ and${\displaystyle 121\times 2^n-1}$)
• Woodall prime search (searching for primes of the form${\displaystyle n\times 2^n-1}$)
• Riesel problem (and their prime and extended generalizations) – searching for primes of the form${\displaystyle k\times 2^n-1}$ wherek is in this list:

k ∈ {23669, 31859, 38473, 46663, 67117, 74699, 81041, 121889, 129007, 143047, 161669, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 485557, 494743 }

Small Proth primes (less than 10²⁰⁰) have been used in constructing prime ladders, sequences of prime numbers such that each term is "close" (within about 10¹¹) to the previous one. Such ladders have been used to empirically verify prime-relatedconjectures. For example,Goldbach's weak conjecture was verified in 2008 up to 8.875 × 10³⁰ using prime ladders constructed from Proth primes.^[18] (The conjecture was later proved byHarald Helfgott.^{[19][20][better source needed]})

Also, Proth primes can optimizeden Boer reduction between theDiffie–Hellman problem and theDiscrete logarithm problem. The prime number 55 × 2²⁸⁶ + 1 has been used in this way.^[21]

As Proth primes have simplebinary representations, they have also been used in fast modular reduction without the need for pre-computation, for example byMicrosoft.^[22]

• Classes of prime numbers
• Eponymous numbers in mathematics

• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from December 2019
• Articles containing potentially dated statements from 2022
• All articles containing potentially dated statements
• All articles lacking reliable references
• Articles lacking reliable references from December 2019