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

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 सूची में नहीं हो सकता। इसका मतलब यह है कि कम से कम एक और अभाज्य संख्या सूची में उन से परे मौजूद है।

यह साबित करता है कि अभाज्य संख्याओं की प्रत्येक परिमित सूची के लिए एक अभाज्य संख्या होती है जो सूची में नहीं होती है। मूल कार्य में, जैसा कि यूक्लिड के पास अभाज्य संख्याओं की मनमानी सूची लिखने का कोई तरीका नहीं था, उसने एक ऐसी विधि का उपयोग किया जिसे वह अक्सर लागू करता था, अर्थात्, सामान्यीकरण उदाहरण की विधि। अर्थात्, वह केवल तीन प्राइम चुनता है और ऊपर उल्लिखित सामान्य विधि का उपयोग करके साबित करता है कि वह हमेशा एक अतिरिक्त प्राइम ढूंढ सकता है। यूक्लिड संभवतः मानता है कि उसके पाठक आश्वस्त हैं कि एक समान प्रमाण काम करेगा, चाहे कितने भी अभाज्य मूल रूप से चुने गए हों। यूक्लिड को अक्सर गलत तरीके से विरोधाभास द्वारा प्रमाण होने की सूचना दी जाती है, जो इस धारणा से शुरू होता है कि शुरू में परिमित सेट में सभी अभाज्य संख्याएँ शामिल हैं, हालांकि यह वास्तव में मामलों द्वारा एक प्रमाण है, एक प्रत्यक्ष प्रमाण विधि। दार्शनिक टोर्केल फ्रेंज़ेन, तर्क पर एक पुस्तक में, यूक्लिड का प्रमाण बताता है कि असीम रूप से कई अभाज्य हैं, यह एक अप्रत्यक्ष प्रमाण नहीं है [...] तर्क को कभी-कभी एक अप्रत्यक्ष प्रमाण के रूप में धारणा के साथ प्रतिस्थापित करके तैयार किया जाता है 'मान लीजिए 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: Furstenberg's proof of the infinitude of primes

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)$

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

हाल के प्रमाण

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

जुआन पाब्लो पिनास्को ने निम्नलिखित प्रमाण लिखा है। चलो पी₁, ..., पी_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)$

यदि पी के अलावा कोई अन्य प्राइम नहीं है₁, ..., पी_N मौजूद है, तो अभिव्यक्ति (1) के बराबर है$\lfloor x\rfloor$ और (2) में अभिव्यक्ति 1 के बराबर है, लेकिन स्पष्ट रूप से अभिव्यक्ति (3) 1 के बराबर नहीं है। इसलिए, 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: Dirichlet's theorem on arithmetic progressions

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

प्रधान संख्या प्रमेय

Main article: Prime number theorem

होने देना π(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)