Euclid's theorem
یوکلڈ تھیوریم نمبر تھیوری میں ایک بنیادی بیان ہے جو اس بات پر زور دیتا ہے کہ لامحدود طور پر بہت سے پرائم نمبر ہیں۔ یہ سب سے پہلے یوکلڈ نے اپنے کام عناصر میں ثابت کیا تھا۔ نظریہ کے کئی ثبوت ہیں۔ یوکلڈ کے ثبوت یوکلڈ نے اپنے کام عناصر (کتاب IX، تجویز 20) میں شائع ہونے والا ثبوت پیش کیا، جس کی تشریح یہاں کی گئی ہے۔ پرائم نمبروں p1، p2،.، pn کی کسی بھی محدود فہرست پر غور کریں۔ یہ دکھایا جائے گا کہ کم از کم ایک اضافی پرائم نمبر موجود ہے جو اس فہرست میں نہیں ہے۔ فرض کریں کہ P فہرست کے تمام پرائم نمبروں کا پروڈکٹ ہے: P = 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! ایک مثبت عدد n کا 2 سے n تک ہر عدد سے تقسیم ہوتا ہے، کیونکہ یہ ان سب کا پروڈکٹ ہے۔ لہذا، 2 سے n تک کے کسی بھی عدد سے قابل تقسیم نہیں ہے، بشمول (یہ ہر ایک سے تقسیم ہونے پر 1 کا بقیہ دیتا ہے)۔ لہذا یہ یا تو پرائم ہے یا n سے بڑے پرائم سے تقسیم ہوتا ہے۔ دونوں صورتوں میں، ہر مثبت عدد n کے لیے، n سے بڑا کم از کم ایک پرائم ہوتا ہے۔ نتیجہ یہ ہے کہ پرائمز کی تعداد لامحدود ہے۔ اویلر کا ثبوت سوئس ریاضی دان لیون ہارڈ اویلر کا ایک اور ثبوت، ریاضی کے بنیادی نظریہ پر انحصار کرتا ہے: کہ ہر عدد کی ایک منفرد پرائم فیکٹرائزیشن ہوتی ہے۔ اویلر نے جو لکھا (اس جدید اشارے کے ساتھ نہیں اور جدید معیارات کے برعکس، جملوں اور پروڈکٹس میں دلائل کو انٹیجرز کے کسی بھی محدود سیٹ تک محدود نہیں کرنا) اس بیان کے مساوی ہے کہ ہمارے پاس جہاں پہلے پرائم نمبروں کے سیٹ کی نشاندہی کرتا ہے، اور مثبت انٹیجرز کا سیٹ ہے جس کے تمام پرائم فیکٹر میں ہیں۔ آخری عدد میں پرائمز کا ہر پروڈکٹ بالکل ایک بار ظاہر ہوتا ہے، اور اس لیے آخری مساوات ریاضی کے بنیادی نظریہ کے مطابق درست ہے۔ اس نتیجے کے اپنے پہلے نتیجہ میں اویلر "مطلق لامحدود" سے ملتی جلتی علامت کی طرف اشارہ کرتا ہے اور لکھتا ہے کہ بیان میں لامحدود رقم "قدر" کے برابر ہے، جس کے لیے لامحدود پروڈکٹ بھی اس طرح برابر ہے (جدید اصطلاحات میں یہ کہنے کے برابر ہے کہ ہارمونک سیریز کا جزوی مجموعہ غیر علامتی طور پر اس طرح مختلف ہوتا ہے)۔ پھر اپنے دوسرے متن میں اویلر نوٹ کرتا ہے کہ پروڈکٹ محدود قدر 2 میں یکجا ہوتا ہے، اور اس کے نتیجے میں مربعوں سے زیادہ پرائمز ہوتے ہیں ("سیکوئٹر انفینیٹیز پلورز ایسس نمبرز پرائموس")۔ یہ یوکلڈ کے نظریہ کو ثابت کرتا ہے۔ اسی مقالے میں (نظریہ 19) اویلر نے درحقیقت مذکورہ بالا مساوات کو ایک زیادہ مضبوط نظریہ ثابت کرنے کے لیے استعمال کیا جو اس سے پہلے نامعلوم تھا، یعنی یہ کہ سلسلہ متفرق ہے، جہاں تمام پرائم نمبروں کے سیٹ کی نشاندہی ہوتی ہے (اویلر لکھتے ہیں کہ لامحدود مجموعہ، جو جدید اصطلاحات میں یہ کہنے کے مساوی ہے کہ اس سلسلے کا جزوی مجموعہ غیر علامتی طور پر ایسا ہی برتاؤ کرتا ہے)۔ ایرڈس کے ثبوت پال ایرڈس نے ایک ایسا ثبوت دیا جو ریاضی کے بنیادی نظریہ پر بھی منحصر ہے۔ ہر مثبت عدد میں مربع فری نمبر اور مربع نمبر میں ایک منفرد فیکٹرائزیشن ہوتی ہے۔ مثلا۔ ایک مثبت عدد ہونے دیں، اور پرائمز کی تعداد کو اس سے کم یا برابر ہونے دیں۔ ان پرائمز کو کال کریں۔ کوئی بھی مثبت عدد جو اس سے کم یا برابر ہو پھر اس شکل میں لکھا جا سکتا ہے جہاں ہر ایک یا تو ہے۔ مربع سے پاک حصہ بنانے کے طریقے ہیں۔ اور زیادہ سے زیادہ ایسا ہی ہو سکتا ہے۔ اس طرح زیادہ سے زیادہ اعداد کو اس شکل میں لکھا جا سکتا ہے۔ دوسرے لفظوں میں، یا، دوبارہ ترتیب دینا، سے کم یا اس کے برابر پرائمز کی تعداد، سے زیادہ یا اس کے برابر ہے۔ چونکہ یہ من مانی تھی، اس لیے مناسب طریقے سے انتخاب کرکے جتنا چاہیں اتنا بڑا ہو سکتا ہے۔ فرسٹن برگ کا ثبوت 1950 کی دہائی میں، ہلل فرسٹن برگ نے پوائنٹ سیٹ ٹوپولوجی کا استعمال کرتے ہوئے تضاد کے ذریعے ایک ثبوت متعارف کرایا۔ انٹیجرز Z پر ایک ٹوپولوجی کی وضاحت کریں، جسے یکساں فاصلہ والا انٹیجر ٹوپولوجی کہا جاتا ہے، ایک ذیلی سیٹ U′Z کو ایک کھلا سیٹ قرار دیتے ہوئے اگر اور صرف اس صورت میں جب یہ یا تو خالی سیٹ ہو، یا یہ ریاضیاتی ترتیبات S (a, b) کا اتحاد ہو، جہاں پھر اس پراپرٹی سے ایک تضاد سامنے آتا ہے کہ انٹیجرز کا ایک محدود سیٹ کھلا نہیں ہو سکتا اور وہ پراپرٹی جو بیس S (a, b) سیٹ کرتا ہے وہ کھلا اور بند دونوں ہے، کیونکہ اسے بند نہیں کیا جا سکتا کیونکہ اس کی تکمیل محدود ہے، لیکن بند ہے کیونکہ یہ بند سیٹوں کا ایک محدود اتحاد ہے۔ شمولیت-اخراج کے اصول کا استعمال کرتے ہوئے حالیہ ثبوت ثبوت جوآن پابلو پناسکو نے درج ذیل ثبوت لکھا ہے۔ فرض کریں کہ p1,., pN سب سے چھوٹے N پرائمز ہیں۔ پھر شمولیت-اخراج کے اصول کے مطابق، x سے کم یا اس کے برابر مثبت انٹیجرز کی تعداد جو ان پرائمز میں سے کسی ایک سے تقسیم ہوتی ہے، x سے تقسیم ہوتی ہے اور x کو φ دیتا ہے۔ یہ اس طرح لکھا جا سکتا ہے کہ اگر p1، pN کے علاوہ کوئی اور پرائم موجود نہیں ہے، تو (1) میں اظہار 1 کے برابر ہے اور (2) میں اظہار 1 کے برابر ہے، لیکن واضح طور پر (3) میں اظہار 1 کے برابر نہیں ہے۔ لہذا، p1،.، pN سے زیادہ پرائمز ہونے چاہئیں۔ لیجنڈری کے فارمولے کا استعمال کرتے ہوئے ثبوت 2010 میں، جونہو پیٹر وانگ نے تضاد کے ذریعے درج ذیل ثبوت شائع کیا۔ فرض کریں کہ k کوئی بھی مثبت عدد ہے۔ پھر لیجنڈری کے فارمولے کے مطابق (بعض اوقات ڈی پولیگناک سے منسوب کیا جاتا ہے) جہاں لیکن اگر صرف محدود طور پر بہت سے پرائم موجود ہوں، تو (فریکشن کا نیومریٹر اکیلا تیزی سے بڑھے گا جبکہ سٹرلنگ کے تخمینے سے ڈینومینیٹر اکیلا تیزی سے بڑھتا ہے)، اس حقیقت سے متصادم ہے کہ ہر 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,139}، ·· پرائمز کے لامحدود بڑھتے ہوئے سیٹوں کی ترتیب فراہم کرتا ہے۔ انکمپریسیبلٹی طریقہ استعمال کرتے ہوئے ثبوت فرض کریں کہ صرف k پرائمز (p1,., pk) تھے۔ ریاضی کے بنیادی نظریہ کے مطابق، اس کے بعد کسی بھی مثبت عدد n کی نمائندگی اس طرح کی جا سکتی ہے جہاں غیر منفی عدد ایکسپونینٹ ای آئی، پرائمز کی محدود سائز کی فہرست کے ساتھ مل کر نمبر کی تشکیل نو کے لیے کافی ہیں۔ چونکہ تمام i کے لیے، یہ اس کے بعد آتا ہے کہ تمام i کے لیے (جہاں بیس-2 لوگارتھم کی نشاندہی ہوتی ہے)۔ اس سے درج ذیل سائز کے n کے لیے ایک انکوڈنگ حاصل ہوتی ہے (بڑے O اشارے کا استعمال کرتے ہوئے): بٹس۔ یہ بائنری میں براہ راست n کی نمائندگی کرنے کے مقابلے میں بہت زیادہ موثر انکوڈنگ ہے، جس میں بٹس لگتے ہیں۔ نقصان کے بغیر ڈیٹا کمپریشن میں ایک قائم شدہ نتیجہ یہ بتاتا ہے کہ کوئی بھی عام طور پر معلومات کے N بٹس کو N بٹس سے کم میں کمپریس نہیں کر سکتا۔ اوپر کی نمائندگی اس کی خلاف ورزی کرتی ہے جب n کافی بڑا ہوتا ہے۔ لہذا، پرائمز کی تعداد محدود نہیں ہونی چاہیے۔ مضبوط نتائج اس حصے میں موجود نظریات بیک وقت یوکلڈ کے نظریہ اور دیگر نتائج کو ظاہر کرتے ہیں۔ ریاضی کی ترقی پر ڈیرچلیٹ کا نظریہ ڈیرچلیٹ کا نظریہ بیان کرتا ہے کہ کسی بھی دو مثبت کوپرائم انٹیجرز a اور d کے لیے، a + nd کی شکل کے لامحدود طور پر بہت سے پرائم ہوتے ہیں، جہاں n بھی ایک مثبت انٹیجر ہے۔ دوسرے لفظوں میں، لامحدود طور پر بہت سے پرائمز ہوتے ہیں جو کسی ماڈیولو ڈی کے ہم آہنگ ہوتے ہیں۔ پرائم نمبر تھیوریم کو پرائم گنتی کرنے والا فنکشن ہونے دیں جو کسی بھی حقیقی نمبر کے لیے پرائمز کی تعداد کو اس سے کم یا اس کے برابر دیتا ہے۔ پرائم نمبر تھیوریم پھر یہ بتاتا ہے کہ یہ ایک اچھا تخمینہ ہے، اس معنی میں کہ دونوں افعال کے حصص کی حد اور جیسا کہ باؤنڈ کے بغیر اضافہ ہوتا ہے 1: اسمیپٹوٹک نوٹیشن کا استعمال کرتے ہوئے اس نتیجہ کو دوبارہ اس طرح بیان کیا جا سکتا ہے کہ یہ یوکلڈ کا نظریہ پیش کرتا ہے، چونکہ برٹرینڈ-چیبیشیف تھیوریم نمبر تھیوریم میں، برٹرینڈ کا مفروضہ ایک نظریہ ہے جس میں کہا گیا ہے کہ کسی بھی انٹیجر کے لیے، ہمیشہ کم از کم ایک پرائم نمبر موجود ہوتا ہے جس کے ساتھ برٹرینڈ-چیبیشیف تھیوریم کو بھی تعلق کے طور پر بیان کیا جا سکتا ہے، جہاں پرائم گنتی فنکشن (پرائمز کی تعداد کم یا برابر) ہے: سب کے لیے یہ بیان پہلی بار 1845 میں جوزف برٹرینڈ (1822-1900) نے پیش کیا تھا۔ برٹرینڈ نے خود وقفے میں تمام اعداد کے لیے اپنے بیان کی تصدیق کی۔ اس کے قیاس کو 1852 میں چیبیشیف (1821-1894) نے مکمل طور پر ثابت کیا تھا اور اس لیے اس مفروضے کو برٹرینڈ-چیبیشیف تھیوریم یا چیبیشیف تھیوریم بھی کہا جاتا ہے۔ نوٹ اور حوالہ جات بیرونی روابط یوکلڈ کے عناصر، کتاب IX، پروپ۔ 20 (یوکلڈ کا ثبوت، کلارک یونیورسٹی میں ڈیوڈ جوائس کی ویب سائٹ پر) بنیادی اعداد کے بارے میں ثبوت کے نظریات پر مشتمل مضامین