चीनी शेषफल प्रमेय कैलकुलेटर

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

शेषफल 1 (a₁)

मापांक 1 (m₁)

शेषफल 2 (a₂)

मापांक 2 (m₂)

शेषफल 3 (a₃) — वैकल्पिक

मापांक 3 (m₃) — उपयोग न हो तो खाली छोड़ें

परिणाम

सबसे छोटा अऋणात्मक हल

8

x (mod 15)

अद्वितीय हल मौजूद है	Yes (mod 15)
उपयोग की गई सर्वांगसमताएँ	2
व्यापक हल	x = 8 + 15k

चीनी शेषफल प्रमेय क्या है?

चीनी शेषफल प्रमेय (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\) का एक ही अद्वितीय हल मौजूद होता है। यह कैलकुलेटर उसी सबसे छोटे अऋणात्मक हल को खोज निकालता है।

CRT एक ही बार में सभी सर्वांगसमताओं को संतुष्ट करने वाला mod M का एकमात्र मान खोजता है।

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

हर शेषफल \(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\) को छोड़कर बाकी सभी मापांकों से विभाज्य होता है, इसलिए प्रत्येक पद सही शेषफल केवल अपनी ही सर्वांगसमता में देता है।

प्रत्येक सर्वांगसमता एक पद a_i M_i y_i देती है, जिन्हें जोड़कर mod M में घटाया जाता है।

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

हल कीजिए: \(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\) की सीमा में घटा लिया जाता है।