Fermat से Modular Inverse

जोड़, घटाव और गुणा मॉड्यूलस के अंतर्गत अच्छी तरह काम करते हैं, लेकिन साधारण भाग नहीं करता। आप सीधे भाग देकर शेषफल नहीं ले सकते। ⚠️

इसका समाधान मॉड्यूलर प्रतिलोम है: x से भाग देने का अर्थ x के प्रतिलोम से गुणा करना होता है। इसलिए a / b mod m को a को b के प्रतिलोम से गुणा करने में बदला जाता है।

x का प्रतिलोम वह संख्या है जिसे x से मॉड्यूलस के अंतर्गत गुणा करने पर 1 मिलता है। साधारण अंकगणित में यह 1/x की भूमिका निभाता है।

प्रतिलोम तभी मौजूद होता है जब x और m में कोई समान गुणनखंड न हो। 1e9+7 जैसे अभाज्य मॉड्यूलस का उपयोग करने पर प्रत्येक अशून्य x का प्रतिलोम निश्चित रूप से होता है।

फर्मा का लघु प्रमेय कहता है कि किसी अभाज्य p के लिए, यदि x, p का गुणज नहीं है, तो x की p माइनस 1वीं घात 1 के सर्वांगसम होती है।

x का एक गुणनखंड अलग कर देने पर शेष भाग उसका प्रतिलोम होना चाहिए। इसलिए x का प्रतिलोम x की p माइनस 2वीं घात है, जिसका p से मॉड लिया गया हो।

यह घातांक बहुत बड़ा है, इसलिए पिछले पाठ की तेज़ घातांक गणना का उपयोग कीजिए। Python में pow को एक बार बुलाने से पूरा काम हो जाता है।

मॉड के अंतर्गत a को b से भाग देने के लिए a को b के प्रतिलोम से गुणा कीजिए। शेषफल p के मॉड्यूलो में वास्तविक भागफल के बिल्कुल बराबर होता है।

0 का कोई प्रतिलोम नहीं होता, क्योंकि शून्य से गुणा करने पर कोई भी संख्या 1 नहीं दे सकती। मॉड्यूलस के अंतर्गत घटकर शून्य बनने वाले मान से भाग देने से पहले जाँच अवश्य कीजिए।

फर्मा का प्रत्येक प्रतिलोम एक तेज़ घातांक गणना है, इसलिए इसमें O(log p) समय लगता है। कुछ भागों के लिए यह सस्ता है, लेकिन लाखों बार करने पर लागत बढ़ जाती है।

जब आपको बहुत सारे प्रतिलोम चाहिए हों, तो प्रत्येक तत्व के लिए pow बुलाने के बजाय एक चतुर रैखिक चरण से उनकी पूर्व-गणना कीजिए। अगले पाठ में nCr के लिए आपको इसी पर निर्भर रहना होगा।

अब आप अभाज्य मॉड्यूलस के अंतर्गत मॉड्यूलर प्रतिलोम से गुणा करके भाग कर सकते हैं। यह प्रतिलोम pow द्वारा x की p माइनस 2वीं घात के रूप में मिलता है। बस शून्य का प्रतिलोम कभी न निकालें। ✅