I talteorien er Proths sætning en primalitetstest for Proths tal .
Proths sætning siger:
Hvis p er et Prota-tal af formen , hvor k er ulige og , så er p primtal (kaldet en Prota-primtal ), hvis og kun hvis sammenligningen foretages for en anden kvadratisk ikke-rest a : |
(a) Lad p være primtal. Derefter for enhver kvadratisk ikke-rest a : ved Eulers kriterium .
(b) Lad for nogle kvadratiske ikke-rest a . Vi bruger Pocklington-kriteriet , hvor . Så er den eneste prime divisor . Lad os kontrollere opfyldelsen af betingelserne for kriteriet:
Da betingelsen er opfyldt, er n primtal. [en]
Proths teorem kan bruges til at teste for primaliteten af Proth-tal. Den probabilistiske testalgoritme baseret på sætningen er som følger: Et heltal vælges tilfældigt , således at og beregner . Følgende resultater er mulige:
Udfald (4) er årsagen til, at testen er sandsynlig. I tilfælde (1) er det en kvadratisk ikke-restmodulo . Proceduren gentages, indtil enkelheden er etableret. Hvis er prime, så vil testen bekræfte dette med en sandsynlighed i én iteration, da antallet af kvadratiske ikke-rester modulo er nøjagtigt . [2]
Prot-primtallene danner en sekvens:
3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449, 577, 641, 673, 769, 929, 1153 A0) ( 8 OEIS sekvens 6 )Fra maj 2017 er Proths største kendte prime, 10223 2 31172165 + 1, blevet fundet af Primegrid- projektet . Den har 9383761 decimalcifre og er den største kendte ikke- Mersenne primtal . [3]
Lemma. Lad for nogle prime l og . Lad være magten af et primtal, hvor . Hvis og , så er n primtal .
Bevis. er en divisor , så . Hvis , så er det en selvmodsigelse. Derfor , og er enkel.Sætning (generaliseret Proths sætning). Lad os for nogle primtal og heltal . Lad . Hvis og for et eller andet heltal , så er primtal.
Beviset for den generaliserede sætning kan findes i Sze [4] .
François Prot (1852-1879) udgav teoremet omkring 1878.