यूलर टोशेंट फ़ंक्शन क्या है?
यूलर टोशेंट फ़ंक्शन, जिसे \(\varphi(n)\) लिखा जाता है, यह गिनता है कि 1 से लेकर n तक कितने धनात्मक पूर्णांक ऐसे हैं जिनका n के साथ 1 के अलावा कोई उभयनिष्ठ गुणनखंड नहीं है — यानी वे पूर्णांक जो n के सहअभाज्य (coprime) हैं। उदाहरण के लिए, \(\varphi(9) = 6\) है क्योंकि 1, 2, 4, 5, 7 और 8 ये सभी 9 के सहअभाज्य हैं। यह फ़ंक्शन संख्या सिद्धांत (number theory) का एक आधारभूत हिस्सा है और क्रिप्टोग्राफ़ी में हर जगह दिखाई देता है, खासकर मशहूर RSA एल्गोरिथ्म में, जहाँ \(\varphi(n)\) उस मॉड्यूलर व्युत्क्रम (modular inverse) को तय करता है जिससे कुंजियाँ बनाई जाती हैं।
इस कैलकुलेटर का उपयोग कैसे करें
कोई भी धनात्मक पूर्णांक n दर्ज करें और "गणना करें" दबाएँ। यह टूल n को उसके अलग-अलग अभाज्य भाजकों में बाँटता है और गुणनफल सूत्र लगाकर तुरंत \(\varphi(n)\) लौटा देता है, साथ ही उन अलग-अलग अभाज्य संख्याओं की सूची भी दिखाता है जो उसने पाईं। यह छोटी संख्याओं के साथ-साथ एक अरब तक की बहुत बड़ी संख्याओं के लिए भी काम करता है।
सूत्र की व्याख्या
टोशेंट निकालने का सबसे कारगर तरीका गुणनफल सूत्र है:
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$
जिसमें n को विभाजित करने वाली हर अलग-अलग अभाज्य संख्या \(p\) को शामिल किया जाता है।
आपको केवल अलग-अलग अभाज्य संख्याओं की ज़रूरत होती है, उनकी पुनरावृत्ति (multiplicity) की नहीं। हर पद \(\left(1 - \frac{1}{p}\right)\) उस अभाज्य से विभाज्य होने वाली संख्याओं के हिस्से को घटा देता है।
हल किया हुआ उदाहरण
मान लीजिए n = 36। इसका अभाज्य गुणनखंडन \(2^2 \times 3^2\) है, इसलिए अलग-अलग अभाज्य संख्याएँ 2 और 3 हैं। तब:
$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$
यानी 1 से 36 के बीच ठीक 12 पूर्णांक ऐसे हैं जो 36 के सहअभाज्य हैं।
अधिक कार्य किए गए उदाहरण
उदाहरण 1: एक अभाज्य संख्या, φ(13)
13 एक अभाज्य संख्या है, इसलिए इसका एकमात्र अभाज्य गुणनखंड स्वयं 13 है:
\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12। यह अभाज्य शॉर्टकट \(\varphi(p) = p-1\) से मेल खाता है।
उदाहरण 2: एक अभाज्य घात, φ(32)
गुणनखंड: \(32 = 2^5\)। केवल एक भिन्न अभाज्य गुणनखंड है, 2।
\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16।
समतुल्य अभाज्य-घात रूप: \(\varphi(p^k) = p^k - p^{k-1}\), इसलिए \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\)। ये ठीक 1 से 31 तक की विषम संख्याएँ हैं।
उदाहरण 3: तीन या अधिक भिन्न अभाज्य संख्याएँ, φ(210)
गुणनखंड: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\)।
- \(210\) से शुरू करें।
- \(1-\frac{1}{2} = \frac{1}{2}\) से गुणा करें: \(210 \cdot \frac{1}{2} = 105\)।
- \(1-\frac{1}{3} = \frac{2}{3}\) से गुणा करें: \(105 \cdot \frac{2}{3} = 70\)।
- \(1-\frac{1}{5} = \frac{4}{5}\) से गुणा करें: \(70 \cdot \frac{4}{5} = 56\)।
- \(1-\frac{1}{7} = \frac{6}{7}\) से गुणा करें: \(56 \cdot \frac{6}{7} = 48\)।
इसलिए \(\varphi(210) = \)48। ध्यान दें कि उत्पाद नियम में प्रत्येक भिन्न अभाज्य संख्या का उपयोग केवल एक बार होता है। उदाहरण के लिए, \(60 = 2^2 \cdot 3 \cdot 5\) के लिए \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\) आता है।
φ(n) की व्याख्या और इसके उपयोग
- अभाज्यता संबंध: \(n \ge 2\) के लिए, \(\varphi(n) = n-1\) तभी होता है जब और केवल जब \(n\) अभाज्य हो। किसी अभाज्य से छोटी हर संख्या उसके सापेक्षतः अभाज्य होती है। यदि \(n\) भाज्य है, तो उससे छोटी कम से कम एक संख्या का कोई गुणनखंड साझा होता है, इसलिए \(\varphi(n) < n-1\)।
- इकाइयों का समूह: \(\varphi(n)\) मॉड्यूलो \(n\) के इकाइयों के समूह में अवयवों की संख्या है, यानी वे अवशेष जिनका mod \(n\) गुणनात्मक व्युत्क्रम होता है। \(n = 15\) के लिए ये 1, 2, 4, 7, 8, 11, 13, 14 हैं, जो 8 अवयव देते हैं।
- ऑयलर प्रमेय: यदि \(\gcd(a, n) = 1\), तो \(a^{\varphi(n)} \equiv 1 \pmod{n}\)। उदाहरण: \(a = 2\), \(n = 15\), \(\varphi(15) = \)8, और \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\)। फ़र्मा का छोटा प्रमेय तब का विशेष स्थिति है जब \(n = p\) अभाज्य हो।
- RSA: जब \(n = pq\) हो, जहाँ \(p\) और \(q\) भिन्न अभाज्य संख्याएँ हैं, तो \(\varphi(n) = (p-1)(q-1)\)। \(n = 15 = 3 \cdot 5\) के साथ: \(\varphi(15) = 2 \cdot 4 = 8\)। सार्वजनिक घातांक \(e\) का \(\varphi(n)\) के सापेक्षतः अभाज्य होना आवश्यक है, और निजी घातांक \(d\) संतुष्ट करता है \(ed \equiv 1 \pmod{\varphi(n)}\)। वास्तविक RSA सैकड़ों अंकों लंबी अभाज्य संख्याओं का उपयोग करता है। जो कोई भी \(n\) का गुणनखंडन कर सकता है, वह \(\varphi(n)\) की गणना कर सकता है, इसीलिए सुरक्षा गुणनखंडन के कठिन होने पर टिकी है।
- अनुपात केवल भिन्न अभाज्य संख्याओं पर निर्भर करता है: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\)। घातांक मायने नहीं रखते। उदाहरण के लिए, 6 और 12 दोनों का अभाज्य समुच्चय {2, 3} है, इसलिए \(\varphi(6)/6 = 2/6 = 1/3\) और \(\varphi(12)/12 = 4/12 = 1/3\)।
अक्सर पूछे जाने वाले सवाल
\(\varphi(1)\) कितना होता है? परंपरा के अनुसार \(\varphi(1) = 1\) होता है, क्योंकि 1 स्वयं के सहअभाज्य माना जाता है।
किसी अभाज्य संख्या p का φ कितना होता है? किसी भी अभाज्य \(p\) के लिए \(\varphi(p) = p - 1\) होता है, क्योंकि 1 से \(p-1\) तक का हर पूर्णांक p के सहअभाज्य होता है।
क्या φ गुणनात्मक (multiplicative) है? हाँ। यदि \(\gcd(a, b) = 1\) हो तो \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\) होता है — और ठीक यही कारण है कि अलग-अलग अभाज्य संख्याओं पर गुणनफल वाला तरीका काम करता है।