Proth prime


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

bp-12-1modp

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×213018586+11.484360328715661×103918989 currently makes for the largest known prime that is not a Mersenne primeMathworldPlanetmath.

Title Proth prime
Canonical name ProthPrime
Date of creation 2013-03-22 17:21:11
Last modified on 2013-03-22 17:21:11
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 7
Author PrimeFan (13766)
Entry type Definition
Classification msc 11A51