Prothin teoreema

Prothin teoreema on lukuteoreettinen lause, jonka avulla voidaan testata, onko annettu Prothin luku alkuluku.

Jos ${\displaystyle p}$ on Prothin luku, eli muotoa ${\displaystyle k2^{n}+1}$, missä ${\displaystyle k}$ on pariton kokonaisluku ja ${\displaystyle k<2^{n}}$, ja on olemassa sellainen kokonaisluku ${\displaystyle a}$, että

${\displaystyle a^{(p-1)/2}\equiv -1{\pmod {p}}\,\!}$,

niin Prothin lauseen mukaan ${\displaystyle p}$ on alkuluku.

Tällaista alkulukua kutsutaan Prothin alkuluvuksi.

Prothin lause tarjoaa käytännöllisen menetelmän sen testaamiseksi, onko Prothin luku alkuluku. Jos nimittäin ${\displaystyle p}$ on alkuluku, umpimähkään valittu ${\displaystyle a}$ toimii noin 50 prosentin todennäköisyydellä.

• 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.^[1]

Ranskalainen matemaatikko François Proth (1852 - 1879) julkaisi teoreeman vuoden 1878 tienoilla.

• Sierpinskin luku

• Prothin teoreema MathWorld -matematiikkasivustolla