यूलर का कुल कार्य: Difference between revisions
No edit summary |
No edit summary |
||
(7 intermediate revisions by 3 users not shown) | |||
Line 3: | Line 3: | ||
{{distinguish|यूलर फलन}} | {{distinguish|यूलर फलन}} | ||
[[Image:EulerPhi.svg|thumb|के पहले हजार मान {{math|''φ''(''n'')}}. शीर्ष रेखा पर बिंदु दर्शाते हैं {{Math|''φ''(''p'')}} कब {{mvar|p}} | [[Image:EulerPhi.svg|thumb|के पहले हजार मान {{math|''φ''(''n'')}}. शीर्ष रेखा पर बिंदु दर्शाते हैं {{Math|''φ''(''p'')}} कब {{mvar|p}} अभाज्य संख्या है, जो है {{Math|''p'' − 1.}}<ref>{{Cite web | ||
| url = https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/euler-s-totient-function-phi-function | | url = https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/euler-s-totient-function-phi-function | ||
| title = Euler's totient function | | title = Euler's totient function | ||
| website = Khan Academy | | website = Khan Academy | ||
| access-date = 2016-02-26 | | access-date = 2016-02-26 | ||
}}</ref>]][[संख्या सिद्धांत]] में, यूलर का कुल फलन किसी दिए गए पूर्णांक तक धनात्मक पूर्णांकों {{mvar|n}} की गणना करता है | जो {{mvar|n}} अपेक्षाकृत प्रमुख हैं | इसे ग्रीक अक्षर [[phi|φ]] का प्रयोग | }}</ref>]][[संख्या सिद्धांत]] में, यूलर का कुल फलन किसी दिए गए पूर्णांक तक धनात्मक पूर्णांकों {{mvar|n}} की गणना करता है | जो {{mvar|n}} अपेक्षाकृत प्रमुख हैं | इसे ग्रीक अक्षर [[phi|φ]] का प्रयोग <math>\varphi(n)</math> या <math>\phi(n)</math>के रूप में लिखा गया है, और इसे यूलर का φ फलन भी कहा जा सकता है। दूसरे शब्दों में, यह {{math|1 ≤ ''k'' ≤ ''n''}} पूर्णांकों {{mvar|k}} की संख्या है | जिसके लिए सबसे बड़ा सामान्य भाजक {{math|gcd(''n'', ''k'')}} 1 के समान है। <ref>{{harvtxt|Long|1972|p=85}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=72}}</ref> इस रूप के पूर्णांक k को कभी-कभी {{mvar|n}} के [[योग]] के रूप में संदर्भित किया जाता है | | ||
उदाहरण के लिए {{math|1= ''n'' = 9}} के योग छह संख्याएँ 1, 2, 4, 5, 7 और 8 हैं। वे सभी 9 से अपेक्षाकृत अभाज्य हैं | किन्तु इस श्रेणी में अन्य तीन संख्याएँ, 3, 6 और 9 नहीं हैं | क्योंकि {{math|1= gcd(9, 3) = gcd(9, 6) = 3}} | उदाहरण के लिए {{math|1= ''n'' = 9}} के योग छह संख्याएँ 1, 2, 4, 5, 7 और 8 हैं। वे सभी 9 से अपेक्षाकृत अभाज्य हैं | किन्तु इस श्रेणी में अन्य तीन संख्याएँ, 3, 6 और 9 नहीं हैं | क्योंकि {{math|1= gcd(9, 3) = gcd(9, 6) = 3}} इसलिए {{math|1= ''φ''(9) = 6}}. एक अन्य उदाहरण के रूप में {{math|1= ''φ''(1) = 1}} क्योंकि {{math|1= ''n'' = 1}} के लिए केवल पूर्णांक है 1 से {{mvar|n}} तक की सीमा 1 ही है, और {{math|1= gcd(1, 1) = 1}} है। | ||
यूलर का कुल फलन एक गुणक फलन है | जिसका अर्थ है कि यदि दो संख्याएँ {{mvar|m}} और {{mvar|n}} अपेक्षाकृत अभाज्य हैं, तो {{math|1= ''φ''(''mn'') = ''φ''(''m'')''φ''(''n'')}}.<ref>{{harvtxt|Long|1972|p=162}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=80}}</ref> यह फलन पूर्णांक मॉड्यूलो {{mvar|n}} (रिंग <math>\Z/n\Z</math>) की इकाइयों के समूह का क्रम देता है। <ref>See [[#Euler's theorem|Euler's theorem]].</ref> इसका उपयोग आरएसए एन्क्रिप्शन प्रणाली को परिभाषित करने के लिए भी किया जाता है। | यूलर का कुल फलन एक गुणक फलन है | जिसका अर्थ है कि यदि दो संख्याएँ {{mvar|m}} और {{mvar|n}} अपेक्षाकृत अभाज्य हैं, तो {{math|1= ''φ''(''mn'') = ''φ''(''m'')''φ''(''n'')}}.<ref>{{harvtxt|Long|1972|p=162}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=80}}</ref> यह फलन पूर्णांक मॉड्यूलो {{mvar|n}} (रिंग <math>\Z/n\Z</math>) की इकाइयों के समूह का क्रम देता है। <ref>See [[#Euler's theorem|Euler's theorem]].</ref> इसका उपयोग आरएसए एन्क्रिप्शन प्रणाली को परिभाषित करने के लिए भी किया जाता है। | ||
== इतिहास, शब्दावली और अंकन == | == इतिहास, शब्दावली और अंकन == | ||
[[लियोनहार्ड यूलर]] ने 1763 में कार्य का प्रारंभ किया था। <ref>L. Euler "[http://eulerarchive.maa.org/pages/E271.html Theoremata arithmetica nova methodo demonstrata]" (An arithmetic theorem proved by a new method), ''Novi commentarii academiae scientiarum imperialis Petropolitanae'' (New Memoirs of the Saint-Petersburg Imperial Academy of Sciences), '''8''' (1763), 74–104. (The work was presented at the Saint-Petersburg Academy on October 15, 1759. A work with the same title was presented at the Berlin Academy on June 8, 1758). Available on-line in: [[Ferdinand Rudio]], {{abbr|ed.|editor}}, ''Leonhardi Euleri Commentationes Arithmeticae'', volume 1, in: ''Leonhardi Euleri Opera Omnia'', series 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915), [http://gallica.bnf.fr/ark:/12148/bpt6k6952c/f571.image pages 531–555]. On page 531, Euler defines {{mvar|n}} as the number of integers that are smaller than {{mvar|N}} and relatively prime to {{mvar|N}} (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), which is the phi function, φ(N).</ref><ref name="Sandifer, p. 203">Sandifer, p. 203</ref><ref>Graham et al. p. 133 note 111</ref> चूँकि, उन्होंने उस समय इसे निरूपित करने के लिए किसी विशिष्ट प्रतीक का चयन नहीं किया था। यूलर ने 1784 के | [[लियोनहार्ड यूलर]] ने 1763 में कार्य का प्रारंभ किया था। <ref>L. Euler "[http://eulerarchive.maa.org/pages/E271.html Theoremata arithmetica nova methodo demonstrata]" (An arithmetic theorem proved by a new method), ''Novi commentarii academiae scientiarum imperialis Petropolitanae'' (New Memoirs of the Saint-Petersburg Imperial Academy of Sciences), '''8''' (1763), 74–104. (The work was presented at the Saint-Petersburg Academy on October 15, 1759. A work with the same title was presented at the Berlin Academy on June 8, 1758). Available on-line in: [[Ferdinand Rudio]], {{abbr|ed.|editor}}, ''Leonhardi Euleri Commentationes Arithmeticae'', volume 1, in: ''Leonhardi Euleri Opera Omnia'', series 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915), [http://gallica.bnf.fr/ark:/12148/bpt6k6952c/f571.image pages 531–555]. On page 531, Euler defines {{mvar|n}} as the number of integers that are smaller than {{mvar|N}} and relatively prime to {{mvar|N}} (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), which is the phi function, φ(N).</ref><ref name="Sandifer, p. 203">Sandifer, p. 203</ref><ref>Graham et al. p. 133 note 111</ref> चूँकि, उन्होंने उस समय इसे निरूपित करने के लिए किसी विशिष्ट प्रतीक का चयन नहीं किया था। यूलर ने 1784 के प्रकाशन में, ग्रीक अक्षर को चुनते हुए, कार्य का और अध्ययन किया था और {{mvar|π}} इसे निरूपित करने के लिए: उन्होंने लिखा {{math|''πD''}} से कम संख्याओं की भीड़ के लिए {{mvar|D}}, और जिसके साथ कोई उभयनिष्ठ भाजक नहीं है। <ref>L. Euler, ''[http://math.dartmouth.edu/~euler/docs/originals/E564.pdf Speculationes circa quasdam insignes proprietates numerorum]'', Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18–30, or Opera Omnia, Series 1, volume 4, pp. 105–115. (The work was presented at the Saint-Petersburg Academy on October 9, 1775).</ref> यह परिभाषा वर्तमान परिभाषा से टोटिएंट फलन {{math|1=''D'' = 1}} के लिए भिन्न होती है | किन्तु अन्यथा वही है। अब-मानक संकेतन <ref name="Sandifer, p. 203"/><ref>Both {{math|''φ''(''n'')}} and {{math|''ϕ''(''n'')}} are seen in the literature. These are two forms of the lower-case Greek letter [[phi]].</ref> {{math|''φ''(''A'')}} [[गॉस]] के 1801 ग्रंथ अरिथमेटिक डिक्विजिशन से आता है | <ref>Gauss, ''Disquisitiones Arithmeticae'' article 38</ref><ref>{{cite book |last=Cajori |first=Florian |author-link=Florian Cajori |title=ए हिस्ट्री ऑफ़ मैथेमेटिकल नोटेशन वॉल्यूम II|year=1929 |publisher=Open Court Publishing Company|at=§409}}</ref> चूँकि गॉस ने तर्क के चारों ओर कोष्ठक का उपयोग नहीं किया और {{math|''φA''}} लिखा था | इस प्रकार, इसे अधिकांशतः यूलर का φ फलन या केवल φ फलन कहा जाता है। | ||
जेम्स जोसेफ सिल्वेस्टर ने 1879 में, इस कार्य के लिए टोटिएंट शब्द निर्मित किया था |,<ref>J. J. Sylvester (1879) "On certain ternary cubic-form equations", ''American Journal of Mathematics'', '''2''' : 357-393; Sylvester coins the term "totient" on [https://books.google.com/books?id=-AcPAAAAIAAJ&pg=PA361 page 361].</ref><ref>{{cite OED2|totient}}</ref> इसलिए इसे यूलर के टोटिएंट फलन, यूलर टोटिएंट या यूलर के टोटिएंट के रूप में भी जाना जाता है। जॉर्डन का टोटिएंट फलन यूलर का | जेम्स जोसेफ सिल्वेस्टर ने 1879 में, इस कार्य के लिए टोटिएंट शब्द निर्मित किया था |,<ref>J. J. Sylvester (1879) "On certain ternary cubic-form equations", ''American Journal of Mathematics'', '''2''' : 357-393; Sylvester coins the term "totient" on [https://books.google.com/books?id=-AcPAAAAIAAJ&pg=PA361 page 361].</ref><ref>{{cite OED2|totient}}</ref> इसलिए इसे यूलर के टोटिएंट फलन, यूलर टोटिएंट या यूलर के टोटिएंट के रूप में भी जाना जाता है। जॉर्डन का टोटिएंट फलन यूलर का सामान्यीकरण है। | ||
कोटिटेंट {{mvar|n}} कों {{math|''n'' − ''φ''(''n'')}} से | कोटिटेंट {{mvar|n}} कों {{math|''n'' − ''φ''(''n'')}} से परिभाषित किया जाता है | यह इससे कम या इसके समान धनात्मक पूर्णांकों की संख्या {{mvar|n}} की गणना करता है | जिसमें कम से कम [[अभाज्य संख्या]] {{mvar|n}} उभयनिष्ठ हो | | ||
== यूलर के टोटिएंट फलन की गणना == | == यूलर के टोटिएंट फलन की गणना == | ||
Line 49: | Line 45: | ||
:<math>\varphi \left(p^k\right) = p^k-p^{k-1} = p^{k-1}(p-1) = p^k \left( 1 - \tfrac{1}{p} \right).</math> | :<math>\varphi \left(p^k\right) = p^k-p^{k-1} = p^{k-1}(p-1) = p^k \left( 1 - \tfrac{1}{p} \right).</math> | ||
उपपत्ति: चूँकि {{mvar|p}} एक अभाज्य संख्या है | {{math|gcd(''p''<sup>''k''</sup>, ''m'')}} के केवल संभावित मान {{math|1, ''p'', ''p''<sup>2</sup>, ..., ''p''<sup>''k''</sup>}} | उपपत्ति: चूँकि {{mvar|p}} एक अभाज्य संख्या है | {{math|gcd(''p''<sup>''k''</sup>, ''m'')}} के केवल संभावित मान {{math|1, ''p'', ''p''<sup>2</sup>, ..., ''p''<sup>''k''</sup>}} हैं, और {{math|gcd(''p''<sup>''k''</sup>, ''m'') > 1}} होने की एकमात्र विधि है | यदि {{mvar|m}} {{mvar|p}} का गुणज है जो {{math|1=''m'' ∈ {{mset|1=''p'', 2''p'', 3''p'', ..., ''p''<sup>''k'' − 1</sup>''p'' = ''p''<sup>''k''</sup>}}}} है और {{math|''p''<sup>''k'' − 1</sup>}} ऐसे गुणज हैं | जो {{math|''p''<sup>''k''</sup>}} से अधिक नहीं हैं। इसलिए अन्य {{math|''p''<sup>''k''</sup> − ''p''<sup>''k'' − 1</sup>}} संख्याएँ सभी {{math|''p''<sup>''k''</sup>}} से अपेक्षाकृत प्रमुख हैं। | ||
==== यूलर के उत्पाद सूत्र का प्रमाण ==== | ==== यूलर के उत्पाद सूत्र का प्रमाण ==== | ||
[[अंकगणित का मौलिक प्रमेय]] कहता है कि यदि {{math|''n'' > 1}} | [[अंकगणित का मौलिक प्रमेय]] कहता है कि यदि {{math|''n'' > 1}} अनूठी अभिव्यक्ति है | <math>n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}, </math> जहाँ {{math|''p''<sub>1</sub> < ''p''<sub>2</sub> < ... < ''p''<sub>''r''</sub>}} अभाज्य संख्याएँ हैं और प्रत्येक {{math|''k''<sub>''i''</sub> ≥ 1}}. (स्थिति {{math|1=''n'' = 1}} खाली गुणनफल से मेल खाता है।) के गुणात्मक गुण का बार-बार उपयोग करना {{mvar|φ}} और के लिए सूत्र {{math|''φ''(''p''<sup>''k''</sup>)}} देता है | | ||
:<math>\begin{array} {rcl} | :<math>\begin{array} {rcl} | ||
Line 74: | Line 70: | ||
वैकल्पिक सूत्र केवल पूर्णांकों का उपयोग करता है:<math display="block">\varphi(20) = \varphi(2^2 5^1)= 2^{2-1}(2{-}1)\,5^{1-1}(5{-}1) = 2\cdot 1\cdot 1\cdot 4 = 8.</math> | वैकल्पिक सूत्र केवल पूर्णांकों का उपयोग करता है:<math display="block">\varphi(20) = \varphi(2^2 5^1)= 2^{2-1}(2{-}1)\,5^{1-1}(5{-}1) = 2\cdot 1\cdot 1\cdot 4 = 8.</math> | ||
=== फूरियर रूपांतरण === | === फूरियर रूपांतरण === | ||
Line 101: | Line 95: | ||
&=& 4 . | &=& 4 . | ||
\end{array} | \end{array} | ||
</math>यूलर उत्पाद और विभाजक योग सूत्र के विपरीत, इसके कारकों | </math>यूलर उत्पाद और विभाजक योग सूत्र के विपरीत, इसके कारकों {{mvar|n}} को जानने की आवश्यकता नहीं है | चूँकि, इसमें सबसे बड़े सामान्य विभाजक की गणना {{mvar|n}} सम्मिलित है और प्रत्येक धनात्मक पूर्णांक से कम {{mvar|n}}, जो वैसे भी गुणनखंड प्रदान करने के लिए पर्याप्त है। | ||
=== भाजक योग === | === भाजक योग === | ||
Line 108: | Line 102: | ||
:<math>\sum_{d\mid n}\varphi(d)=n,</math> | :<math>\sum_{d\mid n}\varphi(d)=n,</math> | ||
जहां योग सभी सकारात्मक विभाजकों | जहां योग सभी सकारात्मक विभाजकों {{mvar|d}} का {{mvar|n}} से अधिक है | कई तरह से सिद्ध किया जा सकता है। (अंकगणितीय फलन नोटेशन सम्मेलनों के लिए अंकगणित देखें।) | ||
प्रमाण यह ध्यान रखना है {{math|''φ''(''d'')}} [[चक्रीय समूह]] {{math|''C''<sub>''d''</sub>}} के संभावित जनरेटर की संख्या | प्रमाण यह ध्यान रखना है {{math|''φ''(''d'')}} [[चक्रीय समूह]] {{math|''C''<sub>''d''</sub>}} के संभावित जनरेटर की संख्या के समान भी है | विशेष रूप से, यदि {{math|''C''<sub>''d''</sub> {{=}} ⟨''g''⟩}} साथ {{math|1=''g''<sup>''d''</sup> = 1}}, तब {{math|''g''<sup>''k''</sup>}} प्रत्येक {{mvar|k}} कोप्राइम से {{mvar|d}} के लिए जनरेटर है | चूंकि {{math|''C''<sub>''n''</sub>}} का प्रत्येक तत्व चक्रीय [[उपसमूह]] उत्पन्न करता है और सभी उपसमूह {{math|''C''<sub>''d''</sub> ⊆ ''C''<sub>''n''</sub>}} ठीक {{math|''C''<sub>''n''</sub>}} से {{math|''φ''(''d'')}} उत्पन्न होते हैं | सूत्र इस प्रकार है। <ref>Gauss, DA art. 39, arts. 52-54</ref> समतुल्य रूप से, सूत्र एकता के nवें मूल पर प्रयुक्त समान तर्क द्वारा प्राप्त किया जा सकता है | | ||
सूत्र को प्राथमिक अंकगणित से भी प्राप्त किया जा सकता है। <ref>Graham et al. pp. 134-135</ref> उदाहरण के लिए, माना {{math|''n'' {{=}} 20}} और हर 20 के साथ 1 तक के सकारात्मक अंशों पर विचार करें | | सूत्र को प्राथमिक अंकगणित से भी प्राप्त किया जा सकता है। <ref>Graham et al. pp. 134-135</ref> उदाहरण के लिए, माना {{math|''n'' {{=}} 20}} और हर 20 के साथ 1 तक के सकारात्मक अंशों पर विचार करें | | ||
Line 128: | Line 122: | ||
\tfrac{17}{20},\,\tfrac{ 9}{10},\,\tfrac{19}{20},\,\tfrac{1}{1} | \tfrac{17}{20},\,\tfrac{ 9}{10},\,\tfrac{19}{20},\,\tfrac{1}{1} | ||
</math> | </math> | ||
ये बीस अंश सभी धनात्मक {{sfrac|''k''|''d''}} ≤ 1 हैं | जिसके प्रत्येक भाजक हैं | {{math|''d'' {{=}} 1, 2, 4, 5, 10, 20}}. प्रत्येक के रूप में 20 वाले अंश वे हैं जिनके अंश अपेक्षाकृत 20 तक हैं, अर्थात् {{sfrac|1|20}}, {{sfrac|3|20}}, {{sfrac|7|20}}, {{sfrac|9|20}}, {{sfrac|11|20}}, {{sfrac|13|20}}, {{sfrac|17|20}}, {{sfrac|19|20}}; परिभाषा के अनुसार {{math|''φ''(20)}} भिन्न है। इसी प्रकार,प्रत्येक 10 के साथ {{math|''φ''(10)}} | ये बीस अंश सभी धनात्मक {{sfrac|''k''|''d''}} ≤ 1 हैं | जिसके प्रत्येक भाजक हैं | {{math|''d'' {{=}} 1, 2, 4, 5, 10, 20}}. प्रत्येक के रूप में 20 वाले अंश वे हैं जिनके अंश अपेक्षाकृत 20 तक हैं, अर्थात् {{sfrac|1|20}}, {{sfrac|3|20}}, {{sfrac|7|20}}, {{sfrac|9|20}}, {{sfrac|11|20}}, {{sfrac|13|20}}, {{sfrac|17|20}}, {{sfrac|19|20}}; परिभाषा के अनुसार {{math|''φ''(20)}} भिन्न है। इसी प्रकार,प्रत्येक 10 के साथ {{math|''φ''(10)}} भाजक अंश है और प्रत्येक भाजक 5 के साथ {{math|''φ''(5)}} अंश है | आदि इस प्रकार बीस अंशों का समुच्चय {{math|''d''}} 20 के लिए आकार के सबसमुच्चय में विभाजित होता है | | ||
विभाजक योग सूत्र पर प्रयुक्त मोबियस उलटा देता है | विभाजक योग सूत्र पर प्रयुक्त मोबियस उलटा देता है | ||
Line 139: | Line 133: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
== कुछ मूल्य == | == कुछ मूल्य == | ||
Line 181: | Line 173: | ||
|} | |} | ||
शीर्ष रेखा के दाईं ओर ग्राफ़ में {{math|''y'' {{=}} ''n'' − 1}} | शीर्ष रेखा के दाईं ओर ग्राफ़ में {{math|''y'' {{=}} ''n'' − 1}} [[ऊपरी सीमा]] है जो सभी के लिए मान्य है {{mvar|n}} के अतिरिक्त, और यदि और केवल यदि प्राप्त किया {{mvar|n}} अभाज्य संख्या है। साधारण निचली सीमा है <math>\varphi(n) \ge \sqrt{n/2} </math>, जो ढीला है: वास्तव में, ग्राफ की सीमा श्रेष्ठ और {{math|{{sfrac|''n''|log log ''n''}}}} सीमा हीन आनुपातिक है |<ref name="hw328" /> | ||
== यूलर प्रमेय == | == यूलर प्रमेय == | ||
Line 191: | Line 183: | ||
विशेष स्थिति जहां {{mvar|n}} प्राइम है जिसे फर्मेट की छोटी प्रमेय के रूप में जाना जाता है। | विशेष स्थिति जहां {{mvar|n}} प्राइम है जिसे फर्मेट की छोटी प्रमेय के रूप में जाना जाता है। | ||
यह लैग्रेंज के प्रमेय (समूह सिद्धांत) | यह लैग्रेंज के प्रमेय (समूह सिद्धांत) और {{math|''φ''(''n'')}} इस तथ्य से आता है | पूर्णांक मॉड्यूलो के गुणक समूह का क्रम (समूह सिद्धांत) {{mvar|n}} है | | ||
[[आरएसए (एल्गोरिदम)]] इस प्रमेय पर आधारित है: इसका तात्पर्य है कि फलन का उलटा कार्य {{math|''a'' ↦ ''a<sup>e</sup>'' mod ''n''}}, जहाँ {{mvar|e}} (सार्वजनिक) एन्क्रिप्शन प्रतिपादक है, कार्य है {{math|''b'' ↦ ''b<sup>d</sup>'' mod ''n''}}, जहाँ {{mvar|d}}, (निजी) डिक्रिप्शन एक्सपोनेंट, का गुणात्मक व्युत्क्रम है | {{mvar|e}} मापांक {{math|''φ''(''n'')}}. कंप्यूटिंग की कठिनाई {{math|''φ''(''n'')}} के गुणनखंड को जाने बिना {{mvar|n}} इस प्रकार कंप्यूटिंग की कठिनाई {{mvar|d}} है | इसे [[आरएसए समस्या]] के रूप में जाना जाता है जिसे फैक्टरिंग {{mvar|n}} द्वारा हल किया जा सकता है | निजी कुंजी का स्वामी गुणनखंडन को जानता है | क्योंकि आरएसए निजी कुंजी को चुनकर बनाया जाता है | {{mvar|n}} दो (यादृच्छिक रूप से चुने गए) बड़े प्राइम्स के उत्पाद के रूप में {{mvar|p}} और {{mvar|q}}. केवल {{mvar|n}} सार्वजनिक रूप से प्रकट किया गया है, और [[पूर्णांक गुणनखंडन]] को देखते हुए हमारे पास गारंटी है कि किसी और को गुणनखंडन के बारे में पता नहीं है। | [[आरएसए (एल्गोरिदम)]] इस प्रमेय पर आधारित है: इसका तात्पर्य है कि फलन का उलटा कार्य {{math|''a'' ↦ ''a<sup>e</sup>'' mod ''n''}}, जहाँ {{mvar|e}} (सार्वजनिक) एन्क्रिप्शन प्रतिपादक है, कार्य है {{math|''b'' ↦ ''b<sup>d</sup>'' mod ''n''}}, जहाँ {{mvar|d}}, (निजी) डिक्रिप्शन एक्सपोनेंट, का गुणात्मक व्युत्क्रम है | {{mvar|e}} मापांक {{math|''φ''(''n'')}}. कंप्यूटिंग की कठिनाई {{math|''φ''(''n'')}} के गुणनखंड को जाने बिना {{mvar|n}} इस प्रकार कंप्यूटिंग की कठिनाई {{mvar|d}} है | इसे [[आरएसए समस्या]] के रूप में जाना जाता है जिसे फैक्टरिंग {{mvar|n}} द्वारा हल किया जा सकता है | निजी कुंजी का स्वामी गुणनखंडन को जानता है | क्योंकि आरएसए निजी कुंजी को चुनकर बनाया जाता है | {{mvar|n}} दो (यादृच्छिक रूप से चुने गए) बड़े प्राइम्स के उत्पाद के रूप में {{mvar|p}} और {{mvar|q}}. केवल {{mvar|n}} सार्वजनिक रूप से प्रकट किया गया है, और [[पूर्णांक गुणनखंडन]] को देखते हुए हमारे पास गारंटी है कि किसी और को गुणनखंडन के बारे में पता नहीं है। | ||
Line 212: | Line 204: | ||
{{math|''φ''(''n'')}} के लिए भी है {{math|''n'' ≥ 3}}. <p>इसके अतिरिक्त, यदि {{mvar|n}} है {{mvar|r}} विशिष्ट विषम अभाज्य कारक, {{math|2<sup>''r''</sup> {{!}} ''φ''(''n'')}</p> | {{math|''φ''(''n'')}} के लिए भी है {{math|''n'' ≥ 3}}. <p>इसके अतिरिक्त, यदि {{mvar|n}} है {{mvar|r}} विशिष्ट विषम अभाज्य कारक, {{math|2<sup>''r''</sup> {{!}} ''φ''(''n'')}</p> | ||
<li> किसी के लिए {{math|''a'' > 1}} और {{math|''n'' > 6}} ऐसा है कि {{math|4 ∤ ''n''}} वहाँ | <li> किसी के लिए {{math|''a'' > 1}} और {{math|''n'' > 6}} ऐसा है कि {{math|4 ∤ ''n''}} वहाँ उपस्थित है {{math|''l'' ≥ 2''n''}} ऐसा है कि {{math|''l'' {{!}} ''φ''(''a<sup>n</sup>'' − 1)}}.</li><li> <math>\frac{\varphi(n)}{n}=\frac{\varphi(\operatorname{rad}(n))}{\operatorname{rad}(n)}</math> | ||
<p>जहाँ {{math|rad(''n'')}} | <p>जहाँ {{math|rad(''n'')}} पूर्णांक का मूलांक है | {{mvar|n}} (विभाजन करने वाले सभी विशिष्ट अभाज्य संख्याओं का गुणनफल {{mvar|[[radical of an integer|n]]}}).</p></li> | ||
<math>\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}</math> <ref>Dineva (in external refs), prop. 1</ref> | <math>\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}</math> <ref>Dineva (in external refs), prop. 1</ref> | ||
Line 230: | Line 222: | ||
<math>\sum_\stackrel{1\le k\le n}{\operatorname{gcd}(k,m)=1} \!\!\!\! 1 = n \frac {\varphi(m)}{m} + O \left ( 2^{\omega(m)} \right )</math> | <math>\sum_\stackrel{1\le k\le n}{\operatorname{gcd}(k,m)=1} \!\!\!\! 1 = n \frac {\varphi(m)}{m} + O \left ( 2^{\omega(m)} \right )</math> | ||
<p>जहाँ {{math|''m'' > 1}} | <p>जहाँ {{math|''m'' > 1}} सकारात्मक पूर्णांक है और {{math|''ω''(''m'')}} के विशिष्ट प्रमुख कारकों की संख्या {{mvar|m}} है |<ref>Bordellès in the [[#External links|external links]]</ref> </p> | ||
===मेनन की पहचान=== | ===मेनन की पहचान=== | ||
Line 242: | Line 234: | ||
== कार्य उत्पन्न करना == | == कार्य उत्पन्न करना == | ||
[[डिरिचलेट श्रृंखला]] | [[डिरिचलेट श्रृंखला]] के लिए {{math|''φ''(''n'')}} को [[रीमैन जीटा फ़ंक्शन|रीमैन जीटा फलन]] के रूप में लिखा जा सकता है |<ref>{{harvnb|Hardy|Wright|1979|loc=thm. 288}}</ref> | ||
:<math>\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}</math> | :<math>\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}</math> | ||
जहां बाईं ओर <math>\Re (s)>2</math> के लिए अभिसरण होता है . | जहां बाईं ओर <math>\Re (s)>2</math> के लिए अभिसरण होता है . | ||
Line 254: | Line 246: | ||
== विकास दर == | == विकास दर == | ||
हार्डी एंड राइट के शब्दों में,{{math|''φ''(''n'')}} का क्रम | हार्डी एंड राइट के शब्दों में,{{math|''φ''(''n'')}} का क्रम सदैव 'लगभग' {{mvar|n}} होता है |<ref>{{harvnb|Hardy|Wright|1979|loc=intro to § 18.4}}</ref> पहला <ref>{{harvnb|Hardy|Wright|1979|loc=thm. 326}}</ref> | ||
:<math>\lim\sup \frac{\varphi(n)}{n}= 1,</math> | :<math>\lim\sup \frac{\varphi(n)}{n}= 1,</math> | ||
Line 260: | Line 252: | ||
:<math>\frac{\varphi(n)}{n^{1-\delta}}\rightarrow\infty.</math> | :<math>\frac{\varphi(n)}{n^{1-\delta}}\rightarrow\infty.</math> | ||
इन दोनों सूत्रों को | इन दोनों सूत्रों को {{math|''φ''(''n'')}} और [[भाजक समारोह|भाजक फलन]] {{math|''σ''(''n'')}}. सूत्र से थोड़ा अधिक प्रयोग करके सिद्ध किया जा सकता है | | ||
वास्तव में, दूसरे सूत्र के प्रमाण के समय, असमानता होती है | | वास्तव में, दूसरे सूत्र के प्रमाण के समय, असमानता होती है | | ||
Line 284: | Line 276: | ||
औसत आदेश के लिए, हमारे पास है |<ref name=Wal1963/><ref name=SMC2425>Sándor, Mitrinović & Crstici (2006) pp.24–25</ref> | औसत आदेश के लिए, हमारे पास है |<ref name=Wal1963/><ref name=SMC2425>Sándor, Mitrinović & Crstici (2006) pp.24–25</ref> | ||
:<math>\varphi(1)+\varphi(2)+\cdots+\varphi(n) = \frac{3n^2}{\pi^2}+O\left(n(\log n)^\frac23(\log\log n)^\frac43\right) \quad\text{as }n\rightarrow\infty,</math> | :<math>\varphi(1)+\varphi(2)+\cdots+\varphi(n) = \frac{3n^2}{\pi^2}+O\left(n(\log n)^\frac23(\log\log n)^\frac43\right) \quad\text{as }n\rightarrow\infty,</math> | ||
[[अर्नोल्ड वाल्फिज़]] के कारण, इसका प्रमाण इवान मटेवेविच विनोग्रादोव के कारण घातीय रकम पर अनुमानों का | [[अर्नोल्ड वाल्फिज़]] के कारण, इसका प्रमाण इवान मटेवेविच विनोग्रादोव के कारण घातीय रकम पर अनुमानों का उपयोग करता है | एम. विनोग्रादोव और एन. एम. कोरोबोव है। | ||
वैन डेर कॉर्पुट और विनोग्रादोव के विधियों के संयोजन से, H.-Q. लियू (ऑन यूलर फलन। प्रोक। रॉय। सोक। एडिनबर्ग सेक्ट। ए 146 (2016), नंबर 4, 769-775) त्रुटि शब्द में सुधार किया है | | वैन डेर कॉर्पुट और विनोग्रादोव के विधियों के संयोजन से, H.-Q. लियू (ऑन यूलर फलन। प्रोक। रॉय। सोक। एडिनबर्ग सेक्ट। ए 146 (2016), नंबर 4, 769-775) त्रुटि शब्द में सुधार किया है | | ||
Line 290: | Line 282: | ||
O\left(n(\log n)^\frac23(\log\log n)^\frac13\right) | O\left(n(\log n)^\frac23(\log\log n)^\frac13\right) | ||
</math> | </math> | ||
(यह वर्तमान में इस प्रकार का सबसे अच्छा ज्ञात अनुमान है)। बिग ओ नोटेशन बड़ा {{mvar|O}} | (यह वर्तमान में इस प्रकार का सबसे अच्छा ज्ञात अनुमान है)। बिग ओ नोटेशन बड़ा {{mvar|O}} ऐसी मात्रा के लिए खड़ा है जो निरंतर समय के कार्य {{mvar|n}} से बंधी है कोष्ठक के अंदर (जो की {{math|''n''<sup>2</sup>}} तुलना में छोटा है). | ||
इस परिणाम का उपयोग सिद्ध करने के लिए किया जा सकता है | <ref>{{harvnb|Hardy|Wright|1979|loc=thm. 332}}</ref> | इस परिणाम का उपयोग सिद्ध करने के लिए किया जा सकता है | <ref>{{harvnb|Hardy|Wright|1979|loc=thm. 332}}</ref> यादृच्छिक रूप से चुनी गई दो संख्याओं के अपेक्षाकृत {{sfrac|6|{{pi}}<sup>2</sup>}} अभाज्य होने की प्रायिकता है | | ||
== | == निरंतर मूल्यों का अनुपात == | ||
1950 में सोमयाजुलु सिद्ध हुआ | <ref name=Rib38>Ribenboim, p.38</ref><ref name=SMC16>Sándor, Mitrinović & Crstici (2006) p.16</ref> | 1950 में सोमयाजुलु सिद्ध हुआ | <ref name=Rib38>Ribenboim, p.38</ref><ref name=SMC16>Sándor, Mitrinović & Crstici (2006) p.16</ref> | ||
Line 310: | Line 302: | ||
== कुल संख्या == | == कुल संख्या == | ||
टोटिएंट नंबर यूलर के टोटिएंट फलन का मान है | अर्थात, a {{mvar|m}} जिसके लिए कम से कम {{mvar|n}} | टोटिएंट नंबर यूलर के टोटिएंट फलन का मान है | अर्थात, a {{mvar|m}} जिसके लिए कम से कम {{mvar|n}} है | जिसके लिए {{math|''φ''(''n'') {{=}} ''m''}}. कुल संख्या की संयोजकता या बहुलता {{mvar|m}} इस समीकरण के समाधान की संख्या है। <ref name=Guy144>Guy (2004) p.144</ref> नॉनटोटिएंट प्राकृतिक संख्या है जो टोटिएंट संख्या नहीं है। 1 से अधिक प्रत्येक विषम पूर्णांक तुच्छ रूप से गैर-परमाणु है। यहाँ अपरिमित रूप से बहुत से अचिंतक भी हैं |<ref name=SC230>Sándor & Crstici (2004) p.230</ref> और वास्तव में प्रत्येक धनात्मक पूर्णांक का गुणज होता है जो सम अचिंतक होता है।<ref name=Zha1993>{{cite journal | zbl=0772.11001 | last=Zhang | first=Mingzhi | title=नास्तिकों पर| journal=[[Journal of Number Theory]] | volume=43 | number=2 | pages=168–172 | year=1993 | issn=0022-314X | doi=10.1006/jnth.1993.1014| doi-access=free }}</ref> | ||
दी गई सीमा तक कुल संख्याओं की संख्या {{mvar|x}} है | | दी गई सीमा तक कुल संख्याओं की संख्या {{mvar|x}} है | | ||
Line 321: | Line 313: | ||
:<math>\Big\vert\{ n : \varphi(n) \le x \}\Big\vert = \frac{\zeta(2)\zeta(3)}{\zeta(6)} \cdot x + R(x)</math> | :<math>\Big\vert\{ n : \varphi(n) \le x \}\Big\vert = \frac{\zeta(2)\zeta(3)}{\zeta(6)} \cdot x + R(x)</math> | ||
जहां त्रुटि शब्द {{mvar|R}} अधिक से अधिक क्रम में {{math|{{sfrac|''x''|(log ''x'')<sup>''k''</sup>}}}} है | किसी भी सकारात्मक {{mvar|k}} के लिए .<ref name="SMC22">Sándor et al (2006) p.22</ref> यह ज्ञात है कि की बहुलता {{mvar|m}} से अधिक है {{math|''m''<sup>''δ''</sup>}} असीम रूप से अधिकांशतः किसी के लिए {{math|''δ'' < 0.55655}}.<ref name="SMC21">Sándor et al (2006) p.21</ref><ref name="Guy145">Guy (2004) p.145</ref> है | | जहां त्रुटि शब्द {{mvar|R}} अधिक से अधिक क्रम में {{math|{{sfrac|''x''|(log ''x'')<sup>''k''</sup>}}}} है | किसी भी सकारात्मक {{mvar|k}} के लिए .<ref name="SMC22">Sándor et al (2006) p.22</ref> यह ज्ञात है कि की बहुलता {{mvar|m}} से अधिक है {{math|''m''<sup>''δ''</sup>}} असीम रूप से अधिकांशतः किसी के लिए {{math|''δ'' < 0.55655}}.<ref name="SMC21">Sándor et al (2006) p.21</ref><ref name="Guy145">Guy (2004) p.145</ref> है | | ||
=== फोर्ड की प्रमेय === | === फोर्ड की प्रमेय === | ||
Line 329: | Line 318: | ||
चूँकि, कोई संख्या नहीं {{mvar|m}} बहुलता से जाना जाता है | {{math|''k'' {{=}} 1}}. कारमाइकल का संपूर्ण कार्य अनुमान यह कथन है कि ऐसा कोई {{mvar|m}} नहीं है |.<ref name=SC228>Sándor & Crstici (2004) p.228</ref> | चूँकि, कोई संख्या नहीं {{mvar|m}} बहुलता से जाना जाता है | {{math|''k'' {{=}} 1}}. कारमाइकल का संपूर्ण कार्य अनुमान यह कथन है कि ऐसा कोई {{mvar|m}} नहीं है |.<ref name=SC228>Sándor & Crstici (2004) p.228</ref> | ||
===पूर्ण सम संख्याएं=== | ===पूर्ण सम संख्याएं=== | ||
{{main article|पूर्ण सम संख्याएं}} | {{main article|पूर्ण सम संख्याएं}} | ||
पूर्ण कुल संख्या एक पूर्णांक है जो इसके पुनरावृत्त कुलों के योग के समान है। अर्थात्, हम टोटिएंट फलन को संख्या n पर प्रयुक्त करते हैं, इसे परिणामी टोटिएंट पर फिर से प्रयुक्त करते हैं, और इसी तरह, जब तक कि संख्या 1 तक नहीं पहुंच जाती है, और संख्याओं के परिणामी क्रम को | पूर्ण कुल संख्या एक पूर्णांक है जो इसके पुनरावृत्त कुलों के योग के समान है। अर्थात्, हम टोटिएंट फलन को संख्या n पर प्रयुक्त करते हैं, इसे परिणामी टोटिएंट पर फिर से प्रयुक्त करते हैं, और इसी तरह, जब तक कि संख्या 1 तक नहीं पहुंच जाती है, और संख्याओं के परिणामी क्रम को साथ जोड़ देते हैं; यदि योग n के समान है, तो n पूर्ण पूर्ण संख्या है। | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
Line 342: | Line 329: | ||
{{main article|रचनात्मक बहुभुज}} | {{main article|रचनात्मक बहुभुज}} | ||
डिसक्विजिशन अरिथमेटिका के अंतिम खंड में <ref>Gauss, DA. The 7th § is arts. 336–366</ref><ref>Gauss proved if {{mvar|n}} satisfies certain conditions then the {{mvar|n}}-gon can be constructed. In 1837 [[Pierre Wantzel]] proved the converse, if the {{mvar|n}}-gon is constructible, then {{mvar|n}} must satisfy Gauss's conditions</ref> गॉस सिद्ध करता है | <ref>Gauss, DA, art 366</ref> कि | डिसक्विजिशन अरिथमेटिका के अंतिम खंड में <ref>Gauss, DA. The 7th § is arts. 336–366</ref><ref>Gauss proved if {{mvar|n}} satisfies certain conditions then the {{mvar|n}}-gon can be constructed. In 1837 [[Pierre Wantzel]] proved the converse, if the {{mvar|n}}-gon is constructible, then {{mvar|n}} must satisfy Gauss's conditions</ref> गॉस सिद्ध करता है | <ref>Gauss, DA, art 366</ref> कि नियमित {{mvar|n}}-गॉन का निर्माण स्ट्रेटेज और कंपास से किया जा सकता है | यदि {{math|''φ''(''n'')}} 2 की शक्ति है। यदि {{mvar|n}} विषम अभाज्य संख्या की शक्ति है,| टोटिएंट के लिए सूत्र कहता है कि इसका टोटिएंट केवल दो की शक्ति हो सकता है | {{mvar|n}} पहली शक्ति है और {{math|''n'' − 1}} 2 की शक्ति है। वे अभाज्य संख्याएँ जो 2 की शक्ति से अधिक होती हैं,| [[फर्मेट प्राइम]] कहलाती हैं, और केवल पाँच ज्ञात हैं: 3, 5, 17, 257, और 65537 है। फर्मेट और गॉस इनके बारे में जानते थे। कोई भी यह सिद्ध करने में सक्षम नहीं है कि क्या और भी हैं। | ||
इस प्रकार, | इस प्रकार, नियमित {{mvar|n}}-गॉन का स्ट्रेटएज-एंड-कम्पास निर्माण होता है | यदि n विशिष्ट फर्मेट प्राइम्स और 2 की किसी भी शक्ति का उत्पाद है। पहले कुछ ऐसे {{mvar|n}} हैं |<ref>Gauss, DA, art. 366. This list is the last sentence in the ''Disquisitiones''</ref> | ||
:2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... {{OEIS|A003401}}. | :2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... {{OEIS|A003401}}. | ||
Line 355: | Line 342: | ||
{{main article|आरएसए (एल्गोरिदम)}} | {{main article|आरएसए (एल्गोरिदम)}} | ||
आरएसए प्रणाली की स्थापना में बड़ी अभाज्य संख्याओं | आरएसए प्रणाली की स्थापना में बड़ी अभाज्य संख्याओं {{mvar|p}} और {{mvar|q}}, को चुनना {{math|''n'' {{=}} ''pq''}} और {{math|''k'' {{=}} ''φ''(''n'')}},की गणना करना और दो संख्याएँ {{mvar|e}} और {{mvar|d}} सम्मिलित है | कि {{math|''ed'' ≡ 1 (mod ''k'')}}. संख्या {{mvar|n}} और {{mvar|e}} (एन्क्रिप्शन कुंजी ) जनता के लिए जारी की जाती हैं, और {{mvar|d}} (डिक्रिप्शन कुंजी ) को निजी रखा जाता है। | ||
संदेश, | संदेश, पूर्णांक द्वारा दर्शाया गया {{mvar|m}}, जहाँ {{math|0 < ''m'' < ''n''}}, कंप्यूटिंग {{math|''S'' {{=}} ''m''<sup>''e''</sup> (mod ''n'')}} द्वारा एन्क्रिप्ट किया गया है | | ||
इसे कंप्यूटिंग | इसे कंप्यूटिंग {{math|''t'' {{=}} ''S''<sup>''d''</sup> (mod ''n'')}} द्वारा डिक्रिप्ट किया जाता है | यूलर के प्रमेय का उपयोग यह दिखाने के लिए किया जा सकता है कि यदि {{math|0 < ''t'' < ''n''}}, तब {{math|''t'' {{=}} ''m''}}. | ||
संख्या होने पर आरएसए प्रणाली की सुरक्षा से समझौता किया जाएगा {{mvar|n}} को कुशलता से फैक्टर किया जा सकता है या यदि {{math|''φ''(''n'')}} बिना फैक्टरिंग के कुशलता से | संख्या होने पर आरएसए प्रणाली की सुरक्षा से समझौता किया जाएगा {{mvar|n}} को कुशलता से फैक्टर किया जा सकता है या यदि {{math|''φ''(''n'')}} बिना फैक्टरिंग के कुशलता से {{mvar|n}} गणना की जा सकती है | | ||
== अनसुलझी समस्याएं == | == अनसुलझी समस्याएं == | ||
Line 367: | Line 354: | ||
=== लेहमर का अनुमान === | === लेहमर का अनुमान === | ||
{{main article| | {{main article|लेहमर की समस्या}} | ||
यदि {{mvar|p}} प्रधान है, तो {{math|''φ''(''p'') {{=}} ''p'' − 1}}. 1932 में डी. एच. लेहमर ने पूछा कि क्या कोई मिश्रित संख्याएँ {{mvar|n}} हैं | ऐसा है कि {{math|''φ''(''n'') }} विभाजित करता है {{math|''n'' − 1}}. कोई नहीं जानता है।<ref>Ribenboim, pp. 36–37.</ref> | |||
1933 में उन्होंने सिद्ध कर दिया कि यदि कोई ऐसा {{mvar|n}} उपस्थित है, यह विषम, वर्ग रहित और कम से कम सात अभाज्य संख्याओं से विभाज्य होना चाहिए (अर्थात {{math|''ω''(''n'') ≥ 7}}). 1980 में कोहेन और हागिस ने यह सिद्ध कर दिया {{math|''n'' > 10<sup>20</sup>}} ओर वो {{math|''ω''(''n'') ≥ 14}}.<ref>{{cite journal | zbl=0436.10002 | last1=Cohen | first1=Graeme L. | last2=Hagis | first2=Peter Jr. | title=On the number of prime factors of {{mvar|n}} if {{math|''φ''(''n'')}} divides {{math|''n'' − 1}} | journal=Nieuw Arch. Wiskd. |series=III Series | volume=28 | pages=177–185 | year=1980 | issn=0028-9825 }}</ref> आगे, हैगिस ने दिखाया कि यदि 3 विभाजित होता है | {{mvar|n}} तब {{math|''n'' > 10<sup>1937042</sup>}} और {{math|''ω''(''n'') ≥ 298848}}.<ref>{{cite journal | zbl=0668.10006 | last=Hagis | first=Peter Jr. | title=On the equation {{math|''M''·φ(''n'') {{=}} ''n'' − 1}} | journal=Nieuw Arch. Wiskd. |series=IV Series | volume=6 | number=3 | pages=255–261 | year=1988 | issn=0028-9825 }}</ref><ref name="Guy142">Guy (2004) p.142</ref> | | |||
=== कारमाइकल का अनुमान === | === कारमाइकल का अनुमान === | ||
{{main article| | {{main article|कारमाइकल का कार्य अनुमान}} | ||
यह बताता है कि कोई संख्या नहीं है {{mvar|n}} गुण के साथ कि अन्य सभी नंबरों के लिए {{mvar|m}}, {{math|''m'' ≠ ''n''}}, {{math|''φ''(''m'') ≠ ''φ''(''n'')}}. ऊपर फोर्ड की प्रमेय देखें। | |||
जैसा कि मुख्य लेख में कहा गया है, यदि इस अनुमान के लिए एकल प्रति उदाहरण है, तो असीम रूप से कई प्रति उदाहरण होने चाहिए, और सबसे छोटे वाले के पास आधार 10 में कम से कम दस अरब अंक हैं।<ref name=Guy144/> | |||
=== रीमैन परिकल्पना === | === रीमैन परिकल्पना === | ||
रीमैन परिकल्पना | रीमैन परिकल्पना सही है यदि और केवल यदि असमानता है | | ||
:<math>\frac{n}{\varphi (n)}<e^\gamma \log\log n+\frac{e^\gamma (4+\gamma-\log 4\pi)}{\sqrt{\log n}}</math> | :<math>\frac{n}{\varphi (n)}<e^\gamma \log\log n+\frac{e^\gamma (4+\gamma-\log 4\pi)}{\sqrt{\log n}}</math> | ||
सभी | सभी {{math|''n'' ≥ ''p''<sub>120569</sub>#}} के लिए सत्य है | जहाँ {{mvar|γ}} यूलर स्थिरांक है और {{math|''p''<sub>120569</sub>#}} प्राथमिक {{math|120569}} अभाज्य संख्याओं का गुणनफल है।<ref>{{Cite book |last1=Broughan |first1=Kevin |title=Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents |publisher=Cambridge University Press |year=2017 |edition=First |isbn=978-1-107-19704-6}} Corollary 5.35</ref> | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[कारमाइकल समारोह|कारमाइकल फलन]] | * [[कारमाइकल समारोह|कारमाइकल फलन]] | ||
* डफिन-शेफ़र अनुमान | * डफिन-शेफ़र अनुमान | ||
* | *फर्मेट की छोटी प्रमेय सामान्यीकरण फर्मेट की छोटी प्रमेय का सामान्यीकरण | ||
* अत्यधिक समग्र संख्या | * अत्यधिक समग्र संख्या | ||
*पूर्णांक मॉड्यूलो का गुणक समूह n|पूर्णांक मॉड्यूलो का गुणक समूह {{mvar|n}} | *पूर्णांक मॉड्यूलो का गुणक समूह n|पूर्णांक मॉड्यूलो का गुणक समूह {{mvar|n}} | ||
* | * [[रामनुजन शूम]] | ||
* [[संपूर्ण सारांश समारोह|संपूर्ण सारांश फलन]] | * [[संपूर्ण सारांश समारोह|संपूर्ण सारांश फलन]] | ||
*डेडेकाइंड का साई फलन | *डेडेकाइंड का साई फलन | ||
Line 514: | Line 496: | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
* {{springer|title=Totient function|id=p/t110040}} | * {{springer|title=Totient function|id=p/t110040}} | ||
*[http://mathcenter.oxford.emory.edu/site/math125/chineseRemainderTheorem/ Euler's φ Function and the Chinese Remainder Theorem — proof that {{math|''φ''(''n'')}} is multiplicative] | *[http://mathcenter.oxford.emory.edu/site/math125/chineseRemainderTheorem/ Euler's φ Function and the Chinese Remainder Theorem — proof that {{math|''φ''(''n'')}} is multiplicative] | ||
Line 522: | Line 504: | ||
{{Totient}} | {{Totient}} | ||
[[Category: | [[Category:Articles with hatnote templates targeting a nonexistent page]] | ||
[[Category:CS1 Deutsch-language sources (de)]] | |||
[[Category:Collapse templates]] | |||
[[Category:Created On 26/04/2023]] | [[Category:Created On 26/04/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Missing redirects]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Sidebars with styles needing conversion]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates generating microformats]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that are not mobile friendly]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Wikipedia metatemplates]] | |||
[[Category:गुणक कार्य]] | |||
[[Category:प्रमाण युक्त लेख]] | |||
[[Category:बीजगणित]] | |||
[[Category:मॉड्यूलर अंकगणित]] | |||
[[Category:लियोनहार्ड यूलर]] | |||
[[Category:संख्या सिद्धांत]] |
Latest revision as of 17:54, 17 May 2023
संख्या सिद्धांत में, यूलर का कुल फलन किसी दिए गए पूर्णांक तक धनात्मक पूर्णांकों n की गणना करता है | जो n अपेक्षाकृत प्रमुख हैं | इसे ग्रीक अक्षर φ का प्रयोग या के रूप में लिखा गया है, और इसे यूलर का φ फलन भी कहा जा सकता है। दूसरे शब्दों में, यह 1 ≤ k ≤ n पूर्णांकों k की संख्या है | जिसके लिए सबसे बड़ा सामान्य भाजक gcd(n, k) 1 के समान है। [2][3] इस रूप के पूर्णांक k को कभी-कभी n के योग के रूप में संदर्भित किया जाता है |
उदाहरण के लिए n = 9 के योग छह संख्याएँ 1, 2, 4, 5, 7 और 8 हैं। वे सभी 9 से अपेक्षाकृत अभाज्य हैं | किन्तु इस श्रेणी में अन्य तीन संख्याएँ, 3, 6 और 9 नहीं हैं | क्योंकि gcd(9, 3) = gcd(9, 6) = 3 इसलिए φ(9) = 6. एक अन्य उदाहरण के रूप में φ(1) = 1 क्योंकि n = 1 के लिए केवल पूर्णांक है 1 से n तक की सीमा 1 ही है, और gcd(1, 1) = 1 है।
यूलर का कुल फलन एक गुणक फलन है | जिसका अर्थ है कि यदि दो संख्याएँ m और n अपेक्षाकृत अभाज्य हैं, तो φ(mn) = φ(m)φ(n).[4][5] यह फलन पूर्णांक मॉड्यूलो n (रिंग ) की इकाइयों के समूह का क्रम देता है। [6] इसका उपयोग आरएसए एन्क्रिप्शन प्रणाली को परिभाषित करने के लिए भी किया जाता है।
इतिहास, शब्दावली और अंकन
लियोनहार्ड यूलर ने 1763 में कार्य का प्रारंभ किया था। [7][8][9] चूँकि, उन्होंने उस समय इसे निरूपित करने के लिए किसी विशिष्ट प्रतीक का चयन नहीं किया था। यूलर ने 1784 के प्रकाशन में, ग्रीक अक्षर को चुनते हुए, कार्य का और अध्ययन किया था और π इसे निरूपित करने के लिए: उन्होंने लिखा πD से कम संख्याओं की भीड़ के लिए D, और जिसके साथ कोई उभयनिष्ठ भाजक नहीं है। [10] यह परिभाषा वर्तमान परिभाषा से टोटिएंट फलन D = 1 के लिए भिन्न होती है | किन्तु अन्यथा वही है। अब-मानक संकेतन [8][11] φ(A) गॉस के 1801 ग्रंथ अरिथमेटिक डिक्विजिशन से आता है | [12][13] चूँकि गॉस ने तर्क के चारों ओर कोष्ठक का उपयोग नहीं किया और φA लिखा था | इस प्रकार, इसे अधिकांशतः यूलर का φ फलन या केवल φ फलन कहा जाता है।
जेम्स जोसेफ सिल्वेस्टर ने 1879 में, इस कार्य के लिए टोटिएंट शब्द निर्मित किया था |,[14][15] इसलिए इसे यूलर के टोटिएंट फलन, यूलर टोटिएंट या यूलर के टोटिएंट के रूप में भी जाना जाता है। जॉर्डन का टोटिएंट फलन यूलर का सामान्यीकरण है।
कोटिटेंट n कों n − φ(n) से परिभाषित किया जाता है | यह इससे कम या इसके समान धनात्मक पूर्णांकों की संख्या n की गणना करता है | जिसमें कम से कम अभाज्य संख्या n उभयनिष्ठ हो |
यूलर के टोटिएंट फलन की गणना
φ(n) की गणना के लिए कई सूत्र हैं |
यूलर का उत्पाद सूत्र
य़ह कहता है
जहां गुणनफल विभाजित होने वाली अलग-अलग अभाज्य संख्याओं n के ऊपर है | (संकेतन के लिए, अंकगणितीय फलन संकेतन देखें।) |
समतुल्य सूत्रीकरण है |
इन सूत्रों का प्रमाण दो महत्वपूर्ण तथ्यों पर निर्भर करता है।
φ एक गुणक फलन है
इसका अर्थ है कि यदि gcd(m, n) = 1, तो φ(m) φ(n) = φ(mn)। उपपत्ति की रूपरेखा है | मान लीजिए A, B, C धनात्मक पूर्णांकों के समुच्चय हैं | जो क्रमशः m, n, mn के सहअभाज्य और उससे कम हैं,| जिससे |A| = φ(m), आदि फिर चीनी शेष प्रमेय द्वारा A × B और C के बीच एक आपत्ति है।
प्रमुख शक्ति तर्क के लिए φ का मान
यदि p अभाज्य है और k ≥ 1 है, तो
उपपत्ति: चूँकि p एक अभाज्य संख्या है | gcd(pk, m) के केवल संभावित मान 1, p, p2, ..., pk हैं, और gcd(pk, m) > 1 होने की एकमात्र विधि है | यदि m p का गुणज है जो m ∈ {p, 2p, 3p, ..., pk − 1p = pk} है और pk − 1 ऐसे गुणज हैं | जो pk से अधिक नहीं हैं। इसलिए अन्य pk − pk − 1 संख्याएँ सभी pk से अपेक्षाकृत प्रमुख हैं।
यूलर के उत्पाद सूत्र का प्रमाण
अंकगणित का मौलिक प्रमेय कहता है कि यदि n > 1 अनूठी अभिव्यक्ति है | जहाँ p1 < p2 < ... < pr अभाज्य संख्याएँ हैं और प्रत्येक ki ≥ 1. (स्थिति n = 1 खाली गुणनफल से मेल खाता है।) के गुणात्मक गुण का बार-बार उपयोग करना φ और के लिए सूत्र φ(pk) देता है |
यह यूलर के उत्पाद सूत्र के दोनों संस्करण देता है।
वैकल्पिक प्रमाण जिसके लिए गुणात्मक गुण की आवश्यकता नहीं होती है | किन्तु समुच्चय पर प्रयुक्त समावेशन-बहिष्करण सिद्धांत का उपयोग करता है | प्रधान विभाजकों द्वारा विभाज्य पूर्णांकों के समुच्चय को छोड़कर बहिष्करण सिद्धांत का उपयोग करता है।
उदाहरण
शब्दों में: 20 के विशिष्ट अभाज्य गुणनखंड 2 और 5 हैं; 1 से 20 तक के बीस पूर्णांकों में से आधे 2 से विभाज्य हैं, दस को छोड़कर; उनमें से पाँचवाँ भाग 5 से विभाज्य है, जिससे आठ संख्याएँ 20 तक सहअभाज्य हो जाती हैं; ये हैं: 1, 3, 7, 9, 11, 13, 17, 19 है।
वैकल्पिक सूत्र केवल पूर्णांकों का उपयोग करता है:
फूरियर रूपांतरण
टोटिएंट महानतम सामान्य भाजक का असतत फूरियर रूपांतरण है | जिसका मूल्यांकन 1 पर किया जाता है।[16]
माना
जहाँ xk = gcd(k,n) के लिए k ∈ {1, ..., n}. तब
इस सूत्र का वास्तविक भाग है |
उदाहरण के लिए, का उपयोग करना और :
भाजक योग
गॉस द्वारा स्थापित गुण ,[17] वह
जहां योग सभी सकारात्मक विभाजकों d का n से अधिक है | कई तरह से सिद्ध किया जा सकता है। (अंकगणितीय फलन नोटेशन सम्मेलनों के लिए अंकगणित देखें।)
प्रमाण यह ध्यान रखना है φ(d) चक्रीय समूह Cd के संभावित जनरेटर की संख्या के समान भी है | विशेष रूप से, यदि Cd = ⟨g⟩ साथ gd = 1, तब gk प्रत्येक k कोप्राइम से d के लिए जनरेटर है | चूंकि Cn का प्रत्येक तत्व चक्रीय उपसमूह उत्पन्न करता है और सभी उपसमूह Cd ⊆ Cn ठीक Cn से φ(d) उत्पन्न होते हैं | सूत्र इस प्रकार है। [18] समतुल्य रूप से, सूत्र एकता के nवें मूल पर प्रयुक्त समान तर्क द्वारा प्राप्त किया जा सकता है |
सूत्र को प्राथमिक अंकगणित से भी प्राप्त किया जा सकता है। [19] उदाहरण के लिए, माना n = 20 और हर 20 के साथ 1 तक के सकारात्मक अंशों पर विचार करें |
उन्हें निम्नतम शब्दों में रखें:
ये बीस अंश सभी धनात्मक k/d ≤ 1 हैं | जिसके प्रत्येक भाजक हैं | d = 1, 2, 4, 5, 10, 20. प्रत्येक के रूप में 20 वाले अंश वे हैं जिनके अंश अपेक्षाकृत 20 तक हैं, अर्थात् 1/20, 3/20, 7/20, 9/20, 11/20, 13/20, 17/20, 19/20; परिभाषा के अनुसार φ(20) भिन्न है। इसी प्रकार,प्रत्येक 10 के साथ φ(10) भाजक अंश है और प्रत्येक भाजक 5 के साथ φ(5) अंश है | आदि इस प्रकार बीस अंशों का समुच्चय d 20 के लिए आकार के सबसमुच्चय में विभाजित होता है |
विभाजक योग सूत्र पर प्रयुक्त मोबियस उलटा देता है
जहाँ μ मोबियस फलन है, जिसके द्वारा परिभाषित गुणक फलन और है | प्रत्येक प्रधान के लिए p और k ≥ 2.के लिए परिभाषित है। यह सूत्र उत्पाद सूत्र से गुणा करके भी प्राप्त किया जा सकता है | उदाहरण:
कुछ मूल्य
पहले 100 मान (sequence A000010 in the OEIS) को नीचे तालिका और ग्राफ़ में दिखाया गया है:
:{| class="wikitable" style="text-align: right"
|+φ(n) for 1 ≤ n ≤ 100 ! + ! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 |- ! 0 | 1 || 1 || 2 || 2 || 4 || 2 || 6 || 4 || 6 || 4 |- ! 10 | 10 || 4 || 12 || 6 || 8 || 8 || 16 || 6 || 18 || 8 |- ! 20 | 12 || 10 || 22 || 8 || 20 || 12 || 18 || 12 || 28 || 8 |- ! 30 | 30 || 16 || 20 || 16 || 24 || 12 || 36 || 18 || 24 || 16 |- ! 40 | 40 || 12 || 42 || 20 || 24 || 22 || 46 || 16 || 42 || 20 |- ! 50 | 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58 || 16 |- ! 60 | 60 || 30 || 36 || 32 || 48 || 20 || 66 || 32 || 44 || 24 |- ! 70 | 70 || 24 || 72 || 36 || 40 || 36 || 60 || 24 || 78 || 32 |- ! 80 | 54 || 40 || 82 || 24 || 64 || 42 || 56 || 40 || 88 || 24 |- ! 90 | 72 || 44 || 60 || 46 || 72 || 32 || 96 || 42 || 60 || 40 |}
शीर्ष रेखा के दाईं ओर ग्राफ़ में y = n − 1 ऊपरी सीमा है जो सभी के लिए मान्य है n के अतिरिक्त, और यदि और केवल यदि प्राप्त किया n अभाज्य संख्या है। साधारण निचली सीमा है , जो ढीला है: वास्तव में, ग्राफ की सीमा श्रेष्ठ और n/log log n सीमा हीन आनुपातिक है |[20]
यूलर प्रमेय
इसमें कहा गया है कि यदि a और n तब अपेक्षाकृत प्रमुख हैं |
विशेष स्थिति जहां n प्राइम है जिसे फर्मेट की छोटी प्रमेय के रूप में जाना जाता है।
यह लैग्रेंज के प्रमेय (समूह सिद्धांत) और φ(n) इस तथ्य से आता है | पूर्णांक मॉड्यूलो के गुणक समूह का क्रम (समूह सिद्धांत) n है |
आरएसए (एल्गोरिदम) इस प्रमेय पर आधारित है: इसका तात्पर्य है कि फलन का उलटा कार्य a ↦ ae mod n, जहाँ e (सार्वजनिक) एन्क्रिप्शन प्रतिपादक है, कार्य है b ↦ bd mod n, जहाँ d, (निजी) डिक्रिप्शन एक्सपोनेंट, का गुणात्मक व्युत्क्रम है | e मापांक φ(n). कंप्यूटिंग की कठिनाई φ(n) के गुणनखंड को जाने बिना n इस प्रकार कंप्यूटिंग की कठिनाई d है | इसे आरएसए समस्या के रूप में जाना जाता है जिसे फैक्टरिंग n द्वारा हल किया जा सकता है | निजी कुंजी का स्वामी गुणनखंडन को जानता है | क्योंकि आरएसए निजी कुंजी को चुनकर बनाया जाता है | n दो (यादृच्छिक रूप से चुने गए) बड़े प्राइम्स के उत्पाद के रूप में p और q. केवल n सार्वजनिक रूप से प्रकट किया गया है, और पूर्णांक गुणनखंडन को देखते हुए हमारे पास गारंटी है कि किसी और को गुणनखंडन के बारे में पता नहीं है।
अन्य सूत्र
विशेष रूप से:
इसकी तुलना सूत्र से करें (लघुतम समापवर्त्य देखें)।
φ(n) के लिए भी है n ≥ 3.
इसके अतिरिक्त, यदि n है r विशिष्ट विषम अभाज्य कारक, {{math|2r | φ(n)}
जहाँ rad(n) पूर्णांक का मूलांक है | n (विभाजन करने वाले सभी विशिष्ट अभाज्य संख्याओं का गुणनफल n).
(जहाँ γ यूलर-माशेरोनी स्थिरांक है)।
जहाँ m > 1 सकारात्मक पूर्णांक है और ω(m) के विशिष्ट प्रमुख कारकों की संख्या m है |[25]
मेनन की पहचान
1965 में पी. केसव मेनन ने सिद्ध किया है |
- : : : : : : : : : : : : : : : : : : : : : : : :
जहाँ d(n) = σ0(n) के विभाजकों की संख्या n है |
कार्य उत्पन्न करना
डिरिचलेट श्रृंखला के लिए φ(n) को रीमैन जीटा फलन के रूप में लिखा जा सकता है |[26]
जहां बाईं ओर के लिए अभिसरण होता है .
लैम्बर्ट श्रृंखला जनरेटिंग फलन है [27]
जो |q| < 1 के लिए अभिसरण करता है .
ये दोनों प्रारंभिक श्रृंखला जोड़तोड़ और φ(n) के लिए सूत्रों द्वारा सिद्ध होते हैं |
विकास दर
हार्डी एंड राइट के शब्दों में,φ(n) का क्रम सदैव 'लगभग' n होता है |[28] पहला [29]
किन्तु जैसे n सभी δ > 0 के लिए अनंत तक जाता है |[30]
इन दोनों सूत्रों को φ(n) और भाजक फलन σ(n). सूत्र से थोड़ा अधिक प्रयोग करके सिद्ध किया जा सकता है |
वास्तव में, दूसरे सूत्र के प्रमाण के समय, असमानता होती है |
सही है n > 1,के लिए सिद्ध होता है।
हमारे पास भी है [20]
यहाँ γ यूलर-मास्चेरोनी स्थिरांक है | यूलर स्थिरांक, γ = 0.577215665..., इसलिए eγ = 1.7810724... और e−γ = 0.56145948....
इसे सिद्ध करने के लिए अभाज्य संख्या प्रमेय की आवश्यकता नहीं है। [31][32] तब से log log n अनंत तक जाता है, यह सूत्र बताता है
वास्तव में, अधिक सत्य है। [33][34][35]
और
दूसरी असमानता जीन लुइस निकोलस द्वारा प्रदर्शित की गई थी। रिबेनबोइम कहते हैं कि प्रमाण की विधि रोचक है, इसमें असमानता को पहले इस धारणा के अनुसार दिखाया गया है कि रीमैन परिकल्पना सत्य है, दूसरी विपरीत धारणा के अनुसार ये भी सही है।[35]: 173
औसत आदेश के लिए, हमारे पास है |[22][36]
अर्नोल्ड वाल्फिज़ के कारण, इसका प्रमाण इवान मटेवेविच विनोग्रादोव के कारण घातीय रकम पर अनुमानों का उपयोग करता है | एम. विनोग्रादोव और एन. एम. कोरोबोव है।
वैन डेर कॉर्पुट और विनोग्रादोव के विधियों के संयोजन से, H.-Q. लियू (ऑन यूलर फलन। प्रोक। रॉय। सोक। एडिनबर्ग सेक्ट। ए 146 (2016), नंबर 4, 769-775) त्रुटि शब्द में सुधार किया है |
(यह वर्तमान में इस प्रकार का सबसे अच्छा ज्ञात अनुमान है)। बिग ओ नोटेशन बड़ा O ऐसी मात्रा के लिए खड़ा है जो निरंतर समय के कार्य n से बंधी है कोष्ठक के अंदर (जो की n2 तुलना में छोटा है).
इस परिणाम का उपयोग सिद्ध करने के लिए किया जा सकता है | [37] यादृच्छिक रूप से चुनी गई दो संख्याओं के अपेक्षाकृत 6/π2 अभाज्य होने की प्रायिकता है |
निरंतर मूल्यों का अनुपात
1950 में सोमयाजुलु सिद्ध हुआ | [38][39]
1954 में एंड्रयू शिंजेल और वाक्लाव सिएरपिन्स्की ने इसे सिद्ध करते हुए इसे शक्तिशाली किया | [38][39]
वह समुच्चय धनात्मक वास्तविक संख्याओं में सघन समुच्चय है। वे सिद्ध भी हुए है |[38]
वह समुच्चय अंतराल (0,1) में सघन है।
कुल संख्या
टोटिएंट नंबर यूलर के टोटिएंट फलन का मान है | अर्थात, a m जिसके लिए कम से कम n है | जिसके लिए φ(n) = m. कुल संख्या की संयोजकता या बहुलता m इस समीकरण के समाधान की संख्या है। [40] नॉनटोटिएंट प्राकृतिक संख्या है जो टोटिएंट संख्या नहीं है। 1 से अधिक प्रत्येक विषम पूर्णांक तुच्छ रूप से गैर-परमाणु है। यहाँ अपरिमित रूप से बहुत से अचिंतक भी हैं |[41] और वास्तव में प्रत्येक धनात्मक पूर्णांक का गुणज होता है जो सम अचिंतक होता है।[42]
दी गई सीमा तक कुल संख्याओं की संख्या x है |
स्थिर के लिए C = 0.8178146....[43] है |
यदि बहुलता के अनुसार गिना जाता है, तो दी गई सीमा तक कुल संख्याओं की संख्या x है
जहां त्रुटि शब्द R अधिक से अधिक क्रम में x/(log x)k है | किसी भी सकारात्मक k के लिए .[44] यह ज्ञात है कि की बहुलता m से अधिक है mδ असीम रूप से अधिकांशतः किसी के लिए δ < 0.55655.[45][46] है |
फोर्ड की प्रमेय
फोर्ड (1999) ने सिद्ध किया कि प्रत्येक पूर्णांक k ≥ 2 के लिए बहुलता k का एक कुल संख्या m है | अर्थात, जिसके लिए समीकरण φ(n) = m का बिल्कुल k समाधान है | यह परिणाम पहले वैक्लाव सिएरपिन्स्की द्वारा अनुमानित किया गया था,|[47] और इसे शिंजेल की परिकल्पना एच के परिणाम के रूप में प्राप्त किया गया था। [43] वास्तव में, प्रत्येक बहुलता जो घटित होती है, अनंत बार होती है। [43][46]
चूँकि, कोई संख्या नहीं m बहुलता से जाना जाता है | k = 1. कारमाइकल का संपूर्ण कार्य अनुमान यह कथन है कि ऐसा कोई m नहीं है |.[48]
पूर्ण सम संख्याएं
पूर्ण कुल संख्या एक पूर्णांक है जो इसके पुनरावृत्त कुलों के योग के समान है। अर्थात्, हम टोटिएंट फलन को संख्या n पर प्रयुक्त करते हैं, इसे परिणामी टोटिएंट पर फिर से प्रयुक्त करते हैं, और इसी तरह, जब तक कि संख्या 1 तक नहीं पहुंच जाती है, और संख्याओं के परिणामी क्रम को साथ जोड़ देते हैं; यदि योग n के समान है, तो n पूर्ण पूर्ण संख्या है।
अनुप्रयोग
साइक्लोटॉमी
डिसक्विजिशन अरिथमेटिका के अंतिम खंड में [49][50] गॉस सिद्ध करता है | [51] कि नियमित n-गॉन का निर्माण स्ट्रेटेज और कंपास से किया जा सकता है | यदि φ(n) 2 की शक्ति है। यदि n विषम अभाज्य संख्या की शक्ति है,| टोटिएंट के लिए सूत्र कहता है कि इसका टोटिएंट केवल दो की शक्ति हो सकता है | n पहली शक्ति है और n − 1 2 की शक्ति है। वे अभाज्य संख्याएँ जो 2 की शक्ति से अधिक होती हैं,| फर्मेट प्राइम कहलाती हैं, और केवल पाँच ज्ञात हैं: 3, 5, 17, 257, और 65537 है। फर्मेट और गॉस इनके बारे में जानते थे। कोई भी यह सिद्ध करने में सक्षम नहीं है कि क्या और भी हैं।
इस प्रकार, नियमित n-गॉन का स्ट्रेटएज-एंड-कम्पास निर्माण होता है | यदि n विशिष्ट फर्मेट प्राइम्स और 2 की किसी भी शक्ति का उत्पाद है। पहले कुछ ऐसे n हैं |[52]
अंकगणितीय प्रगति के लिए अभाज्य संख्या प्रमेय
आरएसए क्रिप्टोप्रणाली
आरएसए प्रणाली की स्थापना में बड़ी अभाज्य संख्याओं p और q, को चुनना n = pq और k = φ(n),की गणना करना और दो संख्याएँ e और d सम्मिलित है | कि ed ≡ 1 (mod k). संख्या n और e (एन्क्रिप्शन कुंजी ) जनता के लिए जारी की जाती हैं, और d (डिक्रिप्शन कुंजी ) को निजी रखा जाता है।
संदेश, पूर्णांक द्वारा दर्शाया गया m, जहाँ 0 < m < n, कंप्यूटिंग S = me (mod n) द्वारा एन्क्रिप्ट किया गया है |
इसे कंप्यूटिंग t = Sd (mod n) द्वारा डिक्रिप्ट किया जाता है | यूलर के प्रमेय का उपयोग यह दिखाने के लिए किया जा सकता है कि यदि 0 < t < n, तब t = m.
संख्या होने पर आरएसए प्रणाली की सुरक्षा से समझौता किया जाएगा n को कुशलता से फैक्टर किया जा सकता है या यदि φ(n) बिना फैक्टरिंग के कुशलता से n गणना की जा सकती है |
अनसुलझी समस्याएं
लेहमर का अनुमान
यदि p प्रधान है, तो φ(p) = p − 1. 1932 में डी. एच. लेहमर ने पूछा कि क्या कोई मिश्रित संख्याएँ n हैं | ऐसा है कि φ(n) विभाजित करता है n − 1. कोई नहीं जानता है।[53]
1933 में उन्होंने सिद्ध कर दिया कि यदि कोई ऐसा n उपस्थित है, यह विषम, वर्ग रहित और कम से कम सात अभाज्य संख्याओं से विभाज्य होना चाहिए (अर्थात ω(n) ≥ 7). 1980 में कोहेन और हागिस ने यह सिद्ध कर दिया n > 1020 ओर वो ω(n) ≥ 14.[54] आगे, हैगिस ने दिखाया कि यदि 3 विभाजित होता है | n तब n > 101937042 और ω(n) ≥ 298848.[55][56] |
कारमाइकल का अनुमान
यह बताता है कि कोई संख्या नहीं है n गुण के साथ कि अन्य सभी नंबरों के लिए m, m ≠ n, φ(m) ≠ φ(n). ऊपर फोर्ड की प्रमेय देखें।
जैसा कि मुख्य लेख में कहा गया है, यदि इस अनुमान के लिए एकल प्रति उदाहरण है, तो असीम रूप से कई प्रति उदाहरण होने चाहिए, और सबसे छोटे वाले के पास आधार 10 में कम से कम दस अरब अंक हैं।[40]
रीमैन परिकल्पना
रीमैन परिकल्पना सही है यदि और केवल यदि असमानता है |
सभी n ≥ p120569# के लिए सत्य है | जहाँ γ यूलर स्थिरांक है और p120569# प्राथमिक 120569 अभाज्य संख्याओं का गुणनफल है।[57]
यह भी देखें
- कारमाइकल फलन
- डफिन-शेफ़र अनुमान
- फर्मेट की छोटी प्रमेय सामान्यीकरण फर्मेट की छोटी प्रमेय का सामान्यीकरण
- अत्यधिक समग्र संख्या
- पूर्णांक मॉड्यूलो का गुणक समूह n|पूर्णांक मॉड्यूलो का गुणक समूह n
- रामनुजन शूम
- संपूर्ण सारांश फलन
- डेडेकाइंड का साई फलन
टिप्पणियाँ
- ↑ "Euler's totient function". Khan Academy. Retrieved 2016-02-26.
- ↑ Long (1972, p. 85)
- ↑ Pettofrezzo & Byrkit (1970, p. 72)
- ↑ Long (1972, p. 162)
- ↑ Pettofrezzo & Byrkit (1970, p. 80)
- ↑ See Euler's theorem.
- ↑ L. Euler "Theoremata arithmetica nova methodo demonstrata" (An arithmetic theorem proved by a new method), Novi commentarii academiae scientiarum imperialis Petropolitanae (New Memoirs of the Saint-Petersburg Imperial Academy of Sciences), 8 (1763), 74–104. (The work was presented at the Saint-Petersburg Academy on October 15, 1759. A work with the same title was presented at the Berlin Academy on June 8, 1758). Available on-line in: Ferdinand Rudio, ed., Leonhardi Euleri Commentationes Arithmeticae, volume 1, in: Leonhardi Euleri Opera Omnia, series 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915), pages 531–555. On page 531, Euler defines n as the number of integers that are smaller than N and relatively prime to N (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), which is the phi function, φ(N).
- ↑ 8.0 8.1 Sandifer, p. 203
- ↑ Graham et al. p. 133 note 111
- ↑ L. Euler, Speculationes circa quasdam insignes proprietates numerorum, Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18–30, or Opera Omnia, Series 1, volume 4, pp. 105–115. (The work was presented at the Saint-Petersburg Academy on October 9, 1775).
- ↑ Both φ(n) and ϕ(n) are seen in the literature. These are two forms of the lower-case Greek letter phi.
- ↑ Gauss, Disquisitiones Arithmeticae article 38
- ↑ Cajori, Florian (1929). ए हिस्ट्री ऑफ़ मैथेमेटिकल नोटेशन वॉल्यूम II. Open Court Publishing Company. §409.
- ↑ J. J. Sylvester (1879) "On certain ternary cubic-form equations", American Journal of Mathematics, 2 : 357-393; Sylvester coins the term "totient" on page 361.
- ↑ "totient". Oxford English Dictionary (2nd ed.). Oxford University Press. 1989.
- ↑ Schramm (2008)
- ↑ Gauss, DA, art 39
- ↑ Gauss, DA art. 39, arts. 52-54
- ↑ Graham et al. pp. 134-135
- ↑ 20.0 20.1 Hardy & Wright 1979, thm. 328
- ↑ Dineva (in external refs), prop. 1
- ↑ 22.0 22.1 22.2 Walfisz, Arnold (1963). आधुनिक संख्या सिद्धांत में वेइल का घातीय योग. Mathematische Forschungsberichte (in Deutsch). Vol. 16. Berlin: VEB Deutscher Verlag der Wissenschaften. Zbl 0146.06003.
- ↑ Lomadse, G. (1964), "The scientific work of Arnold Walfisz" (PDF), Acta Arithmetica, 10 (3): 227–237, doi:10.4064/aa-10-3-227-237
- ↑ 24.0 24.1 Sitaramachandrarao, R. (1985). "लैंडौ II की त्रुटि अवधि पर". Rocky Mountain J. Math. 15 (2): 579–588. doi:10.1216/RMJ-1985-15-2-579.
- ↑ Bordellès in the external links
- ↑ Hardy & Wright 1979, thm. 288
- ↑ Hardy & Wright 1979, thm. 309
- ↑ Hardy & Wright 1979, intro to § 18.4
- ↑ Hardy & Wright 1979, thm. 326
- ↑ Hardy & Wright 1979, thm. 327
- ↑ In fact Chebyshev's theorem (Hardy & Wright 1979, thm.7) and Mertens' third theorem is all that is needed.
- ↑ Hardy & Wright 1979, thm. 436
- ↑ Theorem 15 of Rosser, J. Barkley; Schoenfeld, Lowell (1962). "Approximate formulas for some functions of prime numbers". Illinois J. Math. 6 (1): 64–94. doi:10.1215/ijm/1255631807.
- ↑ Bach & Shallit, thm. 8.8.7
- ↑ 35.0 35.1 Ribenboim (1989). "How are the Prime Numbers Distributed? §I.C The Distribution of Values of Euler's Function". द बुक ऑफ प्राइम नंबर रिकॉर्ड्स (2nd ed.). New York: Springer-Verlag. pp. 172–175. doi:10.1007/978-1-4684-0507-1_5. ISBN 978-1-4684-0509-5.
- ↑ Sándor, Mitrinović & Crstici (2006) pp.24–25
- ↑ Hardy & Wright 1979, thm. 332
- ↑ 38.0 38.1 38.2 Ribenboim, p.38
- ↑ 39.0 39.1 Sándor, Mitrinović & Crstici (2006) p.16
- ↑ 40.0 40.1 Guy (2004) p.144
- ↑ Sándor & Crstici (2004) p.230
- ↑ Zhang, Mingzhi (1993). "नास्तिकों पर". Journal of Number Theory. 43 (2): 168–172. doi:10.1006/jnth.1993.1014. ISSN 0022-314X. Zbl 0772.11001.
- ↑ 43.0 43.1 43.2 Ford, Kevin (1998). "टोटियों का वितरण". Ramanujan J. Developments in Mathematics. 2 (1–2): 67–151. arXiv:1104.3264. doi:10.1007/978-1-4757-4507-8_8. ISBN 978-1-4419-5058-1. ISSN 1382-4090. Zbl 0914.11053.
- ↑ Sándor et al (2006) p.22
- ↑ Sándor et al (2006) p.21
- ↑ 46.0 46.1 Guy (2004) p.145
- ↑ Sándor & Crstici (2004) p.229
- ↑ Sándor & Crstici (2004) p.228
- ↑ Gauss, DA. The 7th § is arts. 336–366
- ↑ Gauss proved if n satisfies certain conditions then the n-gon can be constructed. In 1837 Pierre Wantzel proved the converse, if the n-gon is constructible, then n must satisfy Gauss's conditions
- ↑ Gauss, DA, art 366
- ↑ Gauss, DA, art. 366. This list is the last sentence in the Disquisitiones
- ↑ Ribenboim, pp. 36–37.
- ↑ Cohen, Graeme L.; Hagis, Peter Jr. (1980). "On the number of prime factors of n if φ(n) divides n − 1". Nieuw Arch. Wiskd. III Series. 28: 177–185. ISSN 0028-9825. Zbl 0436.10002.
- ↑ Hagis, Peter Jr. (1988). "On the equation M·φ(n) = n − 1". Nieuw Arch. Wiskd. IV Series. 6 (3): 255–261. ISSN 0028-9825. Zbl 0668.10006.
- ↑ Guy (2004) p.142
- ↑ Broughan, Kevin (2017). Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents (First ed.). Cambridge University Press. ISBN 978-1-107-19704-6. Corollary 5.35
संदर्भ
The Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of Gauss' papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.
संदर्भ to the Disquisitiones are of the form Gauss, DA, art. nnn.
- Abramowitz, M.; Stegun, I. A. (1964), Handbook of Mathematical Functions, New York: Dover Publications, ISBN 0-486-61272-4. See paragraph 24.3.2.
- Bach, Eric; Shallit, Jeffrey (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), MIT Press Series in the Foundations of Computing, Cambridge, MA: The MIT Press, ISBN 0-262-02405-5, Zbl 0873.11070
- Dickson, Leonard Eugene, "History Of The Theory Of Numbers", vol 1, chapter 5 "Euler's Function, Generalizations; Farey Series", Chelsea Publishing 1952
- Ford, Kevin (1999), "The number of solutions of φ(x) = m", Annals of Mathematics, 150 (1): 283–311, doi:10.2307/121103, ISSN 0003-486X, JSTOR 121103, MR 1715326, Zbl 0978.11053.
- Gauss, Carl Friedrich (1986), Disquisitiones Arithmeticae (Second, corrected edition), translated by Clarke, Arthur A., New York: Springer, ISBN 0-387-96254-9
- Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition), translated by Maser, H., New York: Chelsea, ISBN 0-8284-0191-8
- Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994), Concrete Mathematics: a foundation for computer science (2nd ed.), Reading, MA: Addison-Wesley, ISBN 0-201-55802-5, Zbl 0836.00001
- Guy, Richard K. (2004), Unsolved Problems in Number Theory, Problem Books in Mathematics (3rd ed.), New York, NY: Springer-Verlag, ISBN 0-387-20860-7, Zbl 1058.11001
- Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (Fifth ed.), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
- Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950
- Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766
- Ribenboim, Paulo (1996), The New Book of Prime Number Records (3rd ed.), New York: Springer, ISBN 0-387-94457-5, Zbl 0856.11001
- Sandifer, Charles (2007), The early mathematics of Leonhard Euler, MAA, ISBN 978-0-88385-559-1
- Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006), Handbook of number theory I, Dordrecht: Springer-Verlag, pp. 9–36, ISBN 1-4020-4215-9, Zbl 1151.11300
- Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 179–327. ISBN 1-4020-2546-7. Zbl 1079.11001.
- Schramm, Wolfgang (2008), "The Fourier transform of functions of the greatest common divisor", Electronic Journal of Combinatorial Number Theory, A50 (8(1)).
बाहरी संबंध
- "Totient function", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- Euler's φ Function and the Chinese Remainder Theorem — proof that φ(n) is multiplicative
- Euler's टोटिएंट function calculator in JavaScript — up to 20 digits
- Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions
- Plytage, Loomis, Polhill Summing Up The Euler φ Function