Lukuteoriassa Prothin lause on Prothin lukujen primaalisuustesti .
Prothin lause sanoo:
Jos p on muodon Prota-luku , jossa k on pariton ja , niin p on alkuluku (kutsutaan Prota-alkuluvuksi ) silloin ja vain, jos vertailu suoritetaan jollekin neliölliselle ei-jäännökselle a : |
(a) Olkoon p alkuluku. Sitten mille tahansa neliölliselle ei-jäännökselle a : Eulerin kriteerillä .
(b) Olkoon jollekin neliölliselle ei-jäännökselle a . Käytämme Pocklingtonin kriteeriä , jossa . Sitten on ainoa alkujakaja . Tarkastellaan kriteerin ehtojen täyttymistä:
Koska ehto täyttyy, n on alkuluku. [yksi]
Prothin teoreemaa voidaan käyttää Proth-lukujen primaalisuuden testaamiseen. Lauseen perustuva todennäköisyystestausalgoritmi on seuraava: Kokonaisluku valitaan satunnaisesti siten, että ja laskee . Seuraavat tulokset ovat mahdollisia:
Tulos (4) on syy, miksi testi on todennäköisyys. Tapauksessa (1) se on neliöllinen ei-jäännösmoduuli . Toimenpide toistetaan, kunnes yksinkertaisuus on todettu. Jos on alkuluku, niin testi vahvistaa tämän todennäköisyydellä yhdessä iteraatiossa, koska neliöllisten ei-jäännösten lukumäärä modulo on täsmälleen . [2]
Prot-alkuluvut muodostavat sekvenssin:
3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449, 577, 641, 673, 769, 929, 1153… 0 ( OEIS6 A )Toukokuusta 2017 lähtien Prothin suurin tunnettu alkuluku, 10223 2 31172165 + 1, on löydetty Primegrid- projektista . Siinä on 9383761 desimaalilukua ja se on suurin tunnettu ei- Mersennen alkuluku . [3]
Lemma. Anna jonkin verran prime l ja . Antaa olla valta alkuluku, jossa . Jos ja , niin n on alkuluku .
Todiste. on jakaja , joten . Jos , niin on ristiriita. Siksi ja on yksinkertainen.Lause (yleistetty Prothin lause). Olkoon joitakin alkulukuja ja kokonaislukuja . Anna . Jos ja jollekin kokonaisluvulle , niin on alkuluku.
Yleistetyn lauseen todistus löytyy julkaisusta Sze [4] .
François Prot (1852-1879) julkaisi lauseen noin 1878.