मॉड्यूलर गुणात्मक प्रतिलोम कैलकुलेटर

गणना दर्ज करें

पूर्णांक a

मॉड्यूलस m

परिणाम

गुणात्मक प्रतिलोम

4

a^-1 mod m

gcd(a, m)	1
प्रतिलोम मौजूद है	हाँ

मॉड्यूलर गुणात्मक प्रतिलोम (mod m) क्या होता है?

किसी पूर्णांक a का m के सापेक्ष मॉड्यूलर गुणात्मक प्रतिलोम वह पूर्णांक x होता है, जो 1 से m−1 की सीमा में हो और जिसके लिए \((a \cdot x) \bmod m = 1\) सही हो। सरल शब्दों में, जब a को x से गुणा करके m से भाग दिया जाए, तो शेषफल ठीक 1 बचे। यह मॉड्यूलर अंकगणित में "a से भाग देने" के समतुल्य है, और यही संख्या सिद्धांत (Number Theory) तथा क्रिप्टोग्राफी की नींव है — जैसे RSA कुंजी निर्माण, हैशिंग, चीनी शेषफल प्रमेय (Chinese Remainder Theorem) आदि।

Modular arithmetic wraps the number line into a circle of m positions.

इस कैलकुलेटर का उपयोग कैसे करें

पूर्णांक a और मॉड्यूलस m दर्ज करें (m का मान 2 या उससे अधिक होना चाहिए)। कैलकुलेटर पहले a को m के सापेक्ष कम करता है, फिर विस्तारित यूक्लिडियन एल्गोरिथम चलाता है और यदि प्रतिलोम मौजूद हो तो उसे दिखा देता है। a के ऋणात्मक मानों को यह स्वतः ही 0 से m−1 की सीमा में लाकर संभाल लेता है।

सूत्र की व्याख्या

प्रतिलोम केवल और केवल तभी मौजूद होता है जब \(\gcd(a, m) = 1\) हो — यानी a और m में 1 के अलावा कोई उभयनिष्ठ गुणनखंड न हो (वे सहभाज्य या coprime हों)। विस्तारित यूक्लिडियन एल्गोरिथम ऐसे पूर्णांक s और t ढूँढ़ता है जो \(a \cdot s + m \cdot t = \gcd(a, m)\) को संतुष्ट करें। $$\text{a} \cdot x \equiv 1 \pmod{\text{m}}, \quad x \text{ exists } \iff \gcd\!\left(\text{a},\, \text{m}\right) = 1$$ जब gcd 1 होता है, तो गुणांक s को m के सापेक्ष कम करने पर वही प्रतिलोम मिलता है। यदि \(\gcd(a, m) \neq 1\) हो, तो कोई प्रतिलोम मौजूद नहीं होता।

विज्ञापन

The extended Euclidean algorithm yields x satisfying a·x + m·y = 1.

हल किया हुआ उदाहरण

आइए 3 का 11 के सापेक्ष प्रतिलोम निकालें। हमें ऐसा x चाहिए जिसके लिए \((3 \cdot x) \bmod 11 = 1\) हो। आज़माने पर, $$3 \cdot 4 = 12, \quad 12 \bmod 11 = 1$$ अतः प्रतिलोम 4 है। चूँकि \(\gcd(3, 11) = 1\) है, इसलिए विस्तारित यूक्लिडियन एल्गोरिथम भी यही उत्तर तुरंत दे देता है।

विज्ञापन

Multiplying a by its inverse x lands exactly on 1 after wrapping mod m.

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

प्रतिलोम कब मौजूद नहीं होता? जब a और m सहभाज्य न हों। उदाहरण के लिए, 4 का mod 8 में कोई प्रतिलोम नहीं है, क्योंकि \(\gcd(4, 8) = 4 \neq 1\) है।

क्या मॉड्यूलस का अभाज्य (prime) होना ज़रूरी है? नहीं। कोई भी मॉड्यूलस चलेगा, बशर्ते a उसके सहभाज्य हो। यदि m अभाज्य है, तो 1 से m−1 तक का हर अशून्य a प्रतिलोम रखता है।

परिणाम हमेशा 1 और m−1 के बीच ही क्यों रहता है? क्योंकि हम प्रतिलोम को m के सापेक्ष कम करके उसका मानक (canonical) न्यूनतम धनात्मक रूप देते हैं।