ऑयलर का टोशिएंट फलन समझें

1 से 10 तक की संख्याएँ लिखें और हर उस संख्या को काट दें जिसका 10 के साथ कोई उभयनिष्ठ गुणनखंड हो। चार बचती हैं: 1, 3, 7 और 9। यह गिनती, φ(10) = 4, ऑयलर का टोशिएंट फलन है, संख्या सिद्धांत के सबसे ज़्यादा इस्तेमाल होने वाले फलनों में से एक, भिन्नों और घड़ियों से लेकर ऑनलाइन भुगतानों की रक्षा करने वाले एन्क्रिप्शन तक।

एक ग्रिड में 1 से 30 तक की संख्याएँ, जिनमें 30 की आठ सहअभाज्य संख्याएँ भरी हुई हैं, सूत्र φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8, और φ(k) का एक ग्राफ़ जिसमें अभाज्य संख्याएँ एक सीधी रेखा पर हैं
एक ग्रिड में 1 से 30 तक की संख्याएँ, जिनमें 30 की आठ सहअभाज्य संख्याएँ भरी हुई हैं, सूत्र φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8, और φ(k) का एक ग्राफ़ जिसमें अभाज्य संख्याएँ एक सीधी रेखा पर हैं

सहअभाज्य संख्याएँ गिनना

दो संख्याएँ सहअभाज्य होती हैं जब उनका महत्तम समापवर्तक 1 हो। φ(n) 1 से n तक के उन k को गिनता है जिनके लिए gcd(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 और φ(1) = 1। यही गिनती कई जगह सामने आती है। यह 0 और 1 के बीच की उन भिन्नों k/n की संख्या है जो पहले से सरलतम रूप में हैं, उन कदमों की लंबाइयों की संख्या है जो n घंटों वाली घड़ी में सुई को हर घंटे से गुज़ारती हैं, और उन k की संख्या है जिनका मापांक n में व्युत्क्रम है, ताकि k × x ≡ 1 (mod n) हल हो सके।

गुणनफल सूत्र

यदि n को विभाजित करने वाली अभाज्य संख्याएँ p₁, p₂ … हैं, तो φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …। इसका कारण एक छलनी है। सभी संख्याओं में से आधी सम हैं, इसलिए 2 के गुणज हटाने पर 1 − 1/2 हिस्सा बचता है; बची हुई संख्याओं में हर तीसरी 3 की गुणज है, और इसी तरह आगे। चीनी शेषफल प्रमेय के अनुसार अलग-अलग अभाज्यों की शर्तें स्वतंत्र हैं, इसलिए हिस्से सीधे गुणा हो जाते हैं। 100 = 2² × 5² के लिए इससे 100 × 1/2 × 4/5 = 40 मिलता है। दो गुणधर्म यही परिणाम दूसरे रूप में देते हैं: φ(p^k) = p^(k−1)(p − 1), और जब m और n सहअभाज्य हों तो φ(mn) = φ(m) φ(n), इसलिए φ(100) = φ(4) × φ(25) = 2 × 20 = 40।

ऑयलर प्रमेय

फ़र्मा ने 1640 में देखा कि किसी अभाज्य p और p से विभाज्य न होने वाले हर a के लिए a^(p−1) ≡ 1 (mod p)। ऑयलर ने इसका सामान्य रूप सिद्ध किया, जो 1763 में प्रकाशित हुआ: जब भी gcd(a, n) = 1 हो, a^φ(n) ≡ 1 (mod n)। प्रमाण छोटा है। n की φ(n) सहअभाज्य संख्याओं को a से गुणा करें; गुणनफल फिर से n के सहअभाज्य होते हैं और मापांक n में सभी अलग होते हैं, यानी वे वही संख्याएँ हैं, बस दूसरे क्रम में, और दोनों गुणनफलों की तुलना करने पर a^φ(n) ≡ 1 बचता है। किसी दिए गए a के लिए काम करने वाला सबसे छोटा घातांक उसकी कोटि है, जो हमेशा φ(n) को विभाजित करती है; सभी a के लिए एक साथ काम करने वाला सबसे छोटा घातांक कारमाइकल फलन λ(n) है। 561 = 3 × 11 × 17 के लिए λ(561) = 80, 560 को विभाजित करता है, इसलिए 561 के सहअभाज्य हर a के लिए a^560 ≡ 1 (mod 561), जबकि 561 अभाज्य नहीं है। यह सबसे छोटी कारमाइकल संख्या है, और यही कारण है कि अकेला फ़र्मा परीक्षण यह सिद्ध नहीं कर सकता कि कोई संख्या अभाज्य है।

लियोनहार्ड ऑयलर, याकोब एमानुएल हांटमान के चित्र में। उन्होंने 1763 में फ़ermat की टिप्पणी का सामान्य रूप प्रकाशित किया: जब a और n परस्पर अभाज्य हों, तब a^φ(n) ≡ 1 (mod n)।
लियोनहार्ड ऑयलर, याकोब एमानुएल हांटमान के चित्र में। उन्होंने 1763 में फ़ermat की टिप्पणी का सामान्य रूप प्रकाशित किया: जब a और n परस्पर अभाज्य हों, तब a^φ(n) ≡ 1 (mod n)।

गाउस का भाजक योग और औसत

n के भाजकों d पर φ(d) को जोड़ें और आपको हमेशा फिर से n मिलता है: 12 के लिए φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12। गाउस ने इसे 1801 की अपनी कृति डिस्क्विज़िशनेस अरिथमेटिके में सिद्ध किया; भिन्नों 1/12, 2/12 … 12/12 को सरलतम रूप में लाकर उनके हरों के अनुसार छाँटने पर यह दिखता है। औसतन φ(k) लगभग 0.61 k होता है: φ(k)/k का औसत 6/π² ≈ 0.6079 की ओर जाता है, जो इस बात की प्रायिकता भी है कि दो यादृच्छिक पूर्णांक सहअभाज्य हों, और φ(1) + … + φ(N) लगभग 3N²/π² के बराबर होता है। N = 1,000 के लिए योग 304,192 है, जबकि 3N²/π² ≈ 303,964।

कार्ल फ़्रीड्रिश गाउस, क्रिस्चियन आल्ब्रेख्त येन्सेन के 1840 के चित्र में। उन्होंने 1801 की Disquisitiones Arithmeticae में सर्वांगसमता संकेत a ≡ b (mod n) को प्रस्तुत किया।
कार्ल फ़्रीड्रिश गाउस, क्रिस्चियन आल्ब्रेख्त येन्सेन के 1840 के चित्र में। उन्होंने 1801 की Disquisitiones Arithmeticae में सर्वांगसमता संकेत a ≡ b (mod n) को प्रस्तुत किया।

कभी न आने वाले मान

3 से आगे हर n के लिए φ(n) सम होता है, क्योंकि n की सहअभाज्य संख्याएँ k और n − k के जोड़ों में आती हैं। हर सम संख्या भी कोई मान नहीं होती: 14, 26, 34, 38 और 50 वे पहली संख्याएँ हैं जो कभी नहीं आतीं, जबकि 24 दस अलग-अलग संख्याओं का मान है, 35 से 90 तक। इन्हें खोजना एक सीमित खोज है, क्योंकि n को विभाजित करने वाले हर अभाज्य p के लिए p − 1 को φ(n) को विभाजित करना होगा। 1907 में रॉबर्ट कारमाइकल ने दावा किया कि कोई भी मान ठीक एक बार नहीं आता। उनका प्रमाण ग़लत था, दावा आज भी खुला है, और कोई भी अपवाद 10^(10^10) से बड़ा होना चाहिए। डी. एच. लेहमर ने 1932 में पूछा कि क्या किसी भाज्य n के लिए φ(n), n − 1 को विभाजित कर सकता है; कोई उदाहरण ज्ञात नहीं है।

RSA में टोशिएंट

RSA दो बड़ी अभाज्य संख्याएँ p और q चुनता है और n = pq तथा एक घातांक e प्रकाशित करता है। क्योंकि φ(n) = (p − 1)(q − 1), जो कोई n के गुणनखंड कर सके वह φ(n) निकाल सकता है, और उससे निजी घातांक d जिसके लिए e × d ≡ 1 (mod φ(n)); फिर ऑयलर प्रमेय सुनिश्चित करता है कि (m^e)^d ≡ m (mod n)। पाठ्यपुस्तक के उदाहरण n = 3233 = 61 × 53 में φ(n) = 3,120, e = 17 और d = 2,753। कई कार्यान्वयन इसके बजाय λ(n) = lcm(p − 1, q − 1) का उपयोग करते हैं, यहाँ 780, जिससे छोटा d = 413 मिलता है। 600 अंकों वाले RSA मापांक के लिए φ(n) निकालना उतना ही कठिन है जितना उसके गुणनखंड करना: n और φ(n) से दोनों अभाज्य संख्याएँ एक ही वर्गमूल से मिल जाती हैं।

रॉन रिवेस्ट, आदि शमीर और लेन एडलमैन (बाएँ से दाएँ)
रॉन रिवेस्ट, आदि शमीर और लेन एडलमैन (बाएँ से दाएँ)

ख़ुद आज़माएँ

कैलकुलेटर खोलें और 10^18 तक कोई भी n दर्ज करें, ताकि φ(n) उसके अभाज्य गुणनखंडों और सूत्र के साथ दिखे। 500 तक 1 से n तक की संख्याएँ बनाई जाती हैं, सहअभाज्य संख्याएँ भरी हुई और बाकी उस सबसे छोटी अभाज्य संख्या के रंग में जो उनमें और n में साझा है, ताकि गुणनफल सूत्र एक ऐसी छलनी बन जाए जिसे गिना जा सके। ऑयलर प्रमेय जाँचने के लिए कोई संख्या a चुनें, रेखा φ(p) = p − 1 पर अभाज्य संख्याओं के साथ 100,000 तक φ(k) देखने के लिए ‘ग्राफ़’ पर जाएँ, या φ(n) = m वाले सभी n खोजने के लिए ‘व्युत्क्रम’ पर।

अक्सर पूछे जाने वाले प्रश्न

φ(1) = 1 क्यों है?

क्योंकि gcd(1, 1) = 1: 1 से 1 तक की एकमात्र संख्या 1 की सहअभाज्य है। यह परिपाटी सूत्रों को भी सही बनाए रखती है, जैसे n के भाजकों पर गाउस का योग, जो n = 1 के लिए बस φ(1) = 1 है।

क्या φ और अभाज्य गणन फलन एक ही हैं?

नहीं। π(n), n तक की अभाज्य संख्याएँ गिनता है, और φ(n), n तक की वे संख्याएँ जो n की सहअभाज्य हैं। φ(10) = 4 संख्याओं 1, 3, 7 और 9 को गिनता है, जबकि π(10) = 4 संख्याओं 2, 3, 5 और 7 को। यहाँ उनका बराबर होना संयोग है: φ(12) = 4, लेकिन π(12) = 5।

φ(n) कितनी तेज़ी से निकाला जा सकता है?

उतनी ही तेज़ी से जितनी तेज़ी से n के गुणनखंड हो सकें। अभाज्य गुणनखंड पता हों तो कुछ गुणाएँ काफ़ी हैं; पता न हों तो कोई तेज़ विधि ज्ञात नहीं है, और RSA इसी पर टिका है। 10^18 तक की संख्याओं के गुणनखंड ब्राउज़र में कुछ मिलीसेकंड लेते हैं, सैकड़ों अंकों वाली संख्याओं में वर्षों लग सकते हैं।

किन संख्याओं का φ(n), n की तुलना में सबसे छोटा होता है?

जिन संख्याओं के कई छोटे अभाज्य गुणनखंड हों। φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… केवल इस पर निर्भर करता है कि कौन-सी अभाज्य संख्याएँ n को विभाजित करती हैं, उनकी घातों पर नहीं: 2 की हर घात के लिए यह ठीक 1/2 है, और 30 = 2 × 3 × 5 के लिए 8/30, लगभग 27%। पहली 15 अभाज्य संख्याओं के गुणनफल 614,889,782,588,491,410 का φ(n)/n ≈ 14% है, जो 10^18 तक की सभी संख्याओं में सबसे कम है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

टोशिएंट कैलकुलेटर खोलें