Proth's theorem
संख्या सिद्धांत में, प्रथम की प्रमेय प्रथम संख्याओं के लिए एक प्राथमिक परीक्षण है। यह बताता है कि यदि p एक प्रथम संख्या है, तो k2n + 1 के रूप में k विषम और k <2n के साथ, और यदि कोई पूर्णांक a मौजूद है जिसके लिए p अभाज्य है। इस मामले में पी को प्रथम अभाज्य कहा जाता है। यह एक व्यावहारिक परीक्षण है क्योंकि यदि पी अभाज्य है, तो किसी भी चुने हुए ए में काम करने की लगभग 50 प्रतिशत संभावना होती है, इसके अलावा, क्योंकि गणना मॉड पी है, केवल पी से छोटे मूल्यों को ध्यान में रखा जाना चाहिए। व्यवहार में, हालांकि, पी का एक द्विघात गैर-अवशिष्ट एक संशोधित यूक्लिड के एल्गोरिथ्म के माध्यम से पाया जाता है और ए के मूल्य के रूप में लिया जाता है, क्योंकि यदि ए एक द्विघात गैर-अवशिष्ट मॉड्यूलो पी है तो विपरीत भी सही है, और परीक्षण निर्णायक है। इस तरह के लिए लीजेंड्रे प्रतीक है इस प्रकार, कई मोंटे कार्लो प्राथमिकता परीक्षणों (यादृच्छिक एल्गोरिदम जो एक गलत सकारात्मक वापस कर सकते हैं) के विपरीत, प्रथम प्रमेय पर आधारित प्राथमिकता परीक्षण एल्गोरिदम एक लास वेगास एल्गोरिदम है, जो हमेशा सही उत्तर देता है लेकिन एक चलने वाले समय के साथ जो यादृच्छिक रूप से बदलता है। ध्यान दें कि यदि a को ऊपर वर्णित एक द्विघात गैर-अवशेष के रूप में चुना जाता है, तो रनटाइम स्थिर है, इस तरह के द्विघात गैर-अवशेष को खोजने में बिताए गए समय के लिए सुरक्षित है। वास्तविक परीक्षण की तुलना में इस तरह के मूल्य का पता लगाना बहुत तेज़ है। संख्यात्मक उदाहरण प्रमेय के उदाहरणों में शामिल हैंः पी = 3 = 1 (21) + 1 के लिए, हमारे पास है कि 2 (3-1)/2 + 1 = 3 से विभाज्य है, इसलिए 3 अभाज्य है। पी = 5 = 1 (22) + 1 के लिए, हमारे पास है कि 3 (5-1)/2 + 1 = 10 5 से विभाज्य है, इसलिए 5 अभाज्य है। पी = 13 = 3 (22) + 1 के लिए, हमारे पास 5 (13-1)/2 + 1 = 15626 13 से विभाज्य है, इसलिए 13 अभाज्य है। पी = 9 के लिए, जो अभाज्य नहीं है, ऐसा कोई ए नहीं है कि ए (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 चुनता है) भी देखें।