Proth prime number

Proth prime numbers are prime numbers of the form , where are positive integers , as well as odd and . Such numbers are generally called Proth numbers , even if they are not prime numbers. ${\displaystyle k\cdot 2^{n}+1}$ ${\displaystyle k,n\in \mathbb {N} }$ ${\displaystyle k\ }$ ${\displaystyle k<2^{n}\ }$

useful information

Every prime number can be clearly written in the form with odd . If it then applies , it is a Proth prime number. ${\displaystyle k}$ ${\displaystyle k\cdot 2^{n}+1}$ ${\displaystyle k<2^{n}\ }$

The significance of the Proth primes lies in the fact that François Proth (1852–1879) found a simple test (the Proth theorem) that can be used to prove whether Proth numbers are prime numbers. Many of the currently largest known prime numbers were found with this test and there is a freely available program by Yves Gallot which implements the Proth theorem and is often used for such purposes.

The Proth theorem says: The Proth number is prime if there is a natural number with: ${\displaystyle N}$ ${\displaystyle a}$

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

The Proth primes also play a role in the Sierpiński numbers insofar as a sequence of numbers of the form must be free from Proth primes for a Sierpiński number to be. ${\displaystyle k\cdot 2^{n}+1\ }$ ${\displaystyle k\ }$

Among the Proth primes there are also Cullen primes . These are prime numbers of the form . ${\displaystyle n\cdot 2^{n}+1}$

In the following table you can find prime numbers sorted up to 10,000,000. Prime numbers with , which are not Proth's prime numbers, are in brackets. Proth primes with are also called Fermat primes . ${\displaystyle k}$ ${\displaystyle k>2^{n}\ }$ ${\displaystyle k=1}$

Primes to orderly ${\displaystyle N}$ ${\displaystyle k}$
k	shape	Prime numbers of this form	episode	gives prime numbers for n =	episode
01	${\displaystyle 1\cdot 2^{n}+1}$	3, 5, 17, 257, 65537 (no other known)	Follow A019434 in OEIS	1, 2, 4, 8, 16 (no other known)	-
03	${\displaystyle 3\cdot 2^{n}+1}$	(7), 13, 97, 193, 769, 12289, 786433, 3221225473, ...	Follow A039687 in OEIS	(1), 2, 5, 6, 8, 12, 18, 30, 36, 41, ...	Follow A002253 in OEIS
05	${\displaystyle 5\cdot 2^{n}+1}$	(11), 41, 641, 163841, ...	-	(1), 3, 7, 13, 15, 25, 39, 55, 75, 85, ...	Follow A002254 in OEIS
07th	${\displaystyle 7\cdot 2^{n}+1}$	(29), 113, 449, 114689, 7340033, 469762049, ...	Follow A050527 in OEIS	(2), 4, 6, 14, 20, 26, 50, 52, 92, 120, ...	Follow A032353 in OEIS
09	${\displaystyle 9\cdot 2^{n}+1}$	(19), (37), (73), 577, 1153, 18433, 147457, 1179649, ...	Follow A050528 in OEIS	(1), (2), (3), 6, 7, 11, 14, 17, 33, 42, 43, ...	Follow A002256 in OEIS
11	${\displaystyle 11\cdot 2^{n}+1}$	(23), (89), 353, 1409, 5767169, 23068673, ...	Follow A050529 in OEIS	(1), (3), 5, 7, 19, 21, 43, 81, 125, 127, ...	Follow A002261 in OEIS
13	${\displaystyle 13\cdot 2^{n}+1}$	(53), 3329, 13313, 13631489, 3489660929, ...	Follow A300406 in OEIS	(2), 8, 10, 20, 28, 82, 188, 308, 316, ...	Follow A032356 in OEIS
15th	${\displaystyle 15\cdot 2^{n}+1}$	(31), (61), 241, 7681, 15361, 61441, 2013265921, ...	Follow A195745 in OEIS	(1), (2), 4, 9, 10, 12, 27, 37, 38, 44, 48, ...	Follow A002258 in OEIS
17th	${\displaystyle 17\cdot 2^{n}+1}$	(137), 557057, 2281701377, ...	Follow A300407 in OEIS	(3), 15, 27, 51, 147, 243, 267, 347, ...	Follow A002259 in OEIS
19th	${\displaystyle 19\cdot 2^{n}+1}$	1217, 19457, 1337006139375617, ...	Follow A300408 in OEIS	6, 10, 46, 366, 1246, 2038, 4386, ...	Follow A032359 in OEIS
21st	${\displaystyle 21\cdot 2^{n}+1}$	(43), (337), 673, 2689, 10753, ...	-	(1), (4), 5, 7, 9, 12, 16, 17, 41, 124, ...	Follow A032360 in OEIS
23	${\displaystyle 23\cdot 2^{n}+1}$	(47), 11777, ...	-	(1), 9, 13, 29, 41, 49, 69, 73, 341, ...	Follow A032361 in OEIS
...	...	...	...	...	...

The first Proth numbers up to 500 are:

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, ... (sequence A080075 in OEIS )

The first Proth prime numbers up to 1000 are:

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, ... (sequence A080076 in OEIS )

Examples

Example 1: (Proth prime number)

Be and Then is a Proth number because and is odd . ${\displaystyle k:=3}$ ${\displaystyle n:=2.}$ ${\displaystyle N=k\cdot 2^{n}+1=3\cdot 2^{2}+1=13}$ ${\displaystyle k=3}$ ${\displaystyle 3=k<2^{n}=2^{2}=4}$

${\displaystyle N=13}$is a Proth prime number if there is a natural number such that . So you try all the numbers until you find a suitable one : ${\displaystyle a\in \mathbb {N} }$ ${\displaystyle a^{\frac {N-1}{2}}=a^{\frac {13-1}{2}}=a^{6}\equiv -1{\pmod {13}}}$ ${\displaystyle a}$

${\displaystyle {\begin{aligned}1^{\frac {13-1}{2}}&=&1^{6}&=&1&&&\equiv &1{\pmod {13}}\\2^{\frac {13-1}{2}}&=&2^{6}&=&64&=&5\cdot 13-1&\equiv &-1{\pmod {13}}\end{aligned}}}$

Thus, right at the beginning, a suitable one has been found that proves that a Proth number is a prime. Also are suitable numbers for this proof. ${\displaystyle a=2}$ ${\displaystyle N=13}$ ${\displaystyle a=5,6,7,8,11}$

Example 2: (prime number, but not a Proth prime number)

Be and Then is not a Proth number because it is odd, but is. It is a prime number, but not a Proth prime number. ${\displaystyle k:=3}$ ${\displaystyle n:=1.}$ ${\displaystyle N=k\cdot 2^{n}+1=3\cdot 2^{1}+1=7}$ ${\displaystyle k=3}$ ${\displaystyle 3=k\not <2^{n}=2^{1}=2}$ ${\displaystyle N=7}$

Example 3: (not a prime number)

Be and Then is a Proth number because and is odd . ${\displaystyle k:=5}$ ${\displaystyle n:=4.}$ ${\displaystyle N=k\cdot 2^{n}+1=5\cdot 2^{4}+1=81}$ ${\displaystyle k=5}$ ${\displaystyle 5=k<2^{n}=2^{4}=16}$

${\displaystyle N=81}$is a Proth prime number if there is a natural number such that . So you try all the numbers again until you find a suitable one : ${\displaystyle a\in \mathbb {N} }$ ${\displaystyle a^{\frac {N-1}{2}}=a^{\frac {81-1}{2}}=a^{40}\equiv -1{\pmod {81}}}$ ${\displaystyle a}$

${\displaystyle {\begin{aligned}1^{\frac {81-1}{2}}&=&1^{40}&=&1&\equiv \ &1{\pmod {81}}\\2^{\frac {81-1}{2}}&=&2^{40}&=&1.099.511.627.776&\equiv \ &70{\pmod {81}}\\3^{\frac {81-1}{2}}&=&3^{40}&=&&\equiv \ &0{\pmod {81}}\\4^{\frac {81-1}{2}}&=&4^{40}&=&&\equiv \ &40{\pmod {81}}\\5^{\frac {81-1}{2}}&=&5^{40}&=&&\equiv \ &4{\pmod {81}}\end{aligned}}}$

Similarly, none of the others can be found suitable that fulfills the condition . Of course there are calculation rules for the modulo calculations so that you can avoid high numbers. ${\displaystyle a}$ ${\displaystyle a^{\frac {81-1}{2}}\equiv -1{\pmod {81}}}$

Thus the proof has been furnished that there is no Proth prime number (which was actually clear from the start, there is). ${\displaystyle N=81}$ ${\displaystyle N=3\cdot 3\cdot 3\cdot 3}$

Largest known Proth primes

The three largest known Proth primes are as follows:

rank	Prime number	Decimal places	other properties	Discovery date	Explorer	Project	source
1	${\displaystyle 10223\cdot 2^{31172165}+1}$	9,383,761	largest prime number that simultaneously not Mersenne prime is largest Colbert number that evidence no Sierpinski number is ${\displaystyle k=10223}$	October 31, 2016	Péter Szabolcs ( HUN )	Seventeen or Bust
2	${\displaystyle 168451\cdot 2^{19375200}+1}$	5,832,522	Proof that no prime Sierpinski number is ${\displaystyle k=168451}$	17th September 2017	Ben Maloney ( AUS )	Prime Sierpinski Project
3	${\displaystyle 99739\cdot 2^{14019102}+1}$	4,220,176	Proof that not the second smallest Sierpinski number, so no solution to the extended Sierpiński problem is ${\displaystyle k=99739}$	December 24, 2019	Brian D. Niegocki	Extended Sierpinski problem

Web links

• Eric W. Weisstein : Proth Prime . In: MathWorld (English).
• Yves Gallot's Proth.exe: an implementation of Proth's Theorem for Windows - program by Yves Gallot
• Proth Search Page
• Chris Caldwell: Proth prime on The Prime Pages
• List of primes k 2 ⁿ + 1 for k <300
• List of primes k 2 ⁿ + 1 for 300 <k <600
• Homepage of the internet project “Seventeen or Bust”
• Proth prime . In: PlanetMath . (English)

Individual evidence

1. ↑ Yves Gallot's Proth.exe: an implementation of Proth's Theorem for Windows. Retrieved December 5, 2015 . 
2. ↑ List of prime numbers ordered by k for k <300. Accessed December 5, 2015 . 
3. ↑ Chris Caldwell, The Top Twenty: Proth
4. ↑ Chris Caldwell, The Top Twenty: Largest Known Primes
5. ↑ 10223 · 2 ^31172165 + 1 on Prime Pages
6. ↑ 10223 · 2 ^31172165 + 1 on primegrid.com (PDF)
7. ↑ 168451 · 2 ^19375200 + 1 on Prime Pages
8. ↑ 168451 · 2 ^19375200 + 1 on primegrid.com (PDF)
9. ↑ 99739 · 2 ^14019102 + 1 on Prime Pages