चीनी शेषफल प्रमेय क्या है?
चीनी शेषफल प्रमेय (Chinese Remainder Theorem, CRT) संख्या सिद्धांत का एक प्रसिद्ध परिणाम है। इसके अनुसार, यदि आपके पास सर्वांगसमताओं की एक प्रणाली है — \(x \equiv a_1 \pmod{m_1}\), \(x \equiv a_2 \pmod{m_2}\), … — और इनके सभी मापांक (moduli) जोड़ीवार सहअभाज्य हों (यानी किन्हीं दो में कोई उभयनिष्ठ गुणनखंड न हो), तो \(M = m_1 \cdot m_2 \cdot \ldots\) के सापेक्ष \(x\) का एक ही अद्वितीय हल मौजूद होता है। यह कैलकुलेटर उसी सबसे छोटे अऋणात्मक हल को खोज निकालता है।
इस कैलकुलेटर का उपयोग कैसे करें
हर शेषफल \(a_i\) को उसके मापांक \(m_i\) के साथ भरें। आप दो या तीन सर्वांगसमताओं की प्रणाली हल कर सकते हैं — यदि केवल दो ही चाहिए, तो तीसरे मापांक वाला खाना खाली छोड़ दें। यह उपकरण पहले जाँचता है कि आपके मापांक जोड़ीवार सहअभाज्य हैं या नहीं, फिर \(x\) और संयुक्त मापांक \(M\) दोनों लौटाता है। ध्यान दें कि \(x + Mk\) (किसी भी पूर्णांक \(k\) के लिए) के रूप का हर मान भी एक हल होता है।
सूत्र की व्याख्या
मान लीजिए \(M = \prod m_i\)। हर सर्वांगसमता के लिए \(M_i = M / m_i\) और \(y_i = M_i^{-1} \bmod m_i\) परिभाषित करें (\(y_i\) वह मापांकीय व्युत्क्रम है जो विस्तारित यूक्लिडीय एल्गोरिदम से निकाला जाता है)। तब हल इस भारित योग के रूप में आता है:
$$x \equiv \sum_{i} a_i\,M_i\,y_i \pmod{M}$$चूँकि \(M_i\) अपने \(m_i\) को छोड़कर बाकी सभी मापांकों से विभाज्य होता है, इसलिए प्रत्येक पद सही शेषफल केवल अपनी ही सर्वांगसमता में देता है।
हल किया हुआ उदाहरण
हल कीजिए: \(x \equiv 2 \pmod{3}\) और \(x \equiv 1 \pmod{4}\)। यहाँ \(M = 3 \cdot 4 = 12\)। \(M_1 = 4\), और \(4 \equiv 1 \pmod{3}\) होने से \(y_1 = 1\); \(M_2 = 3\), और \(3 \equiv 3 \pmod{4}\) होने से \(y_2 = 3\) (क्योंकि \(3 \cdot 3 = 9 \equiv 1\))। तब $$x = 2 \cdot 4 \cdot 1 + 1 \cdot 3 \cdot 3 = 8 + 9 = 17 \equiv 5 \pmod{12}$$ 5 (mod 12)। जाँच कीजिए: \(5 \bmod 3 = 2\) ✓ और \(5 \bmod 4 = 1\) ✓।
अक्सर पूछे जाने वाले प्रश्न
मापांकों का सहअभाज्य होना क्यों ज़रूरी है? यदि दो मापांकों में कोई उभयनिष्ठ गुणनखंड हो, तो प्रणाली का या तो कोई हल नहीं होता या उनके ल.स. (lcm) के सापेक्ष कई हल हो सकते हैं — ऐसे में मानक CRT सूत्र लागू नहीं होता।
"सबसे छोटे अऋणात्मक हल" का क्या अर्थ है? सभी हल आपस में \(M\) के गुणजों जितने ही अलग होते हैं; कैलकुलेटर उनमें से वह हल बताता है जो \(0\) से \(M-1\) की सीमा में आता है।
क्या मैं ऋणात्मक शेषफल इस्तेमाल कर सकता हूँ? हाँ। हल निकालने से पहले इन्हें हर \(m_i\) के सापेक्ष \(0\) से \(m_i-1\) की सीमा में घटा लिया जाता है।
