चीनी शेषफल प्रमेय कैलकुलेटर (Chinese Remainder Theorem Calculator)
युगपत रैखिक सर्वांगसमता प्रणालियों x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ... को चरण-दर-चरण समाधान के साथ हल करें
चरण-दर-चरण समाधान (Step-by-Step Solution)
चीनी शेषफल प्रमेय (CRT) क्या है?
चीनी शेषफल प्रमेय (Chinese Remainder Theorem) संख्या सिद्धांत के प्राचीनतम और सबसे महत्वपूर्ण परिणामों में से एक है। यह बताता है कि यदि m₁, m₂, ..., mₙ परस्पर सह-अभाज्य (pairwise coprime) धनात्मक पूर्णांक हैं (अर्थात प्रत्येक युग्म का महत्तम समापवर्तक GCD = 1 हो), तो निम्न युगपत सर्वांगसमता प्रणाली (simultaneous congruences):
x ≡ a₂ (mod m₂)
⋮
x ≡ aₙ (mod mₙ)
का M = m₁ × m₂ × ... × mₙ के सापेक्ष एक अद्वितीय हल (unique solution) होता है। इसका अर्थ है कि अंतराल [0, M) में ठीक एक ऐसा पूर्णांक x मौजूद है जो एक साथ इन सभी समीकरणों को संतुष्ट करता है, और अन्य सभी सामान्य हल x₀ + kM के रूप में होते हैं (जहाँ k एक पूर्णांक है)।
इस प्रमेय की उत्पत्ति प्राचीन चीनी पाठ सनजी सुआंजिंग (Sunzi Suanjing) (तीसरी-पांचवीं शताब्दी ईस्वी) से मानी जाती है, जिसने यह सवाल उठाया था: "एक ऐसी संख्या खोजें जिसे 3 से विभाजित करने पर 2 शेष बचे; 5 से विभाजित करने पर 3 शेष बचे; और 7 से विभाजित करने पर 2 शेष बचे।" इसका उत्तर x = 23 है।
CRT सूत्र और एल्गोरिथ्म
CRT का रचनात्मक प्रमाण समाधान के लिए एक स्पष्ट सूत्र प्रदान करता है:
Mᵢ = M / mᵢ (mᵢ को छोड़कर अन्य सभी मापांकों का गुणनफल)
y.ᵢ ≡ Mᵢ⁻¹ (mod m.ᵢ) (M.ᵢ का मॉड्यूलर व्युत्क्रम)
x = (a₁·M₁·y₁ + a₂·M₂·y₂ + ... + aₙ·Mₙ·yₙ) mod M
यहाँ मुख्य विचार यह है कि प्रत्येक पद aᵢ·Mᵢ·y.ᵢ ≡ a.ᵢ (mod m.ᵢ) और ≡ 0 (mod m.ⱼ) (j ≠ i के लिए) होता है, क्योंकि M.ᵢ में m.ᵢ को छोड़कर हर अन्य m.ⱼ शामिल है। इससे ये पद "orthogonal" हो जाते हैं — प्रत्येक पद अन्य को प्रभावित किए बिना ठीक एक सर्वांगसमता को हल करता है।
हल किया गया उदाहरण — सनजी की समस्या
हल करें: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
चरण 2: Mᵢ मानों की गणना करें
M₁ = 105/3 = 35
M₂ = 105/5 = 21
M₃ = 105/7 = 15
चरण 3: मॉड्यूलर व्युत्क्रम yᵢ = Mᵢ⁻¹ (mod mᵢ) ज्ञात करें
y₁ = 35⁻¹ mod 3: 35 ≡ 2 (mod 3), 2×2=4≡1 (mod 3) → y₁ = 2
y₂ = 21⁻¹ mod 5: 21 ≡ 1 (mod 5), 1×1=1 (mod 5) → y₂ = 1
y₃ = 15⁻¹ mod 7: 15 ≡ 1 (mod 7), 1×1=1 (mod 7) → y₃ = 1
चरण 4: सूत्र में मान रखकर जोड़ें
x = (2×35×2) + (3×21×1) + (2×15×1) mod 105
x = 140 + 63 + 30 = 233 mod 105
x = 23 ✓
सत्यापन: 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓। सामान्य हल: x = 23 + 105k (पूर्णांक k के लिए)।
विस्तारित यूक्लिडियन एल्गोरिथ्म (Extended Euclidean Algorithm)
मॉड्यूलर व्युत्क्रम y.ᵢ = M.ᵢ⁻¹ (mod m.ᵢ) को विस्तारित यूक्लिडियन एल्गोरिथ्म का उपयोग करके खोजा जाता है, जो Bezout के समीकरण a·x + b·y = GCD(a, b) को संतुष्ट करने वाले पूर्णांकों x और y की गणना करता है। जब GCD(a, b) = 1 होता है, तो x (mod b) a का मॉड्यूलर व्युत्क्रम होता है।
if b = 0: return (a, 1, 0)
(g, x₁, y₁) = extGCD(b, a mod b)
return (g, y₁, x₁ - ⌊a/b⌋·y₁)
उदाहरण: 35 का व्युत्क्रम mod 3
extGCD(2, 3): → (1, -1, 1) क्योंकि 2×(-1) + 3×1 = 1
(-1 mod 3 + 3) mod 3 = 2 → व्युत्क्रम = 2
यह एल्गोरिथ्म अत्यंत तेज़ी से (O(log(min(a,b))) समय में) कार्य करता है — जो क्रिप्टोग्राफी में उपयोग किए जाने वाले बड़े मापांकों के लिए बहुत कुशल है।