În teoria numerelor, teorema lui Proth este un test de primalitate pentru numerele lui Proth .
Teorema lui Proth spune:
Dacă p este un număr Prota de forma , unde k este impar și , atunci p este prim (numit prim Prota ) dacă și numai dacă pentru un nerezidu pătratic a se face comparația: |
(a) Fie p prim. Atunci pentru orice nerezidu pătratic a : după criteriul lui Euler .
(b) Fie pentru unele nereziduuri pătratice a . Folosim criteriul Pocklington , unde . Atunci este singurul divizor prim . Să verificăm îndeplinirea condițiilor criteriului:
Deoarece condiția este îndeplinită, n este prim. [unu]
Teorema lui Proth poate fi folosită pentru a testa primalitatea numerelor Proth. Algoritmul de testare probabilistică bazat pe teoremă este următorul: Un număr întreg este selectat aleatoriu astfel încât și calculează . Sunt posibile următoarele rezultate:
Rezultatul (4) este motivul pentru care testul este probabilist. În cazul (1) , este un modulo patratic nereziduu . Procedura se repetă până când se stabilește simplitatea. Dacă este prim, atunci testul va confirma acest lucru cu o probabilitate într-o iterație, deoarece numărul de nereziduuri patratice modulo este exact . [2]
Primele Prot formează o secvență:
3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449, 577, 641, 673, 769, 929, 1153 secvența … ( OE8007 )Din mai 2017, cel mai mare prim cunoscut al lui Proth, 10223 2 31172165 + 1, a fost găsit de proiectul Primegrid . Are 9383761 de cifre zecimale și este cel mai mare prim non-Mersenne cunoscut . [3]
Lema. Fie pentru unele prime l și . Fie puterea unui număr prim, unde . Dacă și , atunci n este prim .
Dovada. este un divizor , deci . Dacă , atunci este o contradicție. Prin urmare , și este simplu.Teoremă (teorema lui Proth generalizată). Lăsați câteva numere prime și întregi . Lasă . Dacă și pentru un număr întreg , atunci este prim.
Dovada teoremei generalizate poate fi găsită în Sze [4] .
François Prot (1852-1879) a publicat teorema în jurul anului 1878.