A számelméletben a Proth-tétel a Proth - számok elsődlegességi tesztje .
Proth tétele ezt mondja:
Ha p egy formájú Prota-szám , ahol k páratlan és , akkor p prím (úgynevezett Prota prím ) akkor és csak akkor, ha valamilyen a másodfokú nem-maradékra az összehasonlítást elvégezzük: |
(a) Legyen p prím. Ezután bármely a másodfokú nem-maradékra : az Euler-kritérium szerint .
(b) Legyen valamely másodfokú nem-maradékra a . A Pocklington-kritériumot használjuk , ahol . Ekkor az egyetlen prímosztó . Ellenőrizzük a kritérium feltételeinek teljesülését:
Mivel a feltétel teljesül, n prím. [egy]
A Proth-tétel felhasználható a Proth-számok elsődlegességének tesztelésére. A tételen alapuló valószínűségi vizsgálati algoritmus a következő: Egy egész számot véletlenszerűen választunk ki úgy, hogy és kiszámítja . A következő eredmények lehetségesek:
Az eredmény (4) az oka annak, hogy a teszt valószínűségi. Az (1) esetben ez egy másodfokú nem maradék modulo . Az eljárást addig ismételjük, amíg az egyszerűség létre nem jön. Ha prím, akkor a teszt ezt egy iterációval valószí- nűséggel megerősíti, mivel a másodfokú nem maradékok száma modulo pontosan . [2]
A Prot prímek sorozatot alkotnak:
3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449, 577, 641, 673, 769, 929, 1153…0 ( OEIS6 A sorozat )2017 májusában a Proth legnagyobb ismert prímszámát, a 10223 2 31172165 + 1-et a Primegrid projekt találta meg . 9383761 tizedesjegyből áll, és a legnagyobb ismert nem Mersenne-prím . [3]
Lemma. Legyen néhány prím l és . Legyen egy prímszám hatványa, ahol . Ha és , akkor n prím .
Bizonyíték. egy osztó , tehát . Ha , akkor ez ellentmondás. Ezért , és egyszerű.Tétel (általánosított Proth-tétel). Legyen néhány prím és egész szám . Hadd . Ha és valamilyen egész számra , akkor a prím.
Az általánosított tétel bizonyítása Sze [4]-ben található .
François Prot (1852-1879) 1878 körül publikálta a tételt.