सहअभाज्य पूर्णांक

संख्या सिद्धांत में, दो पूर्णांक $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\perp b$ का प्रस्ताव दिया कि $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 \equiv 1 (mod a)$ द्वारा आदि। वलय-सैद्धांतिक भाषा में, $b$ पूर्णांक मॉड्यूलर अंकगणित $a$ के वलय (गणित) $\mathbb {Z} /a\mathbb {Z}$ में एक इकाई (वलय सिद्धांत) है।
$x \equiv k (mod a)$ और $x \equiv m (mod b)$ के रूप के किसी अज्ञात पूर्णांक $x$ के लिए सर्वांगसम संबंधों के प्रत्येक युग्म का हल होता है (चीनी शेषफल प्रमेय); वस्तुतः हलों का वर्णन एकल सर्वांगसम संबंध मॉड्यूल $ab$ द्वारा किया जाता है।
$a$ और $b$ का लघुत्तम समापवर्त्य उनके गुणनफल $ab$ के समतुल्य है, अर्थात $lcm(a, b) = ab$ ।^[4]

अतः तीसरे बिंदु के परिणामस्वरूप, यदि $a$ और $b$ सहअभाज्य हैं और $br \equiv bs (mod a)$ , तो $r \equiv s (mod a)$ ।^[5] अर्थात्, मॉड्यूल $a$ कार्य करते समय हम " $b$ से विभाजित" हो सकते हैं। इसके अतिरिक्त, यदि $b 1, b 2$ दोनों $a$ के साथ सहअभाज्य हैं, तो उनका गुणनफल $b 1 b 2$ भी ऐसा ही है (अर्थात्, मॉड्यूल $a$ यह व्युत्क्रमणीय अवयवों का गुणनफल है, और इसलिए व्युत्क्रमणीय है);^[6] यह यूक्लिड के लेम्मा के पूर्व बिंदु से भी अनुसरण करता है, जो बताता है कि यदि एक अभाज्य संख्या $p$ किसी गुणनफल $bc$ को विभाजित करती है, तो $p$ कम से कम एक कारक $b, c$ को विभाजित करता है।

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

अतः यदि $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$ सहअभाज्य हैं यदि और मात्र यदि संख्याएँ $2 a - 1$ और $2 b - 1$ सहअभाज्य हैं।^[8] इसके सामान्यीकरण के रूप में, सूत्र $n > 1$ :

\gcd \left(n^{a}-1,n^{b}-1\right)=n^{\gcd(a,b)}-1

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

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

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

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

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

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

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

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

सहप्राथमिकता की प्रायिकता

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

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

\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\%.

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

इस प्रकार से यादृच्छिक रूप से धनात्मक पूर्णांक चुनने की कोई विधि नहीं है जिससे कि प्रत्येक धनात्मक पूर्णांक समान प्रायिकता के साथ हो, परन्तु ऊपर दिए गए जैसे यादृच्छिक रूप से चुने गए पूर्णांकों के विषय में कथनों को प्राकृतिक घनत्व की धारणा का प्रयोग करके औपचारिक रूप दिया जा सकता है। प्रत्येक धनात्मक पूर्णांक $N$ के लिए, मान लीजिए $P N$ यह प्रायिकता है कि $\{1,2,\ldots ,N\}$ में दो यादृच्छिक रूप से चुनी गई संख्याएँ सहअभाज्य हैं। यद्यपि $P N$ कभी भी $6/ π 2$ के समतुल्य नहीं होगा, कार्य के साथ^[9] कोई यह दिखा सकता है कि $N\to \infty$ के रूप में सीमा में, प्रायिकता $P N$ $6/ π 2$ तक पहुंचती है।

अधिक सामान्यतः, यादृच्छिक रूप से चुने गए $k$ के सहअभाज्य होने की प्रायिकता ${\tfrac {1}{\zeta (k)}}.$ है।

सभी सहअभाज्य युग्म उत्पन्न करना

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

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

शाखा 1: $(2m-n,m)$
शाखा 2: $(2m+n,m)$
शाखा 3: $(m+2n,n)$

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

यदि $a>3b,$ तो $(a,b)$ शाखा 3 के साथ $(m,n)=(a-2b,b)$ का एक बच्चा है;
यदि $2b<a<3b,$ तो $(a,b)$ शाखा 2 के साथ $(m,n)=(b,a-2b)$ का एक बच्चा है;
यदि $b<a<2b,$ तो $(a,b)$ शाखा 1 के साथ $(m,n)=(b,2b-a)$ का एक बच्चा है।

सभी स्थितियों में $(m,n)$ $m>n$ के साथ एक "छोटा" सहअभाज्य युग्म है। "पिता की गणना" की यह प्रक्रिया मात्र $a=2b$ या $a=3b$ होने पर ही रुक सकती है। इन स्थितियों में, सह-प्राथमिकता का तात्पर्य यह है कि युग्म या तो $(2,1)$ या $(3,1)$ है।

अनुप्रयोग

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

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

सामान्यीकरण

इस अवधारणा को $\mathbb {Z}$ के अतिरिक्त अन्य बीजगणितीय संरचनाओं तक बढ़ाया जा सकता है; इस प्रकार से उदाहरण के लिए, ऐसे बहुपद जिनका बहुपद सबसे बड़ा सामान्य भाजक 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
↑ Hardy & Wright 2008, p. 6
↑ 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
↑ Ore 1988, p. 47
↑ Niven & Zuckerman 1966, p. 22, Theorem 2.3(b)
↑ Niven & Zuckerman 1966, p. 6, Theorem 1.8
↑ Niven & Zuckerman 1966, p.7, Theorem 1.10
↑ Rosen 1992, p. 140
↑ This theorem was proved by Ernesto Cesàro in 1881. For a proof, see Hardy & Wright 2008, Theorem 332
↑ Saunders, Robert & Randall, Trevor (July 1994), "The family tree of the Pythagorean triplets revisited", Mathematical Gazette, 78: 190–193, doi:10.2307/3618576.
↑ Mitchell, Douglas W. (July 2001), "An alternative characterisation of all primitive Pythagorean triples", Mathematical Gazette, 85: 273–275, doi:10.2307/3622017.
↑ Klaus Pommerening. "Cryptology: Key Generators with Long Periods".
↑ David Mowry. "German Cipher Machines of World War II". 2014. p. 16; p. 22.
↑ Dirk Rijmenants. "Origins of One-time pad".
↑ Gustavus J. Simmons. "Vernam-Vigenère cipher".

संदर्भ

Hardy, G.H.; Wright, E.M. (2008), An Introduction to the Theory of Numbers (6th ed.), Oxford University Press, ISBN 978-0-19-921986-5
Niven, Ivan; Zuckerman, Herbert S. (1966), An Introduction to the Theory of Numbers (2nd ed.), John Wiley & Sons
Ore, Oystein (1988) [1948], Number Theory and Its History, Dover, ISBN 978-0-486-65620-5^{[dead link]}
Rosen, Kenneth H. (1992), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, ISBN 978-0-201-57889-8

अग्रिम पठन

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

[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".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]