# Proth prime

A Proth prime^{} 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 -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\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 |
---|---|

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 |