Prothin alkuluku

Lukuteoriassa Prothin luku on muotoa $k \cdot 2^{n} + 1$ oleva alkuluku, missä $k$ on pariton, $n$ positiivinen kokonaisluku ja $2^{n} > k$ . Fermat'n lukujen tekijät ovat Prothin lukuja mikäli $k$ on pariton ja $k < 2^{n}$ .

Prothin alkuluvut toteuttavat Prothin lauseen, jonka mukaan annettu luku muotoa $N = k \cdot 2^{n} + 1$ , missä $k$ on pariton, $n$ positiivinen kokonaisluku ja $2^{n} > k$ on alkuluku jos ja vain jos on olemassa kokonaisluku $a$ , jolle $a^{\frac{N - 1}{2}} \equiv - 1 (\mod N)$ . Tämä lause tarjoaa nopean tavan testata lukuja Prothin alkuluvuiksi.

Esimerkkejä

Jos p = 3, 2¹ + 1 = 3 on jaollinen luvulla 3, joten 3 on alkuluku.
Jos p = 5, 3² + 1 = 10 on jaollinen luvulla 5, joten 5 on alkuluku.
Jos p = 13, 5⁶ + 1 = 15626 on jaollinen luvulla 13, joten 13 on alkuluku.
Jos p = 9 (joka ei ole alkuluku), ei ole olemassa sellaista lukua a, niin että a⁴ + 1 on jaollinen luvulla 9.

Muutama ensimmäinen Prothin alkuluku A080076 OEIS-tietokannassa:

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153

Suurin tunnettu Prothin alkuluku on Seventeen or Bust -projektin löytämä 19249 · 2^13018586 + 1. Siinä on 3918990 numeroa ja se on suurin tunnettu alkuluku joka ei ole Mersennen alkuluku.

Lähteet

↑ http://primes.utm.edu/top20/page.php?id=3

[1] ttp://primes.utm.edu/top20/page.php?id=3