Prothin alkuluku

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

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