I talteorin är Proths sats ett primatitetstest för Proths tal .
Proths teorem säger:
Om p är ett Prota-tal av formen , där k är udda och , då är p primtal (kallat ett Prota-primtal ) om och endast om jämförelsen görs för någon kvadratisk icke-rest a : |
(a) Låt p vara primtal. Sedan för varje kvadratisk icke-rest a : enligt Eulers kriterium .
(b) Låt för någon kvadratisk icke-rest a . Vi använder Pocklington-kriteriet , där . Då är den enda primtalsdivisorn . Låt oss kontrollera uppfyllandet av villkoren för kriteriet:
Eftersom villkoret är uppfyllt är n primtal. [ett]
Proths sats kan användas för att testa primaliteten hos Proth-tal. Den probabilistiska testalgoritmen baserad på teoremet är följande: Ett heltal väljs slumpmässigt så att och beräknar . Följande resultat är möjliga:
Utfall (4) är anledningen till att testet är probabilistiskt. I fall (1) är det en kvadratisk icke-rester modulo . Proceduren upprepas tills enkelheten är etablerad. Om är primtal, kommer testet att bekräfta detta med en sannolikhet i en iteration, eftersom antalet kvadratiska icke-rester modulo är exakt . [2]
Prot-primtalen bildar en sekvens:
3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449 , 577 , 641 , 673 , 769 , 929 , 1153 , 1153 A0 ... ( 8 00IS sekvens 6 )I maj 2017 har Proths största kända prime, 10223 2 31172165 + 1, hittats av Primegrid- projektet . Den har 9383761 decimalsiffror och är den största kända icke- Mersenne primtal . [3]
Lemma. Låt för några prime l och . Låta vara makten av ett primtal, där . Om och , då är n primtal .
Bevis. är en divisor , så . Om , då är en motsägelse. Därför och är enkel.Sats (generaliserad Proths sats). Låt för några primtal och heltal . Låt . Om och för något heltal , då är primtal.
Beviset för den generaliserade satsen finns i Sze [4] .
François Prot (1852-1879) publicerade satsen omkring 1878.