Proth's theorem
সংখ্যা তত্ত্বে, প্রথম উপপাদ্য হল প্রথম সংখ্যার জন্য একটি প্রাথমিক পরীক্ষা। এটি বলে যে, যদি p একটি প্রথম সংখ্যা হয়, k2n + 1 আকারে k বিজোড় এবং k <2n সহ, এবং যদি একটি পূর্ণসংখ্যা 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 হল মৌলিক সংখ্যা। 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: প্রোথজেটাল