Proth's theorem
સંખ્યા સિદ્ધાંતમાં, પ્રથમ પ્રમેય એ પ્રથમ સંખ્યાઓ માટે પ્રાથમિકતાની કસોટી છે. તે જણાવે છે કે જો p એ k વિષમ અને k <2n સાથે k2n + 1 સ્વરૂપની પ્રથમ સંખ્યા છે, અને જો ત્યાં એક પૂર્ણાંક a અસ્તિત્વમાં છે જેના માટે p અવિભાજ્ય છે. આ કિસ્સામાં p ને પ્રોથ પ્રાઇમ કહેવામાં આવે છે. આ એક વ્યવહારુ કસોટી છે કારણ કે જો p એ અવિભાજ્ય છે, તો કોઈપણ પસંદ કરેલ a પાસે કામ કરવાની લગભગ 50 ટકા તક હોય છે, વધુમાં, ગણતરી મોડ p હોવાથી, p કરતા નાના મૂલ્યોને જ ધ્યાનમાં લેવા પડશે. વ્યવહારમાં, જો કે, p નું વર્ગાત્મક બિન-અવશેષ સંશોધિત યુક્લિડના અલ્ગોરિધમ દ્વારા જોવા મળે છે અને a ના મૂલ્ય તરીકે લેવામાં આવે છે, કારણ કે જો a એ વર્ગાત્મક બિન-અવશેષ મોડ્યુલો p હોય તો વિપરીત પણ સાચું છે, અને પરીક્ષણ નિર્ણાયક છે. આમ, ઘણા મોન્ટે કાર્લો પ્રાથમિક પરીક્ષણો (રેન્ડમાઇઝ્ડ અલ્ગોરિધમ્સ કે જે ફોલ્સ પોઝિટિવ પરત કરી શકે છે) થી વિપરીત, પ્રથમ સિદ્ધાંત પર આધારિત પ્રાથમિક પરીક્ષણ અલ્ગોરિધમ લાસ વેગાસ અલ્ગોરિધમ છે, જે હંમેશા સાચો જવાબ આપે છે પરંતુ ચાલી રહેલા સમય સાથે જે અવ્યવસ્થિત રીતે બદલાય છે. નોંધ લો કે જો a ને ઉપર વર્ણવ્યા મુજબ દ્વિઘાત બિન-અવશેષ તરીકે પસંદ કરવામાં આવે છે, તો રનટાઇમ સ્થિર છે, આવા દ્વિઘાત બિન-અવશેષ શોધવા માટે વિતાવેલા સમય માટે સલામત છે. વાસ્તવિક પરીક્ષણની સરખામણીમાં આવું મૂલ્ય શોધવું ખૂબ જ ઝડપી છે. આંકડાકીય ઉદાહરણો પ્રમેયના ઉદાહરણોમાં નીચેનાનો સમાવેશ થાય છેઃ p = 3 = 1 (21) + 1 માટે, આપણી પાસે 2 (3-1)/2 + 1 = 3 એ 3 વડે વિભાજ્ય છે, તેથી 3 એ અવિભાજ્ય છે. p = 5 = 1 (22) + 1 માટે, આપણી પાસે 3 (5-1)/2 + 1 = 10 એ 5 વડે વિભાજ્ય છે, તેથી 5 એ અવિભાજ્ય છે. p = 13 = 3 (22) + 1 માટે, આપણી પાસે 5 (13-1)/2 + 1 = 15626 એ 13 વડે વિભાજ્ય છે, તેથી 13 એ અવિભાજ્ય છે. p = 9 માટે, જે અવિભાજ્ય નથી, એવું કોઈ a નથી કે a (9-1)/2 + 1 એ 9 વડે વિભાજીત થાય. પ્રથમ પ્રથમ સંખ્યાઓ છેઃ 3,5,13,17,41,97,113,193,241,257,353,449,577,641,673,769,929,1153. સૌથી મોટો જાણીતો પ્રથમ અવિભાજ્ય છે, અને તે 9,383,761 અંકો લાંબો છે. તે પીટર સ્ઝાબોલ્ક્સ દ્વારા પ્રાઇમગ્રિડ સ્વયંસેવક કમ્પ્યુટિંગ પ્રોજેક્ટમાં મળી આવ્યું હતું, જેણે 6 નવેમ્બર 2016ના રોજ તેની જાહેરાત કરી હતી. તે સૌથી મોટી જાણીતી નોન-મર્સેન પ્રાઇમ અને સૌથી મોટી કોલ્બર્ટ સંખ્યા પણ છે. બીજો સૌથી મોટો જાણીતો પ્રથમ અવિભાજ્ય છે, જે પ્રાઇમગ્રિડ દ્વારા મળી આવ્યો છે. પુરાવો આ પ્રમેય માટેનો પુરાવો પોકલિંગ્ટન-લેહમર પ્રાથમિકતા પરીક્ષણનો ઉપયોગ કરે છે, અને પેપિનના પરીક્ષણના પુરાવો સાથે નજીકથી મેળ ખાય છે. પુરાવા સંદર્ભોમાં રિબેનબોઇમ દ્વારા પુસ્તકના પાન 52 પર મળી શકે છે. ઇતિહાસ ફ્રાન્કોઇસ પ્રોથ (1852-1879) એ 1878માં આ પ્રમેય પ્રકાશિત કર્યો હતો. પેપિન્સ ટેસ્ટ (વિશેષ કેસ k = 1, જ્યાં કોઈ a = 3 પસંદ કરે છે) પણ જુઓ.