यूक्लिड का प्रमेय

This article is about अभाज्य संख्याओं की अनंतता पर प्रमेय. For पूर्ण संख्या पर प्रमेय और मेर्सन प्राइम्स, see यूक्लिड-यूलर प्रमेय. For अभाज्य संख्याओं द्वारा उत्पादों की विभाज्यता पर प्रमेय, see यूक्लिड लेमा.

यूक्लिड का प्रमेय संख्या सिद्धांत में मौलिक कथन है जो यह दावा करता है कि अपरिमित रूप से कई अभाज्य संख्याएँ हैं। यह सर्वप्रथम यूक्लिड ने अपनी पुस्तक एलिमेंट्स में सिद्ध किया था। प्रमेय के कई प्रमाण हैं।

यूक्लिड का सबूत

यूक्लिड ने अपने काम एलिमेंट्स (पुस्तक IX, प्रस्ताव 20) में प्रकाशित सबूत की पेशकश की, जिसे यहां व्याख्यायित किया गया है।

अभाज्य संख्याओं p₁, p₂, ..., p_n की किसी भी सीमित सूची पर विचार करें। यह दिखाया जाएगा कि कम से कम एक अतिरिक्त अभाज्य संख्या जो इस सूची में नहीं है, उपस्थित है। 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 सूची में नहीं हो सकता। इसका मतलब यह है कि कम से कम एक और अभाज्य संख्या सूची में उन से परे उपस्थित है।

यह साबित करता है कि अभाज्य संख्याओं की प्रत्येक परिमित सूची के लिए, अभाज्य संख्या होती है जो सूची में नहीं होती है। मूल कार्य में, जैसा कि यूक्लिड के पास अभाज्य संख्याओं की मनमानी सूची लिखने का कोई तरीका नहीं था, उसने एक ऐसी विधि का उपयोग किया जिसे वह अक्सर लागू करता था, अर्थात् सामान्यीकरण उदाहरण की विधि। अर्थात्, वह केवल तीन प्राइम चुनता है और ऊपर उल्लिखित सामान्य विधि का उपयोग करके यह साबित करता है कि वह हमेशा एक अतिरिक्त प्राइम ढूंढ सकता है I यूक्लिड संभवतः यह मानता है कि उसके पाठक आश्वस्त हैं कि एक समान प्रमाण काम करेगा, भले ही मूल रूप से कितने अभाज्य संख्याएं चुनी गई हों।

यूक्लिड को अक्सर गलत तरीके से इस परिणाम को विरोधाभास से साबित करने की सूचना दी जाती है, जो इस धारणा से प्रारम्भ होता है कि प्रारम्भ में परिमित सेट में सभी अभाज्य संख्याएँ सम्मिलित हैं, हालांकि यह वास्तव में मामलों द्वारा एक प्रमाण है, एक प्रत्यक्ष प्रमाण विधि है। तर्क पर एक पुस्तक में दार्शनिक टोर्केल फ्रेंज़ेन कहते हैं, "यूक्लिड का सबूत है कि असीम रूप से कई अभाज्य हैं, अप्रत्यक्ष प्रमाण नहीं है [...] तर्क को कभी-कभी एक अप्रत्यक्ष सबूत के रूप में तैयार किया जाता है, इसे धारणा 'मान लीजिए q₁' के साथ बदलकर , ... q_n सभी अभाज्य संख्याएँ हैं'। हालाँकि, चूंकि इस धारणा का उपयोग प्रमाण में भी नहीं किया गया है, सुधार व्यर्थ है।"

विविधताएं

यूक्लिड के प्रमाण पर कई भिन्नताएँ उपस्थित हैं, जिनमें निम्न सम्मिलित हैं:

धनात्मक पूर्णांक n का भाज्य n! 2 से n तक प्रत्येक पूर्णांक से विभाज्य है, क्योंकि यह उन सभी का गुणनफल है। इस तरह, n! + 1 2 से n तक किसी भी पूर्णांक से विभाज्य नहीं है, समावेशी (प्रत्येक द्वारा विभाजित करने पर यह 1 का शेष देता है)। इस तरह n! + 1 या तो अभाज्य है या n से बड़े अभाज्य से विभाज्य है। किसी भी स्थिति में, प्रत्येक धनात्मक पूर्णांक n के लिए, n से कम से कम एक अभाज्य बड़ा होता है। निष्कर्ष यह है कि अभाज्य संख्याओं की संख्या अनंत है।

यूलर का सबूत

स्विस गणितज्ञ लियोनहार्ड यूलर द्वारा एक अन्य प्रमाण, अंकगणित के मौलिक प्रमेय पर निर्भर करता है: कि प्रत्येक पूर्णांक का एक अद्वितीय प्रधान गुणनखंड होता है। यूलर ने जो लिखा (इस आधुनिक संकेतन के साथ नहीं और, आधुनिक मानकों के विपरीत, योगों और उत्पादों में तर्कों को पूर्णांकों के किसी परिमित समुच्चय तक सीमित नहीं करना) उस कथन के समतुल्य है जो हमारे पास है

$\prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}=\sum _{n\in N_{k}}{\frac {1}{n}},$

जहाँ $P_{k}$ के सेट को दर्शाता है k पहली अभाज्य संख्याएँ, और $N_{k}$ धनात्मक पूर्णांकों का समुच्चय है जिसके अभाज्य गुणनखंड सभी में हैं $P_{k}.$

इसे दिखाने के लिए, हम उत्पाद में प्रत्येक कारक को एक ज्यामितीय श्रृंखला के रूप में विस्तारित करते हैं, और योग पर उत्पाद को वितरित करते हैं (यह रीमैन ज़ेटा फ़ंक्शन के लिए यूलर गुणनफल सूत्र के यूलर गुणनफल सूत्र के प्रमाण का एक विशेष मामला है)।

${\begin{aligned}\prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}&=\prod _{p\in P_{k}}\sum _{i\geq 0}{\frac {1}{p^{i}}}\\&=\left(\sum _{i\geq 0}{\frac {1}{2^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{3^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{5^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{7^{i}}}\right)\cdots \\&=\sum _{\ell ,m,n,p,\ldots \geq 0}{\frac {1}{2^{\ell }3^{m}5^{n}7^{p}\cdots }}\\&=\sum _{n\in N_{k}}{\frac {1}{n}}.\end{aligned}}$

अन्तिम योग में अभाज्य संख्याओं का प्रत्येक गुणनफल ठीक एक बार प्रकट होता है, और इसलिए अंकगणित के मौलिक प्रमेय द्वारा अंतिम समानता सत्य है। इस परिणाम के अपने पहले परिणाम में यूलर एक समान प्रतीक द्वारा निरूपित करता है $\infty$ «पूर्ण अनंतता» और लिखता है कि बयान में अनंत राशि «मूल्य» के बराबर है $\log \infty$, जिसके लिए अनंत उत्पाद इस प्रकार भी बराबर है (आधुनिक शब्दावली में यह कहने के बराबर है कि आंशिक योग $x$ हार्मोनिक श्रृंखला का विचलन समान रूप से होता है $\log x$). उसके बाद अपने दूसरे परिणाम में यूलर ने नोट किया कि उत्पाद

$\prod _{n\geq 2}{\frac {1}{1-{\frac {1}{n^{2}}}}}$

परिमित मान 2 में परिवर्तित हो जाता है, और इसके परिणामस्वरूप वर्गों की तुलना में अधिक अभाज्य संख्याएँ होती हैं ("सीक्वेटुर इन्फिनिटीज़ प्लूरस एसे न्यूमेरोस प्रिमोस")। यह यूक्लिड प्रमेय को सिद्ध करता है।

अनंत को दर्शाने के लिए यूलर द्वारा प्रयुक्त प्रतीक

उसी पेपर में (प्रमेय 19) यूलर ने वास्तव में उपरोक्त समानता का उपयोग एक बहुत मजबूत प्रमेय को साबित करने के लिए किया था जो उसके पहले अज्ञात था, अर्थात् श्रृंखला

$\sum _{p\in P}{\frac {1}{p}}$

अभाज्य संख्याओं के व्युत्क्रमों के योग का अपसरण है, जहाँ P सभी अभाज्य संख्याओं के समुच्चय को दर्शाता है (यूलर लिखता है कि अनंत योग $=\log \log \infty$, जो आधुनिक शब्दावली में यह कहने के बराबर है कि आंशिक योग तक $x$ इस श्रृंखला का एसिम्प्टोटिक रूप से व्यवहार करता है $\log \log x$).

एर्दोस का प्रमाण

पॉल एर्डोस ने प्रमाण दिया वह भी अंकगणित के मौलिक प्रमेय पर निर्भर करता है। प्रत्येक धनात्मक पूर्णांक में एक वर्ग-मुक्त पूर्णांक, वर्ग-मुक्त संख्या और एक वर्ग संख्या में एक अद्वितीय गुणनखंड rs² होता है . उदाहरण के लिए, 75,600 = 2⁴ 3³ 5² 7¹ = 21 ⋅ 60².

होने देना N एक धनात्मक पूर्णांक बनें, और दें k से कम या उसके बराबर अभाज्य संख्याओं की संख्या हो N. उन प्राइम्स को बुलाओ p₁, ... , p_k. कोई धनात्मक पूर्णांक a जो कम या बराबर हो N फिर फॉर्म में लिखा जा सकता है

$a=\left(p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}\right)s^{2},$

जहां प्रत्येक e_i भी है 0 या 1. वहाँ हैं 2^k वर्ग मुक्त भाग बनाने के तरीके a. और s² ज्यादा से ज्यादा हो सकता है N, इसलिए s ≤ √N. इस प्रकार, अधिक से अधिक 2^k √N संख्याओं को इस रूप में लिखा जा सकता है। दूसरे शब्दों में,

$N\leq 2^{k}{\sqrt {N}}.$

या, पुनर्व्यवस्थित k N से कम या उसके बराबर अभाज्य संख्याओं की संख्या 1/2log₂ N से अधिक या उसके बराबर है। चूँकि N स्वैच्छिक था, k उचित रूप से N को चुनकर जितना बड़ा हो सकता है।

फुरस्टेनबर्ग का प्रमाण

Main article: फुरस्टेनबर्ग का अभाज्य संख्याओं की अनंतता का प्रमाण

1950 के दशक में, हिलेल फुरस्टेनबर्ग ने बिंदु-सेट टोपोलॉजी का उपयोग करते हुए विरोधाभास द्वारा एक प्रमाण प्रस्तुत किया है।

उपसमुच्चय U ⊆ Z को एक खुला सेट घोषित करके पूर्णांक Z पर एक टोपोलॉजी परिभाषित करें, जिसे समान रूप से स्थान पूर्णांक टोपोलॉजी कहा जाता है, यदि और केवल यदि यह या तो खाली सेट है, ∅, या यह एक संघ है (अंकगणित अनुक्रम S(a, b) ('a ≠ 0 के लिए) का सिद्धांत सेट करें, जहां

$S(a,b)=\{an+b\mid n\in \mathbb {Z} \}=a\mathbb {Z} +b.$

फिर गुण से एक प्रतिवाद का पालन होता है कि पूर्णांकों का एक परिमित सेट खुला नहीं हो सकता है और वह गुण जो आधार सेट S(a, b) क्लोपेन सेट है, क्योंकि

$\mathbb {Z} \setminus \{-1,+1\}=\bigcup _{p\mathrm {\,prime} }S(p,0)$

बंद नहीं किया जा सकता क्योंकि इसका पूरक परिमित है, लेकिन यह बंद है क्योंकि यह बंद सेटों का परिमित संघ है।

हाल के प्रमाण

समावेश-बहिष्करण सिद्धांत का उपयोग करके सबूत

जुआन पाब्लो पिनास्को ने निम्नलिखित प्रमाण लिखा है।

मान लीजिए p₁, ..., p_N सबसे छोटा N अभाज्य हो। फिर समावेशन-बहिष्करण सिद्धांत द्वारा, x से कम या उसके बराबर धनात्मक पूर्णांकों की संख्या जो कि उन अभाज्यों में से एक से विभाज्य है

${\begin{aligned}1+\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor -\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor &+\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor -\cdots \\&\cdots \pm (-1)^{N+1}\left\lfloor {\frac {x}{p_{1}\cdots p_{N}}}\right\rfloor .\qquad (1)\end{aligned}}$

x से भाग देने पर x → → ∞ देता है

$\sum _{i}{\frac {1}{p_{i}}}-\sum _{i<j}{\frac {1}{p_{i}p_{j}}}+\sum _{i<j<k}{\frac {1}{p_{i}p_{j}p_{k}}}-\cdots \pm (-1)^{N+1}{\frac {1}{p_{1}\cdots p_{N}}}.\qquad (2)$

इसे इस प्रकार लिखा जा सकता है

$1-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)$

यदि p₁, ..., p_N के अलावा और कोई अभाज्य संख्या नहीं है, तो (1) में व्यंजक$\lfloor x\rfloor$के बराबर है और (2) में व्यंजक 1 के बराबर है, लेकिन स्पष्ट रूप से व्यंजक ( 3) 1 के बराबर नहीं है। इसलिए, p₁, ..., p_N से अधिक अभाज्य होने चाहिए।

पोलिग्नैक के सूत्र का उपयोग करके प्रमाण

2010 में, जूनो पीटर वैंग ने विरोधाभास द्वारा निम्नलिखित प्रमाण प्रकाशित किया। मान लीजिए k कोई धनात्मक पूर्णांक है। फिर डी पोलिग्नैक के सूत्र के अनुसार (वास्तव में एड्रियन मैरी लीजेंड्रे के कारण)

$k!=\prod _{p{\text{ prime}}}p^{f(p,k)}$

कहाँ

$f(p,k)=\left\lfloor {\frac {k}{p}}\right\rfloor +\left\lfloor {\frac {k}{p^{2}}}\right\rfloor +\cdots .$

$f(p,k)<{\frac {k}{p}}+{\frac {k}{p^{2}}}+\cdots ={\frac {k}{p-1}}\leq k.$

लेकिन यदि केवल बहुत से अभाज्य संख्याएँ उपस्थित हैं, तब

$\lim _{k\to \infty }{\frac {\left(\prod _{p}p\right)^{k}}{k!}}=0,$

(अंश का अंश घातीय वृद्धि में वृद्धि करेगा, जबकि स्टर्लिंग के सन्निकटन से भाजक एकल चरघातांकी की तुलना में अधिक तेज़ी से बढ़ता है),

इस तथ्य का खंडन करते हुए कि प्रत्येक k के लिए अंश भाजक से अधिक या उसके बराबर है।

निर्माण द्वारा सबूत

फ़िलिप सैदक ने निर्माण द्वारा निम्नलिखित प्रमाण दिया, जो रिडक्टियो एड बेतुका का उपयोग नहीं करता है या यूक्लिड की लेम्मा (कि अगर कोई अभाज्य p ab को विभाजित करता है तो उसे 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 = 3263442 {2, 3, 7, 43, 13, 139}, · · ·
अभाज्य संख्याओं के असीमित बढ़ते सेट का अनुक्रम प्रदान करता है।

असम्पीड्यता विधि का उपयोग करके सबूत

मान लीजिए कि केवल के प्राइम थे (पी₁, ..., पी_k). अंकगणित के मूलभूत प्रमेय के अनुसार, किसी भी धनात्मक पूर्णांक n को तब निरूपित किया जा सकता है

$$n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots {p_{k}}^{e_{k}},$$

जहां गैर-नकारात्मक पूर्णांक घातांक ई_i अभाज्य संख्याओं की परिमित-आकार की सूची के साथ संख्या का पुनर्निर्माण करने के लिए पर्याप्त हैं। तब से $p_{i}\geq 2$ सभी i के लिए, यह उसका अनुसरण करता है $e_{i}\leq \lg n$ सभी के लिए मैं (जहाँ $\lg$ आधार -2 लघुगणक को दर्शाता है)। यह निम्न आकार के एन के लिए एक एन्कोडिंग उत्पन्न करता है (बिग ओ नोटेशन का उपयोग करके):

$O({\text{prime list size}}+k\lg \lg n)=O(\lg \lg n)$ बिट्स।

यह बाइनरी में सीधे एन का प्रतिनिधित्व करने से कहीं अधिक कुशल एन्कोडिंग है, जो लेता है $N=O(\lg n)$ बिट्स। दोषरहित संपीड़न # सीमाएं में एक स्थापित परिणाम बताता है कि सामान्यतः सूचना के एन बिट्स को एन बिट्स से कम में संपीड़ित नहीं किया जा सकता है। उपरोक्त प्रतिनिधित्व इसका उल्लंघन तब तक करता है जब n पर्याप्त रूप से बड़ा होता है $\lg \lg n=o(\lg n)$. इसलिए, अभाज्य संख्याओं की संख्या परिमित नहीं होनी चाहिए।

पर्याप्त परिणाम

इस खंड के प्रमेय एक साथ यूक्लिड के प्रमेय और अन्य परिणामों को दर्शाते हैं।

अंकगणितीय प्रगति पर डिरिचलेट का प्रमेय

Main article: अंकगणितीय प्रगति पर डिरिचलेट की प्रमेय

डिरिचलेट के प्रमेय में कहा गया है कि किन्हीं भी दो धनात्मक सहअभाज्य पूर्णांकों a और d के लिए a + nd के रूप में अपरिमित रूप से अनेक अभाज्य संख्याएँ होती हैं, जहाँ n भी एक धनात्मक पूर्णांक है। दूसरे शब्दों में, अपरिमित रूप से अनेक अभाज्य संख्याएँ होती हैं जो एक सापेक्ष d के अनुरूप होती हैं।

अभाज्य संख्या प्रमेय

Main article: अभाज्य संख्या प्रमेय

मान लीजिए π(x) अभाज्य-गणना फलन है जो किसी वास्तविक संख्या x के लिए x से कम या उसके बराबर अभाज्य संख्याएँ देता है। अभाज्य संख्या प्रमेय तब बताता है कि x / log x, π(x) के लिए एक अच्छा सन्निकटन है, इस अर्थ में कि दो कार्यों π(x) और x / log x के भागफल की सीमा बिना किसी सीमा के x के रूप में बढ़ती है 1 है :

$\lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\log(x)}}=1.$

स्पर्शोन्मुख संकेतन का उपयोग करके इस परिणाम को इस रूप में पुनर्स्थापित किया जा सकता है

$\pi (x)\sim {\frac {x}{\log x}}.$

इससे यूक्लिड प्रमेय प्राप्त होता है, क्योंकि $\lim _{x\rightarrow \infty }{\frac {x}{\log x}}=\infty .$

बर्ट्रेंड-चेबिशेव प्रमेय

संख्या सिद्धांत में, बर्ट्रेंड की परिकल्पना एक प्रमेय है जो बताती है कि किसी भी पूर्णांक के लिए $n>1$, कम से कम एक अभाज्य संख्या हमेशा उपस्थित होती है जैसे कि

$n<p<2n.$

बर्ट्रेंड-चेबीशेव प्रमेय को एक संबंध के रूप में भी कहा जा सकता है $\pi (x)$, कहाँ $\pi (x)$ अभाज्य-गणना फलन है (प्राइम्स की संख्या इससे कम या इसके बराबर $x\,$):

$\pi (x)-\pi ({\tfrac {x}{2}})\geq 1,$ सभी के लिए $x\geq 2.$

यह कथन पहली बार 1845 में जोसेफ लुई फ्रांकोइस बर्ट्रेंड द्वारा अनुमान लगाया गया था (1822-1900)। बर्ट्रेंड ने स्वयं अंतराल में सभी संख्याओं के लिए अपने कथन की पुष्टि की [2, 3 × 10⁶].

उनका अनुमान पूरी तरह से 1852 में पफन्युटी चेबीशेव (1821-1894) द्वारा बर्ट्रेंड के अभिधारणा का प्रमाण था। और इसलिए अभिधारणा को बर्ट्रेंड-चेबिशेव प्रमेय या चेबीशेव प्रमेय भी कहा जाता है।

बाहरी संबंध

• Weisstein, Eric W. "Euclid's Theorem". MathWorld.
• Euclid's Elements, Book IX, Prop. 20 (Euclid's proof, on David Joyce's website at Clark University)