"मॉड्यूलर गुणात्मक उलटा" की गणना कैसे करें जब denominator एम के साथ सह-प्रधान नहीं है?

Question

मैं की गणना करनी है (a/b) mod m जहां a और b बहुत बड़ी संख्या है।

मुझे क्या करना कोशिश कर रहा हूँ (a mod m) * (x mod m), जहां xb की modular inverse है की गणना करने के लिए है।

मैंने Extended Euclidean algorithm का उपयोग करने की कोशिश की, लेकिन बी और एम सह-प्रधान नहीं होने पर क्या करना है? यह विशेष रूप से mentioned है कि बी और एम को सह-प्राइम होने की आवश्यकता है।

मैं कोड here उपयोग करने की कोशिश, और महसूस किया कि उदाहरण के लिए: 3 * x mod 12x के किसी भी मूल्य के लिए बिल्कुल भी संभव नहीं है, यह मौजूद नहीं है!

मुझे क्या करना चाहिए? क्या एल्गोरिदम किसी भी तरह संशोधित किया जा सकता है?

Answer 1

हाँ, आप परेशानी में हैं। एक्स और b*x = 1 mod m में एक्स का कोई समाधान नहीं है यदि बी और एम में एक आम विभाजक है। इसी तरह, आपकी मूल समस्या a/b = y mod m में, आप वाई की तलाश कर रहे हैं जैसे कि a=by mod m। यदि gcd(b,m) द्वारा विभाजित किया गया है, तो आप उस कारक से विभाजित हो सकते हैं और y के लिए हल कर सकते हैं। यदि नहीं, तो कोई y नहीं है जो समीकरण को हल कर सकता है (यानी a/b mod m परिभाषित नहीं किया गया है)।

Answer 2

इसे जांचें: http://www.math.harvard.edu/~sarah/magic/topics/division इससे मदद मिल सकती है। यह मॉड्यूलर विभाजन के तरीकों की व्याख्या करता है।

Answer 3

चीनी रेमेन्डर प्रमेय की वजह से बी और एम को कॉपी करना है। असल में समस्या:

3 * x mod 12

3*x mod 3 और 3*x mod 4 = 2^2

अब से जुड़े एक यौगिक समस्या के रूप में के बारे में सोचा जा सकता है, तो ख से 12 coprime नहीं है, यह शून्य से विभाजित करने के लिए कोशिश की तरह है । इस प्रकार उत्तर मौजूद नहीं है!

यह सार बीजगणित में क्षेत्र सिद्धांत के कारण है। एक क्षेत्र मूल रूप से एक सेट होता है जिसमें अतिरिक्त, घटाव, गुणा, और विभाजन अच्छी तरह परिभाषित होता है। एक परिमित क्षेत्र हमेशा जीएफ (पी^एन) के रूप में होता है, जहां पी प्राइम है और एन एक सकारात्मक पूर्णांक है, और संचालन अतिरिक्त और गुणा मॉड्यूलो पी^एन है। अब, 12 एक प्रमुख शक्ति नहीं है, इसलिए आपकी अंगूठी एक फ़ील्ड नहीं है। इस प्रकार इस समस्या को किसी भी बी के लिए हल नहीं किया जा सकता है जो एम के लिए coprime नहीं है।