Proth's theorem
نمبر تھیوری میں، پروتھ تھیوریم پروتھ نمبروں کے لیے ایک پرائملٹی ٹیسٹ ہے۔ اس میں کہا گیا ہے کہ اگر p ایک پروتھ نمبر ہے، جس کی شکل k2n + 1 ہے جس میں k طاق اور k <2n ہے، اور اگر کوئی عدد a موجود ہے جس کے لیے p پرائم ہے۔ اس صورت میں p کو پروتھ پرائم کہا جاتا ہے۔ یہ ایک عملی امتحان ہے کیونکہ اگر p پرائم ہے، تو کسی بھی منتخب کردہ a کے کام کرنے کا تقریبا 50 فیصد امکان ہوتا ہے، اس کے علاوہ، چونکہ حساب موڈ p ہے، اس لیے p سے چھوٹے کی صرف اقدار کو مدنظر رکھنا پڑتا ہے۔ تاہم، عملی طور پر، پی کا ایک کواڈریٹک نان ریسیڈیو ایک ترمیم شدہ یوکلڈ کے الگورتھم کے ذریعے پایا جاتا ہے اور اسے اے کی قدر کے طور پر لیا جاتا ہے، کیونکہ اگر اے ایک کواڈریٹک نان ریسیڈیو ماڈیولو پی ہے تو اس کا الٹا بھی درست ہے، اور ٹیسٹ فیصلہ کن ہے۔ اس طرح، بہت سے مونٹی کارلو پرائمری ٹیسٹوں (بے ترتیب الگورتھم جو ایک غلط مثبت واپس کر سکتے ہیں) کے برعکس، پروتھ کے نظریہ پر مبنی پرائمری ٹیسٹنگ الگورتھم لاس ویگاس الگورتھم ہے، جو ہمیشہ صحیح جواب واپس کرتا ہے لیکن ایک رننگ ٹائم کے ساتھ جو بے ترتیب طور پر مختلف ہوتا ہے۔ نوٹ کریں کہ اگر a کو کواڈریٹک نان ریسیڈیو کے طور پر منتخب کیا گیا ہے جیسا کہ اوپر بیان کیا گیا ہے، تو رن ٹائم مستقل ہے، اس طرح کے کواڈریٹک نان ریسیڈیو کو تلاش کرنے میں گزارے گئے وقت کے لیے محفوظ ہے۔ اس طرح کی قیمت تلاش کرنا اصل ٹیسٹ کے مقابلے میں بہت تیز ہے۔ عددی مثالیں تھیوریم کی مثالوں میں شامل ہیں: p = 3 = 1 (21) + 1 کے لیے، ہمارے پاس ہے کہ 2 (3-1)/2 + 1 = 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 کا انتخاب کرتا ہے) سیرپنسکی نمبر حوالہ جات بیرونی لنکس پرائملٹی ٹیسٹ پرائم نمبروں کے بارے میں تھیوریمز ڈی: پروتھشے پرمزہل nl: پروتھجیٹل