सहअभाज्य पूर्णांक: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 21: Line 21:
*ऐसे पूर्णांक {{mvar|x, y}} स्थित हैं कि {{math|1=''ax'' + ''by'' = 1}} (बेज़आउट की पहचान देखें)।
*ऐसे पूर्णांक {{mvar|x, y}} स्थित हैं कि {{math|1=''ax'' + ''by'' = 1}} (बेज़आउट की पहचान देखें)।
*पूर्णांक {{mvar|b}} में [[मॉड्यूलर गुणक व्युत्क्रम]] मॉड्यूल {{mvar|a}} है, जिसका अर्थ है कि पूर्णांक {{mvar|y}} स्थित है जैसे कि {{math|''by'' ≡ 1 (mod ''a'')}} द्वारा। वलय-सैद्धांतिक भाषा में, {{mvar|b}} पूर्णांक [[मॉड्यूलर अंकगणित]] {{mvar|a}} के वलय (गणित) {{tmath|\Z/a\Z}} में एक [[इकाई (रिंग सिद्धांत)|इकाई (वलय सिद्धांत)]] है।
*पूर्णांक {{mvar|b}} में [[मॉड्यूलर गुणक व्युत्क्रम]] मॉड्यूल {{mvar|a}} है, जिसका अर्थ है कि पूर्णांक {{mvar|y}} स्थित है जैसे कि {{math|''by'' ≡ 1 (mod ''a'')}} द्वारा। वलय-सैद्धांतिक भाषा में, {{mvar|b}} पूर्णांक [[मॉड्यूलर अंकगणित]] {{mvar|a}} के वलय (गणित) {{tmath|\Z/a\Z}} में एक [[इकाई (रिंग सिद्धांत)|इकाई (वलय सिद्धांत)]] है।
*{{math|''x'' ≡ ''k'' (mod ''a'')}} और {{math|''x'' ≡ ''m'' (mod ''b'')}} के रूप के किसी अज्ञात पूर्णांक {{mvar|x}} के लिए [[सर्वांगसम संबंध|सर्वांगसम संबंधों]] के प्रत्येक युग्म का हल होता है ([[चीनी शेषफल प्रमेय]]); वस्तुतः हलों का वर्णन एकल सर्वांगसम संबंध मॉड्यूलो {{mvar|ab}} द्वारा किया जाता है।
*{{math|''x'' ≡ ''k'' (mod ''a'')}} और {{math|''x'' ≡ ''m'' (mod ''b'')}} के रूप के किसी अज्ञात पूर्णांक {{mvar|x}} के लिए [[सर्वांगसम संबंध|सर्वांगसम संबंधों]] के प्रत्येक युग्म का हल होता है ([[चीनी शेषफल प्रमेय]]); वस्तुतः हलों का वर्णन एकल सर्वांगसम संबंध मॉड्यूल {{mvar|ab}} द्वारा किया जाता है।
*{{mvar|a}} और {{mvar|b}} का लघुत्तम समापवर्त्य उनके गुणनफल {{mvar|ab}} के बराबर है, अर्थात {{math|1=lcm(''a'', ''b'') = ''ab''}}।<ref>{{harvnb|Ore|1988|loc=p. 47}}</ref>
*{{mvar|a}} और {{mvar|b}} का लघुत्तम समापवर्त्य उनके गुणनफल {{mvar|ab}} के बराबर है, अर्थात {{math|1=lcm(''a'', ''b'') = ''ab''}}।<ref>{{harvnb|Ore|1988|loc=p. 47}}</ref>
तीसरे बिंदु के परिणामस्वरूप, यदि {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं और {{math|''br'' &equiv; ''bs'' (mod ''a'')}}, तब {{math|''r'' &equiv; ''s'' (mod ''a'')}}.<ref>{{harvnb|Niven|Zuckerman|1966|loc=p. 22, Theorem 2.3(b)}}</ref> अर्थात्, हम विभाजित कर सकते हैं {{mvar|b}} मॉड्यूलो काम करते समय {{mvar|a}}. इसके अलावा, यदि {{math|''b''<sub>1</sub>, ''b''<sub>2</sub>}} दोनों सहअभाज्य हैं {{mvar|a}}, तो उनका गुणनफल भी वैसा ही है {{math|''b''<sub>1</sub>''b''<sub>2</sub>}} (अर्थात्, प्रपत्र {{mvar|a}} यह व्युत्क्रमणीय अवयवों का गुणनफल है, और इसलिए व्युत्क्रमणीय है);<ref>{{harvnb|Niven|Zuckerman|1966|loc=p. 6, Theorem 1.8}}</ref> यह यूक्लिड के लेम्मा के पहले बिंदु से भी अनुसरण करता है, जो बताता है कि यदि अभाज्य संख्या है {{mvar|p}} किसी गुणनफल को विभाजित करता है {{mvar|bc}}, तब {{mvar|p}} कम से कम कारक को विभाजित करता है {{mvar|b, c}}.
तीसरे बिंदु के परिणामस्वरूप, यदि {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं और {{math|''br'' &equiv; ''bs'' (mod ''a'')}}, तो {{math|''r'' &equiv; ''s'' (mod ''a'')}}<ref>{{harvnb|Niven|Zuckerman|1966|loc=p. 22, Theorem 2.3(b)}}</ref> अर्थात्, मॉड्यूल {{mvar|a}} काम करते समय हम "{{mvar|b}} से विभाजित" हो सकते हैं। इसके अतिरिक्त, यदि {{math|''b''<sub>1</sub>, ''b''<sub>2</sub>}} दोनों {{mvar|a}} के साथ सहअभाज्य हैं , तो उनका गुणनफल {{math|''b''<sub>1</sub>''b''<sub>2</sub>}} भी ऐसा ही है (अर्थात्, मॉड्यूल {{mvar|a}} यह व्युत्क्रमणीय अवयवों का गुणनफल है, और इसलिए व्युत्क्रमणीय है);<ref>{{harvnb|Niven|Zuckerman|1966|loc=p. 6, Theorem 1.8}}</ref> यह यूक्लिड के लेम्मा के पूर्व बिंदु से भी अनुसरण करता है, जो बताता है कि यदि एक अभाज्य संख्या {{mvar|p}} किसी गुणनफल {{mvar|bc}} को विभाजित करती है, तो {{mvar|p}} कम से कम एक कारक {{mvar|b, c}} को विभाजित करता है।।


पहले बिंदु के परिणामस्वरूप, यदि {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं, तो कोई भी शक्तियाँ भी हैं {{mvar|a<sup>k</sup>}} और {{mvar|b<sup>m</sup>}}.
पूर्व बिंदु के परिणामस्वरूप, यदि {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं, तो कोई भी घात {{mvar|a<sup>k</sup>}} और {{mvar|b<sup>m</sup>}} भी सहअभाज्य हैं।


अगर {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं और {{mvar|a}} गुणनफल को विभाजित करता है {{mvar|bc}}, तब {{mvar|a}} बांटता है {{mvar|c}}.<ref>{{harvnb|Niven|Zuckerman|1966|loc=p.7, Theorem 1.10}}</ref> इसे यूक्लिड की प्रमेयिका के सामान्यीकरण के रूप में देखा जा सकता है।
यदि {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं और {{mvar|a}} गुणनफल {{mvar|bc}} को विभाजित करता है , तो {{mvar|a}} , {{mvar|c}} को विभाजित करता है।<ref>{{harvnb|Niven|Zuckerman|1966|loc=p.7, Theorem 1.10}}</ref> इसे यूक्लिड की प्रमेयिका के सामान्यीकरण के रूप में देखा जा सकता है।


[[Image:coprime-lattice.svg|thumb|right|300px|चित्र 1. संख्याएँ 4 और 9 सहअभाज्य हैं। इसलिए, 4 × 9 जाली का विकर्ण किसी अन्य वर्गाकार जाली को नहीं काटता है]]दो पूर्णांक {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं यदि और केवल यदि निर्देशांक वाला बिंदु {{math|(''a'', ''b'')}} कार्टेशियन समन्वय प्रणाली में मूल से दृष्टि की अबाधित रेखा के माध्यम से दिखाई देगा {{math|(0, 0)}}, इस अर्थ में कि मूल और के बीच के रेखा खंड पर कहीं भी पूर्णांक निर्देशांक वाला कोई बिंदु नहीं है {{math|(''a'', ''b'')}}. (चित्र 1 देखें)
[[Image:coprime-lattice.svg|thumb|right|300px|चित्र 1। संख्याएँ 4 और 9 सहअभाज्य हैं। इसलिए, 4 × 9 जाली का विकर्ण किसी अन्य वर्गाकार जाली को नहीं काटता है]]दो पूर्णांक {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं यदि और मात्र यदि कार्तीय समन्वय प्रणाली में निर्देशांक {{math|(''a'', ''b'')}} वाला बिंदु मूल बिंदु  {{math|(0, 0)}} से दृष्टि की एक अबाधित रेखा के माध्यम से "दृश्यमान" होगा, इस अर्थ में कि मूल बिंदु और {{math|(''a'', ''b'')}} के बीच रेखा खंड पर कहीं भी पूर्णांक निर्देशांक वाला कोई बिंदु नहीं है। (चित्र 1 देखें)


एक अर्थ में जिसे सटीक बनाया जा सकता है, [[संभावना]] है कि दो यादृच्छिक रूप से चुने गए पूर्णांक सहअभाज्य हैं {{math|6/''π''<sup>2</sup>}}, जो लगभग 61% है (देखें {{slink||Probability of coprimality}}, नीचे)।
एक अर्थ में जिसे यथार्थ बनाया जा सकता है, यादृच्छिक रूप से चुने गए दो पूर्णांकों के सहअभाज्य होने की [[संभावना|प्रायिकता]] {{math|6/''π''<sup>2</sup>}} है, जो लगभग 61% है (देखें {{slink||सहप्रारंभिकता की प्रायिकता}}, निम्न)।


दो [[प्राकृतिक संख्या]]एँ {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं यदि और केवल यदि संख्याएँ {{math|2<sup>''a''</sup> – 1}} और {{math|2<sup>''b''</sup> – 1}} सहअभाज्य हैं।<ref>{{harvnb|Rosen|1992|loc=p. 140}}</ref> इसके सामान्यीकरण के रूप में, [[ सूत्र |सूत्र]] में यूक्लिडियन एल्गोरिथम का आसानी से अनुसरण किया जा सकता है {{math|''n'' > 1}}:
दो [[प्राकृतिक संख्या]]एँ {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं यदि और मात्र यदि संख्याएँ {{math|2<sup>''a''</sup> – 1}} और {{math|2<sup>''b''</sup> – 1}} सहअभाज्य हैं।<ref>{{harvnb|Rosen|1992|loc=p. 140}}</ref> इसके सामान्यीकरण के रूप में, [[ सूत्र |सूत्र]] {{math|''n'' > 1}}:


: <math>\gcd\left(n^a - 1, n^b - 1\right) = n^{\gcd(a, b)} - 1.</math>
: <math>\gcd\left(n^a - 1, n^b - 1\right) = n^{\gcd(a, b)} - 1</math> में यूक्लिडियन एल्गोरिदम से सरलता से अनुसरण किया जा सकता है।
== समुच्चयों में सहप्रधानता ==
== समुच्चयों में सहप्रधानता ==
पूर्णांकों का समुच्चय (गणित)। <math>S=\{a_1,a_2, \dots a_n\}</math> इसे सहअभाज्य या समुच्चयवार सहअभाज्य भी कहा जा सकता है यदि समुच्चय के सभी अवयवों का सबसे बड़ा सामान्य भाजक 1 है। उदाहरण के लिए, पूर्णांक 6, 10, 15 सहअभाज्य हैं क्योंकि 1 एकमात्र धनात्मक पूर्णांक है जो उन सभी को विभाजित करता है।
पूर्णांकों का समुच्चय (गणित)। <math>S=\{a_1,a_2, \dots a_n\}</math> इसे सहअभाज्य या समुच्चयवार सहअभाज्य भी कहा जा सकता है यदि समुच्चय के सभी अवयवों का सबसे बड़ा सामान्य भाजक 1 है। उदाहरण के लिए, पूर्णांक 6, 10, 15 सहअभाज्य हैं क्योंकि 1 एकमात्र धनात्मक पूर्णांक है जो उन सभी को विभाजित करता है।


यदि पूर्णांकों के समुच्चय में प्रत्येक युग्म सहअभाज्य है, तो समुच्चय को युग्‍मानूसार सहअभाज्य (या युग्‍मानूसार अपेक्षाकृत अभाज्य, परस्पर सहअभाज्य या परस्पर अपेक्षाकृत अभाज्य) कहा जाता है। युग्‍मानूसार सह-प्रधानता, समुच्चयवार सह-प्रधानता की तुलना में अधिक दृढ स्थिति है; प्रत्येक युग्‍मानूसार सहअभाज्य परिमित समुच्चय भी समुच्चयवार सहअभाज्य है, परन्तु इसका विपरीत सत्य नहीं है। उदाहरण के लिए, पूर्णांक 4, 5, 6 (समुच्चयवार) सहअभाज्य हैं (क्योंकि उन सभी को विभाजित करने वाला एकमात्र धनात्मक पूर्णांक 1 है), परन्तु वे युग्‍मानूसार सहअभाज्य नहीं हैं (क्योंकि {{math|1=gcd(4, 6) = 2}}).
यदि पूर्णांकों के समुच्चय में प्रत्येक युग्म सहअभाज्य है, तो समुच्चय को युग्‍मानूसार सहअभाज्य (या युग्‍मानूसार अपेक्षाकृत अभाज्य, परस्पर सहअभाज्य या परस्पर अपेक्षाकृत अभाज्य) कहा जाता है। युग्‍मानूसार सह-प्रधानता, समुच्चयवार सह-प्रधानता की तुलना में अधिक दृढ स्थिति है; प्रत्येक युग्‍मानूसार सहअभाज्य परिमित समुच्चय भी समुच्चयवार सहअभाज्य है, परन्तु इसका विपरीत सत्य नहीं है। उदाहरण के लिए, पूर्णांक 4, 5, 6 (समुच्चयवार) सहअभाज्य हैं (क्योंकि उन सभी को विभाजित करने वाला एकमात्र धनात्मक पूर्णांक 1 है), परन्तु वे युग्‍मानूसार सहअभाज्य नहीं हैं (क्योंकि {{math|1=gcd(4, 6) = 2}})


चीनी शेषफल प्रमेय जैसे संख्या सिद्धांत में कई परिणामों में जोड़ीदार सह-प्राथमिकता की अवधारणा परिकल्पना के रूप में महत्वपूर्ण है।
चीनी शेषफल प्रमेय जैसे संख्या सिद्धांत में कई परिणामों में जोड़ीदार सह-प्राथमिकता की अवधारणा परिकल्पना के रूप में महत्वपूर्ण है।
Line 47: Line 47:
== वलय आदर्शों में सहप्रधानता ==
== वलय आदर्शों में सहप्रधानता ==


दो [[अंगूठी आदर्श]] {{mvar|A}} और {{mvar|B}} [[क्रमविनिमेय वलय]] में {{mvar|R}} को कोप्राइम (या कोमैक्सिमल) कहा जाता है यदि <math>A+B=R.</math> यह बेज़ाउट की पहचान को सामान्यीकृत करता है: इस परिभाषा के साथ, दो [[प्रमुख आदर्श]] ({{mvar|a}}) और ({{mvar|b}}) पूर्णांकों के वलय में {{tmath|\Z}} सहअभाज्य हैं यदि और केवल यदि {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं। यदि आदर्श {{mvar|A}} और {{mvar|B}} का {{mvar|R}} तो सहअभाज्य हैं <math>AB=A\cap B;</math> इसके अलावा, यदि {{mvar|C}} तीसरा आदर्श ऐसा है {{mvar|A}} रोकना {{mvar|BC}}, तब {{mvar|A}} रोकना {{mvar|C}}. चीनी शेषफल प्रमेय को सहअभाज्य आदर्शों का उपयोग करके किसी भी क्रमविनिमेय वलय के लिए सामान्यीकृत किया जा सकता है।
दो [[अंगूठी आदर्श]] {{mvar|A}} और {{mvar|B}} [[क्रमविनिमेय वलय]] में {{mvar|R}} को कोप्राइम (या कोमैक्सिमल) कहा जाता है यदि <math>A+B=R.</math> यह बेज़ाउट की पहचान को सामान्यीकृत करता है: इस परिभाषा के साथ, दो [[प्रमुख आदर्श]] ({{mvar|a}}) और ({{mvar|b}}) पूर्णांकों के वलय में {{tmath|\Z}} सहअभाज्य हैं यदि और मात्र यदि {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं। यदि आदर्श {{mvar|A}} और {{mvar|B}} का {{mvar|R}} तो सहअभाज्य हैं <math>AB=A\cap B;</math> इसके अतिरिक्त, यदि {{mvar|C}} तीसरा आदर्श ऐसा है {{mvar|A}} रोकना {{mvar|BC}}, तब {{mvar|A}} रोकना {{mvar|C}}चीनी शेषफल प्रमेय को सहअभाज्य आदर्शों का उपयोग करके किसी भी क्रमविनिमेय वलय के लिए सामान्यीकृत किया जा सकता है।


== सहप्राथमिकता की संभावना ==
== सहप्राथमिकता की संभावना ==


दो यादृच्छिक रूप से चुने गए पूर्णांक दिए गए हैं {{mvar|a}} और {{mvar|b}}, यह पूछना उचित है कि इसकी कितनी संभावना है {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं। इस निर्धारण में, उस लक्षण वर्णन का उपयोग करना सुविधाजनक है {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं यदि और केवल यदि कोई अभाज्य संख्या उन दोनों को विभाजित नहीं करती है ([[अंकगणित का मौलिक प्रमेय]] देखें)।
दो यादृच्छिक रूप से चुने गए पूर्णांक दिए गए हैं {{mvar|a}} और {{mvar|b}}, यह पूछना उचित है कि इसकी कितनी संभावना है {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं। इस निर्धारण में, उस लक्षण वर्णन का उपयोग करना सुविधाजनक है {{mvar|a}} और {{mvar|b}} सहअभाज्य हैं यदि और मात्र यदि कोई अभाज्य संख्या उन दोनों को विभाजित नहीं करती है ([[अंकगणित का मौलिक प्रमेय]] देखें)।


अनौपचारिक रूप से, संभावना है कि कोई संख्या अभाज्य (या वस्तुतः किसी पूर्णांक) से विभाज्य है {{mvar|p}} है {{tmath|\tfrac{1}{p};}} उदाहरण के लिए, प्रत्येक 7वाँ पूर्णांक 7 से विभाज्य है। इसलिए संभावना है कि दो संख्याएँ दोनों से विभाज्य हैं {{mvar|p}} है {{tmath|\tfrac{1}{p^2},}} और संभावना है कि उनमें से कम से कम नहीं है {{tmath|1-\tfrac{1}{p^2}.}} अलग-अलग अभाज्य संख्याओं से जुड़ी विभाज्यता घटनाओं का कोई भी सीमित संग्रह परस्पर स्वतंत्र है। उदाहरण के लिए, दो घटनाओं के मामले में, संख्या अभाज्य संख्याओं से विभाज्य होती है {{mvar|p}} और {{mvar|q}} यदि और केवल यदि यह विभाज्य है {{mvar|pq}}; बाद वाली घटना की संभावना है {{tmath|\tfrac{1}{pq}.}} यदि कोई अनुमानी धारणा बनाता है कि इस तरह के तर्क को अनंत रूप से कई विभाज्यता घटनाओं तक बढ़ाया जा सकता है, तो उसे अनुमान लगाया जाता है कि दो संख्याओं के सहअभाज्य होने की संभावना सभी अभाज्यों पर गुणनफल द्वारा दी गई है,
अनौपचारिक रूप से, संभावना है कि कोई संख्या अभाज्य (या वस्तुतः किसी पूर्णांक) से विभाज्य है {{mvar|p}} है {{tmath|\tfrac{1}{p};}} उदाहरण के लिए, प्रत्येक 7वाँ पूर्णांक 7 से विभाज्य है। इसलिए संभावना है कि दो संख्याएँ दोनों से विभाज्य हैं {{mvar|p}} है {{tmath|\tfrac{1}{p^2},}} और संभावना है कि उनमें से कम से कम नहीं है {{tmath|1-\tfrac{1}{p^2}.}} अलग-अलग अभाज्य संख्याओं से जुड़ी विभाज्यता घटनाओं का कोई भी सीमित संग्रह परस्पर स्वतंत्र है। उदाहरण के लिए, दो घटनाओं के मामले में, संख्या अभाज्य संख्याओं से विभाज्य होती है {{mvar|p}} और {{mvar|q}} यदि और मात्र यदि यह विभाज्य है {{mvar|pq}}; बाद वाली घटना की संभावना है {{tmath|\tfrac{1}{pq}.}} यदि कोई अनुमानी धारणा बनाता है कि इस तरह के तर्क को अनंत रूप से कई विभाज्यता घटनाओं तक बढ़ाया जा सकता है, तो उसे अनुमान लगाया जाता है कि दो संख्याओं के सहअभाज्य होने की संभावना सभी अभाज्यों पर गुणनफल द्वारा दी गई है,


: <math>\prod_{\text{prime } p} \left(1-\frac{1}{p^2}\right) = \left( \prod_{\text{prime } p} \frac{1}{1-p^{-2}} \right)^{-1} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2} \approx 0.607927102 \approx 61\%.</math>
: <math>\prod_{\text{prime } p} \left(1-\frac{1}{p^2}\right) = \left( \prod_{\text{prime } p} \frac{1}{1-p^{-2}} \right)^{-1} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2} \approx 0.607927102 \approx 61\%.</math>
यहाँ {{mvar|&zeta;}} [[रीमैन ज़ेटा फ़ंक्शन|रीमैन ज़ेटा फलन]] को संदर्भित करता है, अभाज्य से अधिक गुणनफल से संबंधित पहचान {{math|''&zeta;''(2)}} [[यूलर उत्पाद|यूलर गुणनफल]] का उदाहरण है, और इसका मूल्यांकन {{math|''&zeta;''(2)}} जैसा {{math|''π''<sup>2</sup>/6}} [[बेसल समस्या]] है, जिसे 1735 में [[लियोनहार्ड यूलर]] ने हल किया था।
यहाँ {{mvar|&zeta;}} [[रीमैन ज़ेटा फ़ंक्शन|रीमैन ज़ेटा फलन]] को संदर्भित करता है, अभाज्य से अधिक गुणनफल से संबंधित पहचान {{math|''&zeta;''(2)}} [[यूलर उत्पाद|यूलर गुणनफल]] का उदाहरण है, और इसका मूल्यांकन {{math|''&zeta;''(2)}} जैसा {{math|''π''<sup>2</sup>/6}} [[बेसल समस्या]] है, जिसे 1735 में [[लियोनहार्ड यूलर]] ने हल किया था।


यादृच्छिक रूप से धनात्मक पूर्णांक चुनने का कोई तरीका नहीं है ताकि प्रत्येक धनात्मक पूर्णांक समान संभावना के साथ हो, परन्तु ऊपर दिए गए जैसे यादृच्छिक रूप से चुने गए पूर्णांकों के बारे में कथनों को [[प्राकृतिक घनत्व]] की धारणा का उपयोग करके औपचारिक रूप दिया जा सकता है। प्रत्येक धनात्मक पूर्णांक के लिए {{mvar|N}}, होने देना {{mvar|P{{sub|N}}}}दो यादृच्छिक रूप से चुनी गई संख्याओं के होने की प्रायिकता है <math>\{1,2,\ldots,N\}</math> सहअभाज्य हैं. यद्यपि {{mvar|P{{sub|N}}}} कभी बराबर नहीं होगा {{math|6/''π''<sup>2</sup>}} बिल्कुल, काम के साथ<ref>This theorem was proved by [[Ernesto Cesàro]] in 1881. For a proof, see {{harvnb|Hardy|Wright|2008|loc=Theorem 332}}</ref> कोई इसे सीमा के रूप में दिखा सकता है <math>N \to \infty,</math> संभावना {{mvar|P{{sub|N}}}} दृष्टिकोण {{math|6/''π''<sup>2</sup>}}.
यादृच्छिक रूप से धनात्मक पूर्णांक चुनने का कोई तरीका नहीं है ताकि प्रत्येक धनात्मक पूर्णांक समान संभावना के साथ हो, परन्तु ऊपर दिए गए जैसे यादृच्छिक रूप से चुने गए पूर्णांकों के बारे में कथनों को [[प्राकृतिक घनत्व]] की धारणा का उपयोग करके औपचारिक रूप दिया जा सकता है। प्रत्येक धनात्मक पूर्णांक के लिए {{mvar|N}}, होने देना {{mvar|P{{sub|N}}}}दो यादृच्छिक रूप से चुनी गई संख्याओं के होने की प्रायिकता है <math>\{1,2,\ldots,N\}</math> सहअभाज्य हैं। यद्यपि {{mvar|P{{sub|N}}}} कभी बराबर नहीं होगा {{math|6/''π''<sup>2</sup>}} बिल्कुल, काम के साथ<ref>This theorem was proved by [[Ernesto Cesàro]] in 1881. For a proof, see {{harvnb|Hardy|Wright|2008|loc=Theorem 332}}</ref> कोई इसे सीमा के रूप में दिखा सकता है <math>N \to \infty,</math> संभावना {{mvar|P{{sub|N}}}} दृष्टिकोण {{math|6/''π''<sup>2</sup>}}


अधिक सामान्यतः, की संभावना {{mvar|k}} यादृच्छिक रूप से चुने गए पूर्णांक सहअभाज्य हैं {{tmath|\tfrac{1}{\zeta(k)}.}}
अधिक सामान्यतः, की संभावना {{mvar|k}} यादृच्छिक रूप से चुने गए पूर्णांक सहअभाज्य हैं {{tmath|\tfrac{1}{\zeta(k)}.}}
Line 68: Line 68:
*शाखा 3: <math>(m+2n,n)</math>
*शाखा 3: <math>(m+2n,n)</math>
यह योजना संपूर्ण और अनावश्यक है, इसमें कोई अमान्य सदस्य नहीं है। यह टिप्पणी करके सिद्ध किया जा सकता है कि, यदि <math>(a,b)</math> के साथ सहअभाज्य युग्म है <math>a>b,</math> तब
यह योजना संपूर्ण और अनावश्यक है, इसमें कोई अमान्य सदस्य नहीं है। यह टिप्पणी करके सिद्ध किया जा सकता है कि, यदि <math>(a,b)</math> के साथ सहअभाज्य युग्म है <math>a>b,</math> तब
*अगर <math>a>3b,</math> तब <math>(a,b)</math> का बच्चा है <math>(m,n)=(a-2b, b)</math> शाखा 3 के साथ;
*यदि <math>a>3b,</math> तब <math>(a,b)</math> का बच्चा है <math>(m,n)=(a-2b, b)</math> शाखा 3 के साथ;
*अगर <math>2b<a<3b,</math> तब <math>(a,b)</math> का बच्चा है <math>(m,n)=(b, a-2b)</math> शाखा 2 के साथ;
*यदि <math>2b<a<3b,</math> तब <math>(a,b)</math> का बच्चा है <math>(m,n)=(b, a-2b)</math> शाखा 2 के साथ;
*अगर <math>b<a<2b,</math> तब <math>(a,b)</math> का बच्चा है <math>(m,n)=(b, 2b-a)</math> शाखा 1 के साथ.
*यदि <math>b<a<2b,</math> तब <math>(a,b)</math> का बच्चा है <math>(m,n)=(b, 2b-a)</math> शाखा 1 के साथ।
सभी मामलों में <math>(m,n)</math> के साथ छोटा सहअभाज्य युग्म है <math>m>n.</math> पिता की गणना की यह प्रक्रिया तभी रुक सकती है जब दोनों में से कोई हो <math>a=2b</math> या <math>a=3b.</math> इन मामलों में, सहप्रधानता का तात्पर्य यह है कि जोड़ी या तो है <math>(2,1)</math> या <math>(3,1).</math>
सभी मामलों में <math>(m,n)</math> के साथ छोटा सहअभाज्य युग्म है <math>m>n.</math> पिता की गणना की यह प्रक्रिया तभी रुक सकती है जब दोनों में से कोई हो <math>a=2b</math> या <math>a=3b.</math> इन मामलों में, सहप्रधानता का तात्पर्य यह है कि जोड़ी या तो है <math>(2,1)</math> या <math>(3,1).</math>
== अनुप्रयोग ==
== अनुप्रयोग ==
Line 108: Line 108:
* {{citation|first=Kenneth H.|last=Rosen|title=Elementary Number Theory and its Applications|edition=3rd|year=1992|publisher=Addison-Wesley|isbn=978-0-201-57889-8}}
* {{citation|first=Kenneth H.|last=Rosen|title=Elementary Number Theory and its Applications|edition=3rd|year=1992|publisher=Addison-Wesley|isbn=978-0-201-57889-8}}
==अग्रिम पठन==
==अग्रिम पठन==
*{{Citation |last=Lord |first=Nick |title=A uniform construction of some infinite coprime sequences |journal=Mathematical Gazette |volume=92 |date=March 2008 |pages=66–70 }}.
*{{Citation |last=Lord |first=Nick |title=A uniform construction of some infinite coprime sequences |journal=Mathematical Gazette |volume=92 |date=March 2008 |pages=66–70 }}
[[Category: संख्या सिद्धांत]]  
[[Category: संख्या सिद्धांत]]  



Revision as of 10:45, 6 July 2023

संख्या सिद्धांत में, दो पूर्णांक a और b सहअभाज्य, अपेक्षाकृत अभाज्य या परस्पर अभाज्य हैं यदि एकमात्र धनात्मक पूर्णांक जो उन दोनों का विभाजक है, 1 है।[1] परिणामस्वरूप, कोई भी अभाज्य संख्या जो a को विभाजित करती है वह b को विभाजित नहीं करती है, और इसके विपरीत भी। यह उनके सबसे बड़े सामान्य भाजक (जीसीडी) 1 के बराबर है।[2] कोई यह भी कहता है कि a, b से अभाज्य है या a, b से सहअभाज्य है।

संख्या 8 और 9 सहअभाज्य हैं, इस तथ्य के अतिरिक्त कि इनमें से किसी को भी व्यक्तिगत रूप से अभाज्य संख्या नहीं माना जाता है, क्योंकि 1 उनका एकमात्र सामान्य भाजक है। दूसरी ओर, 6 और 9 सहअभाज्य नहीं हैं, क्योंकि वे दोनों 3 से विभाज्य हैं। परिभाषा के अनुसार, घटे हुए भिन्न के अंश और हर सहअभाज्य होते हैं।

संकेतन और परीक्षण

जब पूर्णांक a और b सहअभाज्य होते हैं, तो गणितीय संकेतन में इस तथ्य को व्यक्त करने की मानक विधि सूत्र gcd(a, b) = 1 या (a, b) = 1 द्वारा यह इंगित करना है कि उनका सबसे बड़ा सामान्य भाजक एक है। अपनी 1989 की पाठ्यपुस्तक कंक्रीट गणित में, रोनाल्ड ग्राहम, डोनाल्ड नुथ और ओरेन पाटश्निक ने यह इंगित करने के लिए एक वैकल्पिक संकेतन का प्रस्ताव दिया कि a और b अपेक्षाकृत अभाज्य हैं और सहअभाज्य ( (जैसा कि a, b से अभाज्य है) के अतिरिक्त "अभाज्य" शब्द का उपयोग किया जाना चाहिए।[3]

यह निर्धारित करने की तीव्र विधि है कि क्या दो संख्याएँ सहअभाज्य हैं, यूक्लिडियन एल्गोरिथ्म और इसके तीव्र प्रकार जैसे बाइनरी जीसीडी एल्गोरिदम या लेहमर के जीसीडी एल्गोरिदम द्वारा दिया गया है।

1 और n के बीच, एक धनात्मक पूर्णांक n के साथ सहअभाज्य पूर्णांकों की संख्या, यूलर के टोटिएंट फलन द्वारा दी जाती है, जिसे यूलर के फाई फलन, φ(n) के रूप में भी जाना जाता है।

पूर्णांकों के समुच्चय (गणित) को सहअभाज्य भी कहा जा सकता है यदि इसके अवयवों में 1 को छोड़कर कोई सामान्य धनात्मक कारक नहीं है। पूर्णांकों के समुच्चय पर दृढ स्थिति युग्‍मानूसार सहअभाज्य है, जिसका अर्थ है कि समुच्चय में विभिन्न पूर्णांकों के प्रत्येक युग्म (a, b) के लिए a और b सहअभाज्य हैं। समुच्चय {2, 3, 4} सहअभाज्य है, परन्तु यह युग्‍मानूसार सहअभाज्य नहीं है क्योंकि 2 और 4 अपेक्षाकृत अभाज्य नहीं हैं।

गुण

संख्याएँ 1 और −1 प्रत्येक पूर्णांक के साथ सहअभाज्य एकमात्र पूर्णांक हैं, और वे एकमात्र पूर्णांक हैं जो 0 के साथ सहअभाज्य हैं।

कई स्थितियाँ हैं a और b के सहअभाज्य होने के समतुल्य हैं:

  • कोई भी अभाज्य संख्या a और b दोनों को विभाजित नहीं करती है।
  • ऐसे पूर्णांक x, y स्थित हैं कि ax + by = 1 (बेज़आउट की पहचान देखें)।
  • पूर्णांक b में मॉड्यूलर गुणक व्युत्क्रम मॉड्यूल a है, जिसका अर्थ है कि पूर्णांक y स्थित है जैसे कि by ≡ 1 (mod a) द्वारा। वलय-सैद्धांतिक भाषा में, b पूर्णांक मॉड्यूलर अंकगणित a के वलय (गणित) में एक इकाई (वलय सिद्धांत) है।
  • xk (mod a) और xm (mod b) के रूप के किसी अज्ञात पूर्णांक x के लिए सर्वांगसम संबंधों के प्रत्येक युग्म का हल होता है (चीनी शेषफल प्रमेय); वस्तुतः हलों का वर्णन एकल सर्वांगसम संबंध मॉड्यूल ab द्वारा किया जाता है।
  • a और b का लघुत्तम समापवर्त्य उनके गुणनफल ab के बराबर है, अर्थात lcm(a, b) = ab[4]

तीसरे बिंदु के परिणामस्वरूप, यदि a और b सहअभाज्य हैं और brbs (mod a), तो rs (mod a)[5] अर्थात्, मॉड्यूल a काम करते समय हम "b से विभाजित" हो सकते हैं। इसके अतिरिक्त, यदि b1, b2 दोनों a के साथ सहअभाज्य हैं , तो उनका गुणनफल b1b2 भी ऐसा ही है (अर्थात्, मॉड्यूल a यह व्युत्क्रमणीय अवयवों का गुणनफल है, और इसलिए व्युत्क्रमणीय है);[6] यह यूक्लिड के लेम्मा के पूर्व बिंदु से भी अनुसरण करता है, जो बताता है कि यदि एक अभाज्य संख्या p किसी गुणनफल bc को विभाजित करती है, तो p कम से कम एक कारक b, c को विभाजित करता है।।

पूर्व बिंदु के परिणामस्वरूप, यदि a और b सहअभाज्य हैं, तो कोई भी घात ak और bm भी सहअभाज्य हैं।

यदि a और b सहअभाज्य हैं और a गुणनफल bc को विभाजित करता है , तो a , c को विभाजित करता है।[7] इसे यूक्लिड की प्रमेयिका के सामान्यीकरण के रूप में देखा जा सकता है।

चित्र 1। संख्याएँ 4 और 9 सहअभाज्य हैं। इसलिए, 4 × 9 जाली का विकर्ण किसी अन्य वर्गाकार जाली को नहीं काटता है

दो पूर्णांक a और b सहअभाज्य हैं यदि और मात्र यदि कार्तीय समन्वय प्रणाली में निर्देशांक (a, b) वाला बिंदु मूल बिंदु (0, 0) से दृष्टि की एक अबाधित रेखा के माध्यम से "दृश्यमान" होगा, इस अर्थ में कि मूल बिंदु और (a, b) के बीच रेखा खंड पर कहीं भी पूर्णांक निर्देशांक वाला कोई बिंदु नहीं है। (चित्र 1 देखें)

एक अर्थ में जिसे यथार्थ बनाया जा सकता है, यादृच्छिक रूप से चुने गए दो पूर्णांकों के सहअभाज्य होने की प्रायिकता 6/π2 है, जो लगभग 61% है (देखें § सहप्रारंभिकता की प्रायिकता, निम्न)।

दो प्राकृतिक संख्याएँ a और b सहअभाज्य हैं यदि और मात्र यदि संख्याएँ 2a – 1 और 2b – 1 सहअभाज्य हैं।[8] इसके सामान्यीकरण के रूप में, सूत्र n > 1:

में यूक्लिडियन एल्गोरिदम से सरलता से अनुसरण किया जा सकता है।

समुच्चयों में सहप्रधानता

पूर्णांकों का समुच्चय (गणित)। इसे सहअभाज्य या समुच्चयवार सहअभाज्य भी कहा जा सकता है यदि समुच्चय के सभी अवयवों का सबसे बड़ा सामान्य भाजक 1 है। उदाहरण के लिए, पूर्णांक 6, 10, 15 सहअभाज्य हैं क्योंकि 1 एकमात्र धनात्मक पूर्णांक है जो उन सभी को विभाजित करता है।

यदि पूर्णांकों के समुच्चय में प्रत्येक युग्म सहअभाज्य है, तो समुच्चय को युग्‍मानूसार सहअभाज्य (या युग्‍मानूसार अपेक्षाकृत अभाज्य, परस्पर सहअभाज्य या परस्पर अपेक्षाकृत अभाज्य) कहा जाता है। युग्‍मानूसार सह-प्रधानता, समुच्चयवार सह-प्रधानता की तुलना में अधिक दृढ स्थिति है; प्रत्येक युग्‍मानूसार सहअभाज्य परिमित समुच्चय भी समुच्चयवार सहअभाज्य है, परन्तु इसका विपरीत सत्य नहीं है। उदाहरण के लिए, पूर्णांक 4, 5, 6 (समुच्चयवार) सहअभाज्य हैं (क्योंकि उन सभी को विभाजित करने वाला एकमात्र धनात्मक पूर्णांक 1 है), परन्तु वे युग्‍मानूसार सहअभाज्य नहीं हैं (क्योंकि gcd(4, 6) = 2)।

चीनी शेषफल प्रमेय जैसे संख्या सिद्धांत में कई परिणामों में जोड़ीदार सह-प्राथमिकता की अवधारणा परिकल्पना के रूप में महत्वपूर्ण है।

पूर्णांकों के अनंत समुच्चय का युग्‍मानूसार सहअभाज्य होना संभव है। उल्लेखनीय उदाहरणों में सभी अभाज्य संख्याओं का समुच्चय, सिल्वेस्टर के अनुक्रम में अवयवों का समुच्चय और सभी फ़र्मेट संख्याओं का समुच्चय शामिल हैं।

वलय आदर्शों में सहप्रधानता

दो अंगूठी आदर्श A और B क्रमविनिमेय वलय में R को कोप्राइम (या कोमैक्सिमल) कहा जाता है यदि यह बेज़ाउट की पहचान को सामान्यीकृत करता है: इस परिभाषा के साथ, दो प्रमुख आदर्श (a) और (b) पूर्णांकों के वलय में सहअभाज्य हैं यदि और मात्र यदि a और b सहअभाज्य हैं। यदि आदर्श A और B का R तो सहअभाज्य हैं इसके अतिरिक्त, यदि C तीसरा आदर्श ऐसा है A रोकना BC, तब A रोकना C। चीनी शेषफल प्रमेय को सहअभाज्य आदर्शों का उपयोग करके किसी भी क्रमविनिमेय वलय के लिए सामान्यीकृत किया जा सकता है।

सहप्राथमिकता की संभावना

दो यादृच्छिक रूप से चुने गए पूर्णांक दिए गए हैं a और b, यह पूछना उचित है कि इसकी कितनी संभावना है a और b सहअभाज्य हैं। इस निर्धारण में, उस लक्षण वर्णन का उपयोग करना सुविधाजनक है a और b सहअभाज्य हैं यदि और मात्र यदि कोई अभाज्य संख्या उन दोनों को विभाजित नहीं करती है (अंकगणित का मौलिक प्रमेय देखें)।

अनौपचारिक रूप से, संभावना है कि कोई संख्या अभाज्य (या वस्तुतः किसी पूर्णांक) से विभाज्य है p है उदाहरण के लिए, प्रत्येक 7वाँ पूर्णांक 7 से विभाज्य है। इसलिए संभावना है कि दो संख्याएँ दोनों से विभाज्य हैं p है और संभावना है कि उनमें से कम से कम नहीं है अलग-अलग अभाज्य संख्याओं से जुड़ी विभाज्यता घटनाओं का कोई भी सीमित संग्रह परस्पर स्वतंत्र है। उदाहरण के लिए, दो घटनाओं के मामले में, संख्या अभाज्य संख्याओं से विभाज्य होती है p और q यदि और मात्र यदि यह विभाज्य है pq; बाद वाली घटना की संभावना है यदि कोई अनुमानी धारणा बनाता है कि इस तरह के तर्क को अनंत रूप से कई विभाज्यता घटनाओं तक बढ़ाया जा सकता है, तो उसे अनुमान लगाया जाता है कि दो संख्याओं के सहअभाज्य होने की संभावना सभी अभाज्यों पर गुणनफल द्वारा दी गई है,

यहाँ ζ रीमैन ज़ेटा फलन को संदर्भित करता है, अभाज्य से अधिक गुणनफल से संबंधित पहचान ζ(2) यूलर गुणनफल का उदाहरण है, और इसका मूल्यांकन ζ(2) जैसा π2/6 बेसल समस्या है, जिसे 1735 में लियोनहार्ड यूलर ने हल किया था।

यादृच्छिक रूप से धनात्मक पूर्णांक चुनने का कोई तरीका नहीं है ताकि प्रत्येक धनात्मक पूर्णांक समान संभावना के साथ हो, परन्तु ऊपर दिए गए जैसे यादृच्छिक रूप से चुने गए पूर्णांकों के बारे में कथनों को प्राकृतिक घनत्व की धारणा का उपयोग करके औपचारिक रूप दिया जा सकता है। प्रत्येक धनात्मक पूर्णांक के लिए N, होने देना PNदो यादृच्छिक रूप से चुनी गई संख्याओं के होने की प्रायिकता है सहअभाज्य हैं। यद्यपि PN कभी बराबर नहीं होगा 6/π2 बिल्कुल, काम के साथ[9] कोई इसे सीमा के रूप में दिखा सकता है संभावना PN दृष्टिकोण 6/π2

अधिक सामान्यतः, की संभावना k यादृच्छिक रूप से चुने गए पूर्णांक सहअभाज्य हैं

सभी सहअभाज्य जोड़े उत्पन्न करना

(2,1) पर जड़ित वृक्ष। जड़ (2,1) को लाल रंग में दर्शाया गया है, इसके तीन बच्चों को नारंगी रंग में दिखाया गया है, तीसरी पीढ़ी को पीले रंग में दिखाया गया है, और इसी तरह इंद्रधनुष क्रम में। एक्स-अक्ष के निकट और अन्य अंतरालों में सहअभाज्य जोड़े हैं जो नहीं दिखाए गए हैं क्योंकि बिंदु देखने में बहुत छोटे हैं।

धनात्मक सहअभाज्य संख्याओं के सभी जोड़े (m, n) (साथ m > n) को दो असंयुक्त पूर्ण टर्नरी वृक्षों में व्यवस्थित किया जा सकता है, वृक्ष से प्रारंभ करके (2, 1) (सम-विषम और विषम-सम जोड़ियों के लिए),[10] और दूसरा पेड़ से शुरू होता है (3, 1) (विषम-विषम जोड़ियों के लिए)।[11] प्रत्येक शिखर के बच्चे (m, n) इस प्रकार उत्पन्न होते हैं:

  • शाखा 1:
  • शाखा 2:
  • शाखा 3:

यह योजना संपूर्ण और अनावश्यक है, इसमें कोई अमान्य सदस्य नहीं है। यह टिप्पणी करके सिद्ध किया जा सकता है कि, यदि के साथ सहअभाज्य युग्म है तब

  • यदि तब का बच्चा है शाखा 3 के साथ;
  • यदि तब का बच्चा है शाखा 2 के साथ;
  • यदि तब का बच्चा है शाखा 1 के साथ।

सभी मामलों में के साथ छोटा सहअभाज्य युग्म है पिता की गणना की यह प्रक्रिया तभी रुक सकती है जब दोनों में से कोई हो या इन मामलों में, सहप्रधानता का तात्पर्य यह है कि जोड़ी या तो है या

अनुप्रयोग

मशीन डिज़ाइन में, समान, समान गियर घिसाव को अपेक्षाकृत प्रमुख होने के लिए साथ जुड़ने वाले दो गियर के दांतों की संख्या का चयन करके प्राप्त किया जाता है। जब 1:1 गियर ट्रेन की आवश्यकता होती है, तो उनके बीच दो समान आकार के गियर के लिए अपेक्षाकृत प्राइम गियर डाला जा सकता है।

प्री-कंप्यूटर क्रिप्टोग्राफी में, कुछ वर्नाम सिफर मशीनों ने विभिन्न लंबाई के कुंजी टेप के कई लूपों को संयोजित किया। कई रोटर मशीनें अलग-अलग संख्या में दांतों के रोटरों को जोड़ती हैं। ऐसे संयोजन तब सबसे अच्छा काम करते हैं जब लंबाई का पूरा समुच्चय युग्‍मानूसार सहअभाज्य हो।[12][13][14][15]

सामान्यीकरण

इस अवधारणा को अन्य बीजगणितीय संरचनाओं तक बढ़ाया जा सकता है उदाहरण के लिए, ऐसे बहुपद जिनका बहुपद सबसे बड़ा सामान्य भाजक 1 है, सहअभाज्य बहुपद कहलाते हैं।

यह भी देखें

टिप्पणियाँ

  1. Eaton, James S. (1872). अंकगणित पर एक ग्रंथ. Boston: Thompson, Bigelow & Brown. p. 49. Retrieved 10 January 2022. Two numbers are mutually prime when no whole number but one will divide each of them
  2. Hardy & Wright 2008, p. 6
  3. Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics / A Foundation for Computer Science, Addison-Wesley, p. 115, ISBN 0-201-14236-8
  4. Ore 1988, p. 47
  5. Niven & Zuckerman 1966, p. 22, Theorem 2.3(b)
  6. Niven & Zuckerman 1966, p. 6, Theorem 1.8
  7. Niven & Zuckerman 1966, p.7, Theorem 1.10
  8. Rosen 1992, p. 140
  9. This theorem was proved by Ernesto Cesàro in 1881. For a proof, see Hardy & Wright 2008, Theorem 332
  10. Saunders, Robert & Randall, Trevor (July 1994), "The family tree of the Pythagorean triplets revisited", Mathematical Gazette, 78: 190–193, doi:10.2307/3618576.
  11. Mitchell, Douglas W. (July 2001), "An alternative characterisation of all primitive Pythagorean triples", Mathematical Gazette, 85: 273–275, doi:10.2307/3622017.
  12. Klaus Pommerening. "Cryptology: Key Generators with Long Periods".
  13. David Mowry. "German Cipher Machines of World War II". 2014. p. 16; p. 22.
  14. Dirk Rijmenants. "Origins of One-time pad".
  15. Gustavus J. Simmons. "Vernam-Vigenère cipher".

संदर्भ

अग्रिम पठन

  • Lord, Nick (March 2008), "A uniform construction of some infinite coprime sequences", Mathematical Gazette, 92: 66–70