Euclid's theorem
ইউক্লিডের উপপাদ্য সংখ্যা তত্ত্বের একটি মৌলিক বিবৃতি যা দাবি করে যে অসীম সংখ্যক মৌলিক সংখ্যা রয়েছে। ইউক্লিড তাঁর এলিমেন্টস গ্রন্থে এটি প্রথম প্রমাণ করেছিলেন। উপপাদ্যটির বেশ কয়েকটি প্রমাণ রয়েছে। ইউক্লিডের প্রমাণ ইউক্লিড তাঁর এলিমেন্টস (বুক IX, প্রপোসিশন 20) গ্রন্থে প্রকাশিত একটি প্রমাণ উপস্থাপন করেছেন, যা এখানে ব্যাখ্যা করা হয়েছে। মৌলিক সংখ্যা p1, p2,., pn-এর যে কোনও সসীম তালিকা বিবেচনা করুন। এটি দেখানো হবে যে এই তালিকায় নেই এমন কমপক্ষে একটি অতিরিক্ত মৌলিক সংখ্যা বিদ্যমান। ধরা যাক পি তালিকার সমস্ত মৌলিক সংখ্যার গুণফলঃ পি = p1p2.pn। ধরা যাক q = P + 1। তাহলে q হয় মৌলিক সংখ্যা অথবা নয়ঃ যদি q মৌলিক সংখ্যা হয়, তবে কমপক্ষে আরও একটি মৌলিক সংখ্যা রয়েছে যা তালিকায় নেই, যথা, q নিজেই। যদি q মৌলিক সংখ্যা না হয়, তাহলে কিছু মৌলিক গুণক p q কে ভাগ করে। যদি এই গুণক p আমাদের তালিকায় থাকে, তবে এটি P কে ভাগ করবে (যেহেতু P হল তালিকার প্রতিটি সংখ্যার গুণফল); কিন্তু p এছাড়াও P + 1 = q কে ভাগ করে, যেমনটি সবেমাত্র বলা হয়েছে। যদি p, P এবং q কে ভাগ করে, তাহলে p-কে অবশ্যই দুটি সংখ্যার পার্থক্যকে ভাগ করতে হবে, যা হল (P + 1) −P বা মাত্র 1। যেহেতু কোনও মৌলিক সংখ্যা 1 কে ভাগ করে না, তাই p তালিকায় থাকতে পারে না। এর অর্থ হল, তালিকার বাইরে অন্তত আরও একটি মৌলিক সংখ্যা বিদ্যমান। এটি প্রমাণ করে যে মৌলিক সংখ্যার প্রতিটি সসীম তালিকার জন্য একটি মৌলিক সংখ্যা রয়েছে যা তালিকায় নেই। মূল রচনায়, যেহেতু ইউক্লিডের মৌলিক সংখ্যার একটি নির্বিচারে তালিকা লেখার কোনও উপায় ছিল না, তাই তিনি এমন একটি পদ্ধতি ব্যবহার করেছিলেন যা তিনি প্রায়শই প্রয়োগ করতেন, অর্থাৎ সাধারণীকরণযোগ্য উদাহরণের পদ্ধতি। অর্থাৎ, তিনি মাত্র তিনটি মৌলিক সংখ্যা বেছে নেন এবং উপরে বর্ণিত সাধারণ পদ্ধতি ব্যবহার করে প্রমাণ করেন যে তিনি সর্বদা একটি অতিরিক্ত মৌলিক সংখ্যা খুঁজে পেতে পারেন। ইউক্লিড সম্ভবত অনুমান করেন যে তাঁর পাঠকরা নিশ্চিত যে, মূলত যত মৌলিক সংখ্যাই বেছে নেওয়া হোক না কেন, অনুরূপ প্রমাণ কাজ করবে। ইউক্লিড প্রায়শই ভুলভাবে এই ফলাফলটি দ্বন্দ্ব দ্বারা প্রমাণ করেছেন বলে জানা যায় যে প্রাথমিকভাবে বিবেচিত সসীম সেটটিতে সমস্ত মৌলিক সংখ্যা রয়েছে, যদিও এটি আসলে ক্ষেত্রে একটি প্রমাণ, একটি সরাসরি প্রমাণ পদ্ধতি। দার্শনিক টর্কেল ফ্রাঞ্জেন যুক্তি সম্পর্কিত একটি বইয়ে বলেছেন, "ইউক্লিডের প্রমাণ যে অসীম সংখ্যক মৌলিক সংখ্যা রয়েছে তা কোনও পরোক্ষ প্রমাণ নয়। যাইহোক, যেহেতু এই অনুমানটি প্রমাণের ক্ষেত্রেও ব্যবহার করা হয় না, তাই সংস্কারটি অর্থহীন। বৈচিত্র্য ইউক্লিডের প্রমাণের বিভিন্ন বৈচিত্র্য রয়েছে, যার মধ্যে নিম্নলিখিতগুলি রয়েছেঃ ফ্যাক্টরিয়াল এন! একটি ধনাত্মক পূর্ণসংখ্যা n-এর 2 থেকে n পর্যন্ত প্রতিটি পূর্ণসংখ্যা দ্বারা বিভাজ্য, কারণ এটি তাদের সকলের গুণফল। সুতরাং, 2 থেকে n পর্যন্ত কোনও পূর্ণসংখ্যা দ্বারা বিভাজ্য নয়, অন্তর্ভুক্ত (প্রতিটি দ্বারা ভাগ করলে এটি 1 এর অবশিষ্টাংশ দেয়)। সুতরাং, n-এর চেয়ে বড় মৌলিক সংখ্যা দ্বারা মৌলিক বা বিভাজ্য। উভয় ক্ষেত্রেই, প্রতিটি ধনাত্মক পূর্ণসংখ্যা n-এর জন্য, n-এর চেয়ে কমপক্ষে একটি মৌলিক সংখ্যা বড়। উপসংহার হল যে মৌলিক সংখ্যার সংখ্যা অসীম। অয়লারের প্রমাণ সুইস গণিতবিদ লিওনহার্ড অয়লারের আরেকটি প্রমাণ গাণিতিক মৌলিক উপপাদ্যের উপর নির্ভর করেঃ যে প্রতিটি পূর্ণসংখ্যার একটি অনন্য মৌলিক গুণনীয়ক রয়েছে। অয়লার যা লিখেছেন (এই আধুনিক স্বরলিপির সাথে নয় এবং আধুনিক মানের বিপরীতে, যোগফল এবং গুণফলের আর্গুমেন্টগুলিকে পূর্ণসংখ্যার কোনও সীমাবদ্ধ সেটের মধ্যে সীমাবদ্ধ না করে) তা এই বিবৃতির সমতুল্য যে আমাদের কাছে যেখানে প্রথম মৌলিক সংখ্যার সেটকে বোঝায়, এবং ধনাত্মক পূর্ণসংখ্যার সেট যার সমস্ত মৌলিক গুণক রয়েছে। উপান্ত্য যোগফলের মধ্যে মৌলিক সংখ্যার প্রতিটি গুণফল ঠিক একবার উপস্থিত হয়, এবং তাই গাণিতিক মৌলিক উপপাদ্য অনুসারে শেষ সমতাটি সত্য। এই ফলাফলের প্রথম পর্যালোচনায় অয়লার "পরম অনন্ত"-এর অনুরূপ একটি প্রতীক দ্বারা নির্দেশ করেছেন এবং লিখেছেন যে বিবৃতির অসীম যোগফল "মান"-এর সমান, যার সাথে অসীম গুণফলও এইভাবে সমান (আধুনিক পরিভাষায় এটি বলার সমতুল্য যে হারমোনিক সিরিজের আংশিক যোগফল অ্যাসিম্পটোটিকভাবে ভিন্ন হয়)। তারপর অয়লার তাঁর দ্বিতীয় অনুচ্ছেদে উল্লেখ করেছেন যে গুণফলটি সসীম মান 2-এ রূপান্তরিত হয় এবং ফলস্বরূপ বর্গের চেয়ে বেশি মৌলিক সংখ্যা রয়েছে ("ক্রমিক অসীমগুলি এসিস সংখ্যা প্রাইমস")। এটি ইউক্লিডের উপপাদ্যকে প্রমাণ করে। একই গবেষণাপত্রে (উপপাদ্য 19) অয়লার প্রকৃতপক্ষে উপরের সমতা ব্যবহার করেছিলেন একটি আরও শক্তিশালী উপপাদ্য প্রমাণ করার জন্য যা তাঁর আগে অজানা ছিল, যথা সিরিজটি ডাইভারজেন্ট, যেখানে সমস্ত মৌলিক সংখ্যার সেটকে বোঝায় (অয়লার লিখেছেন যে অসীম যোগফল, যা আধুনিক পরিভাষায় বলার সমতুল্য যে এই সিরিজের আংশিক যোগফল অ্যাসিম্পটোটিকভাবে আচরণ করে)। এরদোসের প্রমাণ পল এরদোস একটি প্রমাণ দিয়েছেন যা গাণিতিক মৌলিক উপপাদ্যের উপরও নির্ভর করে। প্রতিটি ধনাত্মক পূর্ণসংখ্যার একটি বর্গ-মুক্ত সংখ্যা এবং একটি বর্গ সংখ্যায় একটি অনন্য গুণনসংখ্যা থাকে। উদাহরণস্বরূপ,। একটি ধনাত্মক পূর্ণসংখ্যা ধরা যাক, এবং এর চেয়ে কম বা সমান মৌলিক সংখ্যার সংখ্যা ধরা যাক। সেই মৌলিক সংখ্যাগুলিকে কল করুন। যে কোনও ধনাত্মক পূর্ণসংখ্যা যা এর চেয়ে কম বা সমান হয় তা সেই আকারে লেখা যেতে পারে যেখানে প্রতিটি হয় বা। এর বর্গ-মুক্ত অংশ গঠনের উপায় রয়েছে। এবং এটা হতেই পারে। সুতরাং, সর্বাধিক সংখ্যা এই আকারে লেখা যেতে পারে। অন্য কথায়, বা, পুনর্বিন্যাস, এর চেয়ে কম বা সমান মৌলিক সংখ্যার সংখ্যা এর চেয়ে বেশি বা সমান। যেহেতু এটি স্বেচ্ছাচারী ছিল, তাই যথাযথভাবে বেছে নেওয়ার মাধ্যমে যতটা ইচ্ছা তত বড় হতে পারে। ফারস্টেনবার্গের প্রমাণ 1950-এর দশকে, হিলেল ফারস্টেনবার্গ পয়েন্ট-সেট টপোলজি ব্যবহার করে দ্বন্দ্ব দ্বারা একটি প্রমাণ প্রবর্তন করেছিলেন। পূর্ণসংখ্যা Z-এর উপর একটি টপোলজি সংজ্ঞায়িত করুন, যাকে সমানভাবে ব্যবধানযুক্ত পূর্ণসংখ্যা টপোলজি বলা হয়, একটি উপসেট U′Z-কে একটি উন্মুক্ত সেট হিসাবে ঘোষণা করে যদি এবং শুধুমাত্র যদি এটি খালি সেট হয়, যু, বা এটি গাণিতিক ক্রম S (a, b)-এর একটি ইউনিয়ন হয় (a §0-এর জন্য), যেখানে তারপর একটি বৈপরীত্য বৈশিষ্ট্য থেকে অনুসরণ করা হয় যে পূর্ণসংখ্যার একটি সীমাবদ্ধ সেট খোলা হতে পারে না এবং যে বৈশিষ্ট্যটি S (a, b) সেট করে তা উভয়ই খোলা এবং বন্ধ, কারণ এর পরিপূরক সীমাবদ্ধ, কিন্তু বন্ধ করা যায় না কারণ এটি বন্ধ সেটগুলির একটি সীমাবদ্ধ ইউনিয়ন। অন্তর্ভুক্তি-বর্জন নীতি ব্যবহার করে সাম্প্রতিক প্রমাণ প্রমাণ হুয়ান পাবলো পিনাস্কো নিম্নলিখিত প্রমাণ লিখেছেন। ধরা যাক p1,., pN হল সবচেয়ে ছোট N মৌলিক সংখ্যা। তারপর অন্তর্ভুক্তি-বর্জন নীতি অনুসারে, x-এর কম বা সমান ধনাত্মক পূর্ণসংখ্যার সংখ্যা যা সেই মৌলিক সংখ্যাগুলির মধ্যে একটির দ্বারা বিভাজ্য, তা হল x দ্বারা ভাগ করা এবং x → φ দেওয়া। এটি এইভাবে লেখা যেতে পারে যদি p1,., pN ছাড়া অন্য কোনও মৌলিক সংখ্যা না থাকে, তবে (1)-এর অভিব্যক্তিটি সমান এবং (2)-এর অভিব্যক্তিটি 1-এর সমান, তবে স্পষ্টতই (3)-এর অভিব্যক্তিটি 1-এর সমান নয়। অতএব, অবশ্যই p1,., pN এর চেয়ে বেশি মৌলিক সংখ্যা থাকতে হবে। লেজেন্ডারের সূত্র ব্যবহার করে প্রমাণ 2010 সালে, জুনহো পিটার ওয়াং দ্বন্দ্ব দ্বারা নিম্নলিখিত প্রমাণ প্রকাশ করেছিলেন। ধরা যাক k যেকোনও ধনাত্মক পূর্ণসংখ্যা। তারপরে লেজেন্ডারের সূত্র অনুসারে (কখনও কখনও ডি পলিগনাককে দায়ী করা হয়) যেখানে কিন্তু যদি কেবলমাত্র সীমাবদ্ধভাবে অনেকগুলি মৌলিক সংখ্যা বিদ্যমান থাকে, তবে (ভগ্নাংশের সংখ্যা এককভাবে সূচকীয়ভাবে বৃদ্ধি পাবে যখন স্টার্লিংয়ের আনুমানিক দ্বারা হরটি এককভাবে সূচকীয়ভাবে আরও দ্রুত বৃদ্ধি পাবে), এই সত্যের বিরোধিতা করে যে প্রতিটি কে-এর জন্য সংখ্যাটি হরের চেয়ে বড় বা সমান। নির্মাণ দ্বারা প্রমাণ ফিলিপ সাইদাক নির্মাণ দ্বারা নিম্নলিখিত প্রমাণ দিয়েছেন, যা রিডাক্টিও অ্যাড অ্যাবসর্ডাম বা ইউক্লিডের লেম্মা ব্যবহার করে না (যে যদি একটি মৌলিক সংখ্যা p আবকে ভাগ করে তবে এটি অবশ্যই a বা b কে ভাগ করবে)। যেহেতু প্রতিটি স্বাভাবিক সংখ্যার (> 1) কমপক্ষে একটি মৌলিক গুণক থাকে এবং দুটি ক্রমিক সংখ্যা n ও (n + 1)-এর মধ্যে কোনও সাধারণ গুণক থাকে না, তাই গুণফল n (n + 1)-এর মৌলিক গুণক সংখ্যা n-এর চেয়ে বেশি আলাদা। সুতরাং প্রোনিক সংখ্যার শৃঙ্খলঃ 1 × 2 = 2 {2}, 2 × 3 = 6 {2,3}, 6 × 7 = 42 {2,3,7}, 42 × 43 = 1806 {2,3,7,43}, 1806 × 1807 = 326342 {2,3,7,43,13,13,139}, ··আমার সীমাহীন ক্রমবর্ধমান সেটের একটি ক্রম প্রদান করে। অসংকুচন পদ্ধতি ব্যবহার করে প্রমাণ ধরুন শুধুমাত্র k মৌলিক সংখ্যা (p1,., pk) ছিল। গাণিতিক মৌলিক উপপাদ্য অনুসারে, যে কোনও ধনাত্মক পূর্ণসংখ্যা n-কে তখন এমনভাবে উপস্থাপন করা যেতে পারে যেখানে অ-ঋণাত্মক পূর্ণসংখ্যা সূচকগুলি এবং সসীম আকারের মৌলিক সংখ্যার তালিকা সংখ্যাটি পুনর্গঠনের জন্য যথেষ্ট। যেহেতু সমস্ত i-এর জন্য, এটি অনুসরণ করে যে সমস্ত i-এর জন্য (যেখানে ভিত্তি-2 লগারিদম বোঝায়)। এটি নিম্নলিখিত আকারের n-এর জন্য একটি এনকোডিং প্রদান করে (বড় O স্বরলিপি ব্যবহার করে): বিট। এটি বাইনারিতে সরাসরি এন উপস্থাপন করার চেয়ে অনেক বেশি কার্যকর এনকোডিং, যা বিট নেয়। ক্ষতিহীন তথ্য সংকোচনের একটি প্রতিষ্ঠিত ফলাফল বলে যে কেউ সাধারণত এন বিটের তথ্যকে এন বিটের চেয়ে কম সংকুচিত করতে পারে না। উপরের উপস্থাপনাটি এটিকে লঙ্ঘন করে যখন n যথেষ্ট বড় হয়। অতএব, মৌলিক সংখ্যার সংখ্যা অবশ্যই সীমাবদ্ধ হওয়া উচিত নয়। শক্তিশালী ফলাফল এই বিভাগের উপপাদ্যগুলি একই সাথে ইউক্লিডের উপপাদ্য এবং অন্যান্য ফলাফলকে বোঝায়। গাণিতিক অগ্রগতির উপর ডিরিচলেটের উপপাদ্য বলে যে কোনও দুটি ধনাত্মক সহমৌলিক পূর্ণসংখ্যা a এবং d-এর জন্য a + nd আকারে অসীম সংখ্যক মৌলিক সংখ্যা রয়েছে, যেখানে n একটি ধনাত্মক পূর্ণসংখ্যাও। অন্য কথায়, অসীম সংখ্যক মৌলিক সংখ্যা রয়েছে যা একটি মডুলো ডি-এর সাথে সামঞ্জস্যপূর্ণ। মৌলিক সংখ্যা উপপাদ্য ধরা যাক মৌলিক-গণনা ফাংশন যা যে কোনও বাস্তব সংখ্যার জন্য মৌলিক সংখ্যার সংখ্যা কম বা সমান দেয়। মৌলিক সংখ্যা উপপাদ্যটি তখন বলে যে এটি একটি ভাল অনুমান, এই অর্থে যে দুটি ফাংশনের ভাগফলের সীমা এবং সীমা ছাড়াই বৃদ্ধি হিসাবে 1: অ্যাসিম্পটোটিক স্বরলিপি ব্যবহার করে এই ফলাফলটি পুনরায় বলা যেতে পারে এটি ইউক্লিডের উপপাদ্যটি দেয়, যেহেতু বার্ট্রান্ড-চেবিশেভ উপপাদ্য সংখ্যা তত্ত্বে, বার্ট্রান্ডের স্বীকার্যটি এমন একটি উপপাদ্য যা বলে যে কোনও পূর্ণসংখ্যার জন্য সর্বদা কমপক্ষে একটি মৌলিক সংখ্যা বিদ্যমান থাকে যার সাথে বার্ট্রান্ড-চেবিশেভ উপপাদ্যটিও সম্পর্ক হিসাবে বলা যেতে পারে, যেখানে মৌলিক-গণনা ফাংশন (মৌলিক সংখ্যার সংখ্যা কম বা সমান): সবকিছুর জন্য এই বিবৃতিটি প্রথম অনুমান করা হয়েছিল 1845 সালে জোসেফ বার্ট্রান্ড (1822-1900) দ্বারা। বার্ট্রান্ড নিজেই 1852 সালে চেবিশেভ (1821-1894) দ্বারা সমস্ত সংখ্যার জন্য তাঁর বক্তব্য যাচাই করেছিলেন এবং তাই এই অনুমানটিকে বার্ট্রান্ড-চেবিশেভ উপপাদ্য বা চেবিশেভের উপপাদ্যও বলা হয়। নোট এবং রেফারেন্সগুলি ইউক্লিডের এলিমেন্টস, বুক IX, প্রোপের বাহ্যিক লিঙ্ক। 20 (ইউক্লিডের প্রমাণ, ক্লার্ক বিশ্ববিদ্যালয়ের ডেভিড জয়েসের ওয়েবসাইটে) মৌলিক সংখ্যা সম্পর্কে উপপাদ্য সম্বলিত নিবন্ধ