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ä.