कोप्राइम पूर्णांक

गणित में, दो पूर्णांक $a$ तथा $b$ कोप्राइम, अपेक्षाकृत प्राइम या पारस्परिक रूप से प्राइम हैं यदि एकमात्र सकारात्मक पूर्णांक जो दोनों का विभाजक है, वह 1 है।^[1] नतीजतन, कोई भी अभाज्य संख्या जो विभाजित होती है $a$ विभाजित नहीं करता $b$ , और इसके विपरीत। यह उनके सबसे बड़े सामान्य भाजक (GCD) के 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] यह निर्धारित करने का एक तेज़ तरीका है कि क्या दो नंबर कोप्राइम हैं, यूक्लिडियन एल्गोरिथ्म और इसके तेज़ वेरिएंट जैसे कि बाइनरी जीसीडी एल्गोरिथम या लेहमर के जीसीडी एल्गोरिथम द्वारा दिया गया है।

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

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

पहले बिंदु के परिणामस्वरूप, यदि a और b सहअभाज्य हैं, तो कोई भी शक्तियाँ a हैं^{कश्मीर} और बी^मी.

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

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

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

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

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

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

समुच्चयों में समानता

पूर्णांकों का एक समुच्चय (गणित) S = {a₁, एक₂, .... एक_n} को कोप्राइम या सेटवाइज़ कोप्राइम भी कहा जा सकता है यदि सेट के सभी तत्वों का सबसे बड़ा सामान्य विभाजक 1 है। उदाहरण के लिए, पूर्णांक 6, 10, 15 कोप्राइम हैं क्योंकि 1 एकमात्र सकारात्मक पूर्णांक है जो उन सभी को विभाजित करता है।

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

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

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

अंगूठी के आदर्शों में समानता

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

कोप्रिमेलिटी की संभावना

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

अनौपचारिक रूप से, प्रायिकता कि कोई भी संख्या एक अभाज्य (या वास्तव में कोई पूर्णांक) से विभाज्य है $p$ है $1/p$ ; उदाहरण के लिए, प्रत्येक 7वां पूर्णांक 7 से विभाज्य है। इसलिए दो संख्याओं के p से विभाज्य होने की प्रायिकता है $1/p^{2}$ , और संभावना है कि उनमें से कम से कम एक नहीं है $1-1/p^{2}$ . अलग-अलग अभाज्य संख्याओं से जुड़ी विभाज्यता घटनाओं का कोई भी परिमित संग्रह परस्पर स्वतंत्र है। उदाहरण के लिए, दो घटनाओं के मामले में, एक संख्या अभाज्य संख्या p और q से विभाज्य है यदि और केवल यदि यह pq से विभाज्य है; बाद वाली घटना की प्रायिकता 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/sup>/6 बेसल समस्या है, जिसे लियोनहार्ड यूलर ने 1735 में हल किया था।}

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

अधिक आम तौर पर, यादृच्छिक रूप से चुने गए पूर्णांकों के कोप्राइम होने की संभावना है $1/{\zeta (k)}$ .

सभी कोप्राइम जोड़े बनाना

इस एल्गोरिथम द्वारा कोप्राइम जोड़े के निर्माण का क्रम। पहले नोड (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)$

यह योजना संपूर्ण है और गैर-निरर्थक है जिसमें कोई अमान्य सदस्य नहीं है।

अनुप्रयोग

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

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

सामान्यीकरण

इस अवधारणा को पूर्णांकों की अंगूठी की तुलना में अन्य बीजगणितीय संरचनाओं तक बढ़ाया जा सकता है $\mathbb {Z}$ ; उदाहरण के लिए, ऐसे बहुपद जिनका बहुपद का महत्तम समापवर्तक 1 है, सहअभाज्य बहुपद कहलाते हैं।

यह भी देखें

यूक्लिड का बाग
सुपरपार्टेंट नंबर

↑ Eaton, James S. (1872). अंकगणित पर एक ग्रंथ. Boston: Thompson, Bigelow & Brown. p. 49. Retrieved 10 January 2022. दो संख्याएँ परस्पर अभाज्य होती हैं जब कोई पूर्ण संख्या नहीं बल्कि एक उनमें से प्रत्येक को विभाजित करती है
↑ 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. दो संख्याएँ परस्पर अभाज्य होती हैं जब कोई पूर्ण संख्या नहीं बल्कि एक उनमें से प्रत्येक को विभाजित करती है

[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]