# Proth prime

A is a Proth number that is also a prime number. Given a Proth number $p$, if one can find a coprime integer $b$ such that

 $b^{\frac{p-1}{2}}\equiv-1\mod p$

then $p$ is a prime, and specifically a Proth prime (this is a theorem first stated by François Proth). Thanks to this theorem, Yves Gallot created an algorithm used in a primality-testing program employed by the Seventeen or Bust project. The first few Proth primes are 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, etc. (listed in A080076 of Sloane’s OEIS). Konstantin Agafonov’s discovery of the Proth prime $19249\times 2^{13018586}+1\approx 1.484360328715661\times 10^{3918989}$ currently makes for the largest known prime that is not a Mersenne prime.

Title Proth prime ProthPrime 2013-03-22 17:21:11 2013-03-22 17:21:11 PrimeFan (13766) PrimeFan (13766) 7 PrimeFan (13766) Definition msc 11A51