Proth number

In number theory, a Proth number, named after the mathematician François Proth, is a number of the form

${\displaystyle N=k\cdot 2^{n}+1}$

where $k$ is an odd positive integer and $n$ is a positive integer such that $2^n > k$. Without the latter condition, all odd integers greater than 1 would be Proth numbers.^[1]

The first Proth numbers are (sequence A080075 in the OEIS):

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, etc.

The Cullen numbers (n·2ⁿ+1) and Fermat numbers (2²ⁿ+1) are special cases of Proth numbers.

Proth primes

A Proth prime is a Proth number which is prime. The first Proth primes are ( A080076):

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.

The primality of a Proth number can be tested with Proth's theorem which states^[2] that a Proth number $p$ is prime if and only if there exists an integer $a$ for which the following is true:

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

The largest known Proth prime as of 2016 is ${\displaystyle 10223\cdot 2^{31172165}+1}$, and is 9,383,761 digits long.^[3] It was found by Szabolcs Peter in the PrimeGrid distributed computing project which announced it on 6 November 2016.^[4] It is also the largest known non-Mersenne prime.^[5]

See also

• Sierpinski number
• PrimeGrid – a distributed computing project searching for large Proth primes

References

1. Weisstein, Eric W. "Proth Number". MathWorld.
2. Weisstein, Eric W. "Proth's Theorem". MathWorld.
3. Chris Caldwell, The Top Twenty: Proth, from The Prime Pages.
4. "World Record Colbert Number discovered!".
5. Chris Caldwell, The Top Twenty: Largest Known Primes, from The Prime Pages.