यूक्लिड का प्रमेय: Difference between revisions

Revision as of 15:13, 8 February 2023

This article utilizes technical mathematical notation for logarithms. All instances of log(x) without a subscript base should be interpreted as a natural logarithm, commonly notated as ln(x) or log_e(x).

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

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

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

अभाज्य संख्याओं 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 को भी अंतर को विभाजित करना चाहिए^[3] दो संख्याओं में से, जो (P + 1) − P या केवल 1 है। चूंकि कोई भी अभाज्य संख्या 1 को विभाजित नहीं करती है, p सूची में नहीं हो सकता। इसका मतलब यह है कि कम से कम एक और अभाज्य संख्या सूची में उन से परे उपस्थित है।

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

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

विविधताएं

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

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

यूलर का सबूत

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

\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 में परिवर्तित हो जाता है, और इसके परिणामस्वरूप वर्गों की तुलना में अधिक अभाज्य संख्याएँ होती हैं ("सीक्वेटुर इन्फिनिटीज़ प्लूरस एसे न्यूमेरोस प्रिमोस")। यह यूक्लिड प्रमेय को सिद्ध करता है।^[10]

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

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

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

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

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

पॉल एर्डोस ने प्रमाण दिया^[11] वह भी अंकगणित के मौलिक प्रमेय पर निर्भर करता है। प्रत्येक धनात्मक पूर्णांक में एक वर्ग-मुक्त पूर्णांक, वर्ग-मुक्त संख्या और एक वर्ग संख्या में एक अद्वितीय गुणनखंड $rs 2$ होता है . उदाहरण के लिए, $75,600 = 2 4335271 = 21 \cdot 60 2$ .

होने देना $N$ एक धनात्मक पूर्णांक बनें, और दें $k$ से कम या उसके बराबर अभाज्य संख्याओं की संख्या हो $N$ . उन प्राइम्स को बुलाओ $p 1, ... , 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 2$ ज्यादा से ज्यादा हो सकता है $N$ , इसलिए $s \leq \sqrt N$ . इस प्रकार, अधिक से अधिक $2 k \sqrt N$ संख्याओं को इस रूप में लिखा जा सकता है। दूसरे शब्दों में,

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

या, पुनर्व्यवस्थित $k$ $N$ से कम या उसके बराबर अभाज्य संख्याओं की संख्या $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/2log2 N$ से अधिक या उसके बराबर है। चूँकि $N$ स्वैच्छिक था, $k$ उचित रूप से $N$ को चुनकर जितना बड़ा हो सकता है।

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

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

एक उपसमुच्चय 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)

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

हाल के प्रमाण

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

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

मान लीजिए 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 में, जूनो पीटर वैंग ने विरोधाभास द्वारा निम्नलिखित प्रमाण प्रकाशित किया।^[14] मान लीजिए 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 के लिए अंश भाजक से अधिक या उसके बराबर है।

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

फ़िलिप सैदक ने निर्माण द्वारा निम्नलिखित प्रमाण दिया, जो रिडक्टियो एड बेतुका का उपयोग नहीं करता है^[15] या यूक्लिड की लेम्मा (कि अगर कोई अभाज्य 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)$ . इसलिए, अभाज्य संख्याओं की संख्या परिमित नहीं होनी चाहिए।^[16]

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

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

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

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

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

मान लीजिए $π (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 में जोसेफ लुई फ्रांकोइस बर्ट्रेंड द्वारा अनुमान लगाया गया था^[17] (1822-1900)। बर्ट्रेंड ने स्वयं अंतराल में सभी संख्याओं के लिए अपने कथन की पुष्टि की [2, 3 × 10⁶]. उनका अनुमान पूरी तरह से 1852 में पफन्युटी चेबीशेव (1821-1894) द्वारा बर्ट्रेंड के अभिधारणा का प्रमाण था।^[18] और इसलिए अभिधारणा को बर्ट्रेंड-चेबिशेव प्रमेय या चेबीशेव प्रमेय भी कहा जाता है।

नोट्स और संदर्भ

↑ James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.
↑ Ore, Oystein (1988) [1948], Number Theory and its History, Dover, p. 65
↑ In general, for any integers a, b, c if $a\mid b$ and $a\mid c$ , then $a\mid (b-c)$ . For more information, see Divisibility.
↑ The exact formulation of Euclid's assertion is: "The prime numbers are more numerous than any proposed multitude of prime numbers".
↑ Katz, Victor J. (1998), A History of Mathematics/ an Introduction (2nd ed.), Addison Wesley Longman, p. 87
↑ Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52.
↑ Franzén, Torkel (2004), Inexhaustibility: A Non-exhaustive Treatment, A K Peters, Ltd, p. 101
↑ Bostock, Linda; Chandler, Suzanne; Rourke, C. (2014-11-01). Further Pure Mathematics (in English). Nelson Thornes. p. 168. ISBN 9780859501033.
↑ Theorems 7 and their Corollaries 1 and 2 in: Leonhard Euler. Variae observationes circa series infinitas. Commentarii academiae scientiarum Petropolitanae 9, 1744, pp. 160–188. [1]. (Original) [2]. (English translation version)
↑ In his History of the Theory of Numbers (Vol. 1, p. 413) Dickson refers to this proof, as well as to another one by citing page 235 of another work by Euler: Introductio in Analysin Infinitorum. Tomus Primus. Bousquet, Lausanne 1748. [3]. There (§ 279) Euler in fact essentially restates the much stronger Theorem 19 (described below) in the paper of his former proof.
↑ Havil, Julian (2003). Gamma: Exploring Euler's Constant. Princeton University Press. pp. 28–29. ISBN 0-691-09983-9.
↑ Furstenberg, Harry (1955). "On the infinitude of primes". American Mathematical Monthly. 62 (5): 353. doi:10.2307/2307043. JSTOR 2307043. MR 0068566.
↑ Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", American Mathematical Monthly, volume 116, number 2, February, 2009, pages 172–173.
↑ Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", American Mathematical Monthly, volume 117, number 2, February 2010, page 181.
↑ Saidak, Filip (December 2006). "A New Proof of Euclid's Theorem". American Mathematical Monthly. 113 (10): 937–938. doi:10.2307/27642094. JSTOR 27642094.
↑ Shen, Alexander (2016), Kolmogorov complexity and algorithmic randomness (PDF), AMS, p. 245
↑ Bertrand, Joseph (1845), "Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme.", Journal de l'École Royale Polytechnique (in français), 18 (Cahier 30): 123–140.
↑ Tchebychev, P. (1852), "Mémoire sur les nombres premiers." (PDF), Journal de mathématiques pures et appliquées, Série 1 (in français): 366–390. (Proof of the postulate: 371–382). Also see Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp. 15–33, 1854

बाहरी संबंध

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)

[1] James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.

[2] Ore, Oystein (1988) [1948], Number Theory and its History, Dover, p. 65

[3] In general, for any integers a, b, c if $a\mid b$ and $a\mid c$ , then $a\mid (b-c)$ . For more information, see Divisibility.

[4] The exact formulation of Euclid's assertion is: "The prime numbers are more numerous than any proposed multitude of prime numbers".

[5] Katz, Victor J. (1998), A History of Mathematics/ an Introduction (2nd ed.), Addison Wesley Longman, p. 87

[6] Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52.

[7] Franzén, Torkel (2004), Inexhaustibility: A Non-exhaustive Treatment, A K Peters, Ltd, p. 101

[8] Bostock, Linda; Chandler, Suzanne; Rourke, C. (2014-11-01). Further Pure Mathematics (in English). Nelson Thornes. p. 168. ISBN 9780859501033.

[9] Theorems 7 and their Corollaries 1 and 2 in: Leonhard Euler. Variae observationes circa series infinitas. Commentarii academiae scientiarum Petropolitanae 9, 1744, pp. 160–188. [1]. (Original) [2]. (English translation version)

[10] In his History of the Theory of Numbers (Vol. 1, p. 413) Dickson refers to this proof, as well as to another one by citing page 235 of another work by Euler: Introductio in Analysin Infinitorum. Tomus Primus. Bousquet, Lausanne 1748. [3]. There (§ 279) Euler in fact essentially restates the much stronger Theorem 19 (described below) in the paper of his former proof.

[Havil-11] Havil, Julian (2003). Gamma: Exploring Euler's Constant. Princeton University Press. pp. 28–29. ISBN 0-691-09983-9.

[12] Furstenberg, Harry (1955). "On the infinitude of primes". American Mathematical Monthly. 62 (5): 353. doi:10.2307/2307043. JSTOR 2307043. MR 0068566.

[13] Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", American Mathematical Monthly, volume 116, number 2, February, 2009, pages 172–173.

[14] Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", American Mathematical Monthly, volume 117, number 2, February 2010, page 181.

[15] Saidak, Filip (December 2006). "A New Proof of Euclid's Theorem". American Mathematical Monthly. 113 (10): 937–938. doi:10.2307/27642094. JSTOR 27642094.

[16] Shen, Alexander (2016), Kolmogorov complexity and algorithmic randomness (PDF), AMS, p. 245

[17] Bertrand, Joseph (1845), "Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme.", Journal de l'École Royale Polytechnique (in français), 18 (Cahier 30): 123–140.

[18] Tchebychev, P. (1852), "Mémoire sur les nombres premiers." (PDF), Journal de mathématiques pures et appliquées, Série 1 (in français): 366–390. (Proof of the postulate: 371–382). Also see Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp. 15–33, 1854

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

@@ Line 6: / Line 6: @@
 यूक्लिड ने अपने काम एलिमेंट्स (पुस्तक IX, प्रस्ताव 20) में प्रकाशित सबूत की पेशकश की,<ref>James Williamson (translator and commentator), ''The Elements of Euclid, With Dissertations'', [[Clarendon Press]], Oxford, 1782, page 63.</ref> जिसे यहां व्याख्यायित किया गया है।<ref>{{citation|first=Oystein|last=Ore|title=Number Theory and its History|year=1988|orig-year=1948|publisher=Dover|page=65}}</ref>
-अभाज्य संख्याओं p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>n</sub> की किसी भी सीमित सूची पर विचार करें। यह दिखाया जाएगा कि कम से कम एक अतिरिक्त अभाज्य संख्या जो इस सूची में नहीं है, मौजूद है। P को सूची में सभी अभाज्य संख्याओं का गुणनफल होने दें: P = p1p2...pn. मान लीजिए q = P + 1. तब q या तो अभाज्य है या नहीं:
+अभाज्य संख्याओं p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>n</sub> की किसी भी सीमित सूची पर विचार करें। यह दिखाया जाएगा कि कम से कम एक अतिरिक्त अभाज्य संख्या जो इस सूची में नहीं है, उपस्थित है। P को सूची में सभी अभाज्य संख्याओं का गुणनफल होने दें: P = p1p2...pn. मान लीजिए q = P + 1. तब q या तो अभाज्य है या नहीं:
 *यदि q अभाज्य है, तो कम से कम एक और अभाज्य है जो सूची में नहीं है, अर्थात् स्वयं q।
-*यदि q अभाज्य नहीं है, तो कोई अभाज्य कारक p, q को विभाजित करता है। यदि यह कारक p हमारी सूची में होता, तो यह P को विभाजित करता (क्योंकि P सूची में प्रत्येक संख्या का गुणनफल है); लेकिन p, P + 1 = q को भी विभाजित करता है, जैसा कि अभी बताया गया है। यदि p, P को विभाजित करता है और q को भी, तो p को भी अंतर को विभाजित करना चाहिए<ref>In general, for any integers ''a'', ''b'', ''c'' if <math>a \mid b</math> and <math>a \mid c</math>, then <math> a \mid (b - c)</math>. For more information, see [[Divisibility]].</ref> दो संख्याओं में से, जो (P + 1) − P या केवल 1 है। चूंकि कोई भी अभाज्य संख्या 1 को विभाजित नहीं करती है, p सूची में नहीं हो सकता। इसका मतलब यह है कि कम से कम एक और अभाज्य संख्या सूची में उन से परे मौजूद है।
+*यदि q अभाज्य नहीं है, तो कोई अभाज्य कारक p, q को विभाजित करता है। यदि यह कारक p हमारी सूची में होता, तो यह P को विभाजित करता (क्योंकि P सूची में प्रत्येक संख्या का गुणनफल है); लेकिन p, P + 1 = q को भी विभाजित करता है, जैसा कि अभी बताया गया है। यदि p, P को विभाजित करता है और q को भी, तो p को भी अंतर को विभाजित करना चाहिए<ref>In general, for any integers ''a'', ''b'', ''c'' if <math>a \mid b</math> and <math>a \mid c</math>, then <math> a \mid (b - c)</math>. For more information, see [[Divisibility]].</ref> दो संख्याओं में से, जो (P + 1) − P या केवल 1 है। चूंकि कोई भी अभाज्य संख्या 1 को विभाजित नहीं करती है, p सूची में नहीं हो सकता। इसका मतलब यह है कि कम से कम एक और अभाज्य संख्या सूची में उन से परे उपस्थित है।
 यह साबित करता है कि अभाज्य संख्याओं की प्रत्येक परिमित सूची के लिए, एक अभाज्य संख्या होती है जो सूची में नहीं होती है।<ref>The exact formulation of Euclid's assertion is: "The prime numbers are more numerous than any proposed multitude of prime numbers".</ref> मूल कार्य में, जैसा कि यूक्लिड के पास अभाज्य संख्याओं की मनमानी सूची लिखने का कोई तरीका नहीं था, उसने एक ऐसी विधि का उपयोग किया जिसे वह अक्सर लागू करता था, अर्थात् सामान्यीकरण उदाहरण की विधि। अर्थात्, वह केवल तीन प्राइम चुनता है और ऊपर उल्लिखित सामान्य विधि का उपयोग करके यह साबित करता है कि वह हमेशा एक अतिरिक्त प्राइम ढूंढ सकता है I यूक्लिड संभवतः यह मानता है कि उसके पाठक आश्वस्त हैं कि एक समान प्रमाण काम करेगा, भले ही मूल रूप से कितने अभाज्य संख्याएं चुनी गई हों।<ref>{{citation|first=Victor J.|last=Katz|title=A History of Mathematics/ an Introduction|edition=2nd|publisher=Addison Wesley Longman|year=1998|page=87}}</ref>
@@ Line 15: / Line 15: @@
 यूक्लिड को अक्सर गलत तरीके से इस परिणाम को विरोधाभास से साबित करने की सूचना दी जाती है, जो इस धारणा से शुरू होता है कि शुरू में [[परिमित सेट]] में सभी अभाज्य संख्याएँ शामिल हैं, <ref>Michael Hardy and Catherine Woodgold, "Prime Simplicity", ''[[Mathematical Intelligencer]]'', volume 31, number 4, fall 2009, pages 44–52.</ref> हालांकि यह वास्तव में मामलों द्वारा एक प्रमाण है, एक प्रत्यक्ष प्रमाण विधि है। तर्क पर एक पुस्तक में दार्शनिक टोर्केल फ्रेंज़ेन कहते हैं, "यूक्लिड का सबूत है कि असीम रूप से कई अभाज्य हैं, एक अप्रत्यक्ष सबूत नहीं है [...] तर्क को कभी-कभी एक अप्रत्यक्ष सबूत के रूप में तैयार किया जाता है, इसे धारणा 'मान लीजिए q<sub>1</sub>' के साथ बदलकर , ... q<sub>n</sub> सभी अभाज्य संख्याएँ हैं'। हालाँकि, चूंकि इस धारणा का उपयोग प्रमाण में भी नहीं किया गया है, सुधार व्यर्थ है।" <ref>{{citation|first=Torkel|last=Franzén|author-link=Torkel Franzén|title=Inexhaustibility: A Non-exhaustive Treatment|year=2004|publisher=A K Peters, Ltd|page=101}}</ref>
 === विविधताएं ===
-यूक्लिड के प्रमाण पर कई भिन्नताएँ मौजूद हैं, जिनमें निम्न शामिल हैं:
+यूक्लिड के प्रमाण पर कई भिन्नताएँ उपस्थित हैं, जिनमें निम्न शामिल हैं:
 धनात्मक पूर्णांक n का भाज्य n<nowiki>!</nowiki> 2 से n तक प्रत्येक पूर्णांक से विभाज्य है, क्योंकि यह उन सभी का गुणनफल है। इस तरह, {{nowrap|''n''! + 1}} 2 से n तक किसी भी पूर्णांक से विभाज्य नहीं है, समावेशी (प्रत्येक द्वारा विभाजित करने पर यह 1 का शेष देता है)। इस तरह {{nowrap|''n''! + 1}} या तो अभाज्य है या n से बड़े अभाज्य से विभाज्य है। किसी भी स्थिति में, प्रत्येक धनात्मक पूर्णांक n के लिए, n से कम से कम एक अभाज्य बड़ा होता है। निष्कर्ष यह है कि अभाज्य संख्याओं की संख्या अनंत है।<ref>{{Cite book|title=Further Pure Mathematics|last1=Bostock|first1=Linda|last2=Chandler|first2=Suzanne|last3=Rourke|first3=C.|date=2014-11-01|publisher=Nelson Thornes|isbn=9780859501033|pages=168|language=en}}</ref>
@@ Line 103: / Line 103: @@
 : <math> f(p,k) = \left\lfloor \frac{k}{p} \right\rfloor + \left\lfloor \frac{k}{p^2} \right\rfloor + \cdots. </math>
 : <math> f(p,k) < \frac{k}{p} + \frac{k}{p^2} + \cdots = \frac{k}{p-1} \le k. </math>
-लेकिन यदि केवल बहुत से अभाज्य संख्याएँ मौजूद हैं, तब
+लेकिन यदि केवल बहुत से अभाज्य संख्याएँ उपस्थित हैं, तब
 : <math> \lim_{k\to\infty} \frac{\left(\prod_p p\right)^k}{k!} = 0, </math>
 (अंश का अंश [[घातीय वृद्धि]] में वृद्धि करेगा, जबकि स्टर्लिंग के सन्निकटन से भाजक एकल चरघातांकी की तुलना में अधिक तेज़ी से बढ़ता है),
 इस तथ्य का खंडन करते हुए कि प्रत्येक k के लिए अंश भाजक से अधिक या उसके बराबर है।
@@ Line 116: / Line 117: @@
 === असम्पीड्यता विधि का उपयोग करके सबूत ===
-मान लीजिए कि केवल के प्राइम थे (पी<sub>1</sub>, ..., पी<sub>''k''</sub>). अंकगणित के मूलभूत प्रमेय के अनुसार, किसी भी धनात्मक पूर्णांक n को तब निरूपित किया जा सकता है
+मान लीजिए कि केवल के प्राइम थे (पी<sub>1</sub>, ..., पी<sub>''k''</sub>). अंकगणित के मूलभूत प्रमेय के अनुसार, किसी भी धनात्मक पूर्णांक n को तब निरूपित किया जा सकता है<math display=block>n = {p_1}^{e_1} {p_2}^{e_2} \cdots {p_k}^{e_k},</math>
-<math display=block>n = {p_1}^{e_1} {p_2}^{e_2} \cdots {p_k}^{e_k},</math>
 जहां गैर-नकारात्मक पूर्णांक घातांक ई<sub>''i''</sub> अभाज्य संख्याओं की परिमित-आकार की सूची के साथ संख्या का पुनर्निर्माण करने के लिए पर्याप्त हैं। तब से <math>p_i \geq 2</math> सभी i के लिए, यह उसका अनुसरण करता है <math>e_i \leq \lg n</math> सभी के लिए मैं (जहाँ <math>\lg</math> आधार -2 लघुगणक को दर्शाता है)। यह निम्न आकार के एन के लिए एक एन्कोडिंग उत्पन्न करता है ([[बिग ओ नोटेशन]] का उपयोग करके):
 :<math>O(\text{prime list size} + k \lg \lg n) = O(\lg \lg n)</math> बिट्स।
 यह बाइनरी में सीधे एन का प्रतिनिधित्व करने से कहीं अधिक कुशल एन्कोडिंग है, जो लेता है <math>N = O(\lg n)</math> बिट्स। दोषरहित संपीड़न # सीमाएं में एक स्थापित परिणाम बताता है कि आम तौर पर सूचना के एन बिट्स को एन बिट्स से कम में संपीड़ित नहीं किया जा सकता है। उपरोक्त प्रतिनिधित्व इसका उल्लंघन तब तक करता है जब n पर्याप्त रूप से बड़ा होता है <math>\lg \lg n = o(\lg n)</math>. इसलिए, अभाज्य संख्याओं की संख्या परिमित नहीं होनी चाहिए।<ref>{{citation|title=Kolmogorov complexity and algorithmic randomness|first=Alexander|last=Shen|publisher=AMS|year=2016|url=http://www.lirmm.fr/~ashen/kolmbook-eng.pdf|page=245}}</ref>
+== पर्याप्त परिणाम ==
+इस खंड के प्रमेय एक साथ यूक्लिड के प्रमेय और अन्य परिणामों को दर्शाते हैं।
-== मजबूत परिणाम ==
+=== अंकगणितीय प्रगति पर डिरिचलेट का प्रमेय ===
+{{main article|अंकगणितीय प्रगति पर डिरिचलेट की प्रमेय}}
-इस खंड के प्रमेय एक साथ यूक्लिड के प्रमेय और अन्य परिणामों को दर्शाते हैं।
+डिरिचलेट के प्रमेय में कहा गया है कि किन्हीं भी दो धनात्मक सहअभाज्य पूर्णांकों a और d के लिए a + nd के रूप में अपरिमित रूप से अनेक अभाज्य संख्याएँ होती हैं, जहाँ n भी एक धनात्मक पूर्णांक है। दूसरे शब्दों में, अपरिमित रूप से अनेक अभाज्य संख्याएँ होती हैं जो एक सापेक्ष d के अनुरूप होती हैं।
-=== अंकगणितीय प्रगति पर डिरिचलेट का प्रमेय ===
+=== अभाज्य संख्या प्रमेय ===
-{{main article|Dirichlet's theorem on arithmetic progressions}}
+{{main article|अभाज्य संख्या प्रमेय }}
-डिरिचलेट के प्रमेय में कहा गया है कि किन्हीं भी दो धनात्मक सहअभाज्य [[पूर्णांक]]ों a और d के लिए a + nd के रूप में अपरिमित रूप से अनेक अभाज्य संख्याएँ होती हैं, जहाँ n भी एक धनात्मक पूर्णांक है। दूसरे शब्दों में, ऐसे अपरिमित रूप से अनेक अभाज्य संख्याएँ हैं जो [[मॉड्यूलर अंकगणित]]ीय d के [[सर्वांगसमता संबंध]] हैं।
-=== प्रधान संख्या प्रमेय ===
+मान लीजिए {{math|''π''(''x'')}} अभाज्य-गणना फलन है जो किसी वास्तविक संख्या x के लिए x से कम या उसके बराबर अभाज्य संख्याएँ देता है। अभाज्य संख्या प्रमेय तब बताता है कि {{math|''x'' / log ''x''}}, {{math|''π''(''x'')}} के लिए एक अच्छा सन्निकटन है, इस अर्थ में कि दो कार्यों {{math|''π''(''x'')}} और {{math|''x'' / log ''x''}} के भागफल की सीमा बिना किसी सीमा के x के रूप में बढ़ती है 1 है :
-{{main article|Prime number theorem}}
-होने देना {{math|''π''(''x'')}} [[प्राइम-काउंटिंग फंक्शन]] बनें जो प्राइम्स की संख्या को कम या बराबर देता है {{mvar|x}}, किसी भी वास्तविक संख्या के लिए{{mvar|x}}. अभाज्य संख्या प्रमेय तब बताता है कि {{math|''x'' / log ''x''}} का अच्छा अनुमान है {{math|''π''(''x'')}}, इस अर्थ में कि दो कार्यों के भागफल के एक कार्य की सीमा {{math|''π''(''x'')}} और {{math|''x'' / log ''x''}} जैसा {{mvar|x}} बिना किसी सीमा के बढ़ता है 1:
 :<math>\lim_{x\rightarrow\infty} \frac{\pi(x)}{x/\log(x)}=1. </math>
@@ Line 140: / Line 142: @@
 :<math>\pi(x)\sim \frac{x}{\log x}.</math>
 इससे यूक्लिड प्रमेय प्राप्त होता है, क्योंकि <math>\lim_{x\rightarrow\infty} \frac{x}{\log x}=\infty. </math>
 === बर्ट्रेंड-चेबिशेव प्रमेय ===
 {{Short description|There are infinitely many prime numbers.}}
-संख्या सिद्धांत में, बर्ट्रेंड की परिकल्पना एक [[प्रमेय]] है जो बताती है कि किसी भी पूर्णांक के लिए <math>n > 1</math>, कम से कम एक अभाज्य संख्या हमेशा मौजूद होती है जैसे कि
+संख्या सिद्धांत में, बर्ट्रेंड की परिकल्पना एक [[प्रमेय]] है जो बताती है कि किसी भी पूर्णांक के लिए <math>n > 1</math>, कम से कम एक अभाज्य संख्या हमेशा उपस्थित होती है जैसे कि
 :<math>n < p < 2n.</math>
-बर्ट्रेंड-चेबीशेव प्रमेय को एक संबंध के रूप में भी कहा जा सकता है <math>\pi(x)</math>, कहाँ <math>\pi(x)</math> प्राइम-काउंटिंग फंक्शन है (प्राइम्स की संख्या इससे कम या इसके बराबर <math>x \,</math>):
+बर्ट्रेंड-चेबीशेव प्रमेय को एक संबंध के रूप में भी कहा जा सकता है <math>\pi(x)</math>, कहाँ <math>\pi(x)</math> अभाज्य-गणना फलन है (प्राइम्स की संख्या इससे कम या इसके बराबर <math>x \,</math>):
 :<math>\pi(x) - \pi(\tfrac{x}{2}) \ge 1,</math> सभी के लिए <math>x \ge 2.</math>
 यह कथन पहली बार 1845 में जोसेफ लुई फ्रांकोइस बर्ट्रेंड द्वारा अनुमान लगाया गया था<ref>{{Citation|first=Joseph |last=Bertrand |author-link=Joseph Bertrand |title=Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme. |journal=Journal de l'École Royale Polytechnique |issue=Cahier 30 |volume=18 |year=1845 |pages=123–140 |language=fr |url={{Google Books|WTa-qRIWckoC|page=123|plainurl=yes}}}}.</ref> (1822-1900)। बर्ट्रेंड ने स्वयं अंतराल में सभी संख्याओं के लिए अपने कथन की पुष्टि की {{nowrap|[2, 3 × 10<sup>6</sup>].}}
@@ Line 154: / Line 155: @@
 == नोट्स और संदर्भ ==
 {{reflist}}
 ==बाहरी संबंध==

Anonymous

Search

यूक्लिड का प्रमेय: Difference between revisions

Namespaces

More

Page actions

Revision as of 15:13, 8 February 2023

Contents