यूलर टोटिएंट फलन कैलकुलेटर

यूलर टोटिएंट फलन φ(n) क्या है?

यूलर टोटिएंट फलन (Euler's totient function), जिसे φ(n) या phi(n) लिखा जाता है, संख्या सिद्धांत में सबसे महत्वपूर्ण फलनों में से एक है। एक सकारात्मक पूर्णांक n के लिए, φ(n) 1 से n तक के उन पूर्णांकों की संख्या की गणना करता है जो n के साथ सह-अभाज्य (coprime) हैं — यानी, जिनका महत्तम समापवर्तक gcd(k, n) = 1 होता है। इस फलन को 1763 में लियोनार्ड यूलर द्वारा पेश किया गया था।

उदाहरण के लिए, φ(12) = 4 क्योंकि 1 से 12 तक की संख्याओं में केवल 1, 5, 7 और 11 ही 12 के साथ कोई सामान्य गुणनखंड साझा नहीं करती हैं। 2, 3, 4, 6, 8, 9, 10 और 12 जैसी संख्याएं 12 के साथ सामान्य गुणनखंड साझा करती हैं।

यूलर का उत्पाद सूत्र (Euler's Product Formula)

φ(n) की गणना करने का सबसे कुशल तरीका यूलर उत्पाद सूत्र है। सबसे पहले, n का अभाज्य गुणनखंडन (prime factorization) खोजें:

n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ

फिर लागू करें:

φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × ... × (1 − 1/pₖ)

n = 60 = 2² × 3 × 5 के लिए: φ(60) = 60 × (1 − 1/2) × (1 − 1/3) × (1 − 1/5) = 60 × 1/2 × 2/3 × 4/5 = 16. यह सूत्र इसलिए काम करता है क्योंकि टोटिएंट एक गुणात्मक फलन (multiplicative function) है — यदि gcd(a, b) = 1 है, तो φ(ab) = φ(a) × φ(b) होता है।

प्रमुख गुण

• φ(1) = 1 — 1 ही एकमात्र संख्या है जो स्वयं के साथ सह-अभाज्य है।
• φ(p) = p − 1 किसी भी अभाज्य (prime) संख्या p के लिए — 1 से p−1 तक के सभी पूर्णांक p के साथ सह-अभाज्य हैं।
• φ(p^k) = p^(k-1) × (p − 1) अभाज्य घातों के लिए।
• गुणात्मकता (Multiplicative): φ(mn) = φ(m) × φ(n) जब gcd(m, n) = 1।
• φ(n) हमेशा सम (even) होता है n > 2 के लिए।

यूलर का प्रमेय (Euler's Theorem)

यूलर का प्रमेय मोड्यूलर अंकगणित का एक महत्वपूर्ण सिद्धांत है: यदि gcd(a, n) = 1 हो, तो:

a^φ(n) ≡ 1 (mod n)

यह फर्मेट के छोटे प्रमेय (Fermat's Little Theorem) का सामान्यीकरण है। यूलर के प्रमेय का उपयोग क्रिप्टोग्राफी में मॉड्यूलस व्युत्क्रमों की गणना करने और तेजी से मॉड्यूलस घातांक करने के लिए किया जाता है।

RSA क्रिप्टोग्राफी संबंध

RSA, जो कि व्यापक रूप से उपयोग की जाने वाली सार्वजनिक-कुंजी क्रिप्टोग्राफिक प्रणाली है, सीधे यूलर के टोटिएंट फलन पर आधारित है:

• दो बड़े अभाज्य p और q चुनें।
• n = p × q सेट करें (RSA मॉड्यूलस)।
• φ(n) = (p − 1)(q − 1) की गणना करें।
• सार्वजनिक घातांक e चुनें जहाँ gcd(e, φ(n)) = 1 हो।
• निजी घातांक d की गणना करें ताकि e × d ≡ 1 (mod φ(n)) हो।

इसकी सुरक्षा n के गुणनखंडन की कठिनाई पर निर्भर करती है।