चीनी शेष प्रमेय (The Chinese Remainder Theorem)

परिचय

संख्या सिद्धांत (Number Theory) में चीनी शेष प्रमेय (Chinese Remainder Theorem – CRT) एक अत्यंत महत्वपूर्ण सिद्धांत है, जो एक साथ कई समांग समीकरणों (Simultaneous Congruences) को हल करने की विधि प्रदान करता है। इस प्रमेय का उपयोग गणित, क्रिप्टोग्राफी, कंप्यूटर नेटवर्किंग, डेटा एनालिटिक्स, और कोडिंग थ्योरी में व्यापक रूप से किया जाता है।

CRT का उद्गम चीन के गणितज्ञ सन त्सू (Sun Tzu) के कार्यों से हुआ, जिन्होंने तीसरी शताब्दी ईस्वी में इस सिद्धांत का पहला रूप प्रस्तुत किया था। यह प्रमेय उन समस्याओं का समाधान देता है जहाँ किसी संख्या को विभिन्न मॉड्यूलस से विभाजित करने पर अलग-अलग शेषफल प्राप्त होते हैं।

प्रमेय का कथन

यदि n₁, n₂, n₃, …, nₖ ऐसी संख्याएँ हैं जो परस्पर सहाभाज्य (Pairwise Coprime) हैं, और:

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
x ≡ a₃ (mod n₃)
...
x ≡ aₖ (mod nₖ)

तो, एक अद्वितीय समाधान x मौजूद है जो इन सभी समीकरणों को संतुष्ट करता है और यह समाधान इस रूप में दिया जा सकता है:

x ≡ A (mod N)

जहाँ N = n₁ × n₂ × … × nₖ

समझने के लिए उदाहरण

मान लीजिए निम्न समांग समीकरण प्रणाली दी गई है:

x ≡ 2 (mod 3)
x ≡ 3 (mod 4)
x ≡ 2 (mod 5)

समाधान:

यहाँ n₁ = 3, n₂ = 4, n₃ = 5 अतः N = 3 × 4 × 5 = 60

अब प्रत्येक के लिए:

• N₁ = N/n₁ = 60/3 = 20
• N₂ = 60/4 = 15
• N₃ = 60/5 = 12

अब Modular Inverse खोजें:

• 20 × y₁ ≡ 1 (mod 3) ⇒ y₁ = 2
• 15 × y₂ ≡ 1 (mod 4) ⇒ y₂ = 3
• 12 × y₃ ≡ 1 (mod 5) ⇒ y₃ = 3

अब x = Σ (aᵢ × Nᵢ × yᵢ)

x = (2×20×2) + (3×15×3) + (2×12×3) = 80 + 135 + 72 = 287

x ≡ 287 mod 60 ⇒ x = 47

अतः समाधान है x ≡ 47 (mod 60).

प्रमेय का सार

चीनी शेष प्रमेय हमें बताता है कि यदि मॉड्यूलस परस्पर सहाभाज्य हैं, तो किसी भी सेट की समांग समीकरणों का एकल समाधान मौजूद होगा। यह समाधान संपूर्ण मॉड्यूलस के गुणनफल (N) के मॉड में अद्वितीय होता है।

एल्गोरिद्मिक दृष्टिकोण

1. सभी मॉड्यूलस n₁, n₂, …, nₖ को गुणा कर N निकालें।
2. प्रत्येक i के लिए Nᵢ = N / nᵢ निकालें।
3. प्रत्येक Nᵢ का Modular Inverse (yᵢ) निकालें।
4. अंत में x = Σ (aᵢ × Nᵢ × yᵢ) mod N।

प्रोग्रामिंग उदाहरण (Python)

def chinese_remainder(a, n):
    N = 1
    for ni in n:
        N *= ni
    result = 0
    for ai, ni in zip(a, n):
        Ni = N // ni
        yi = pow(Ni, -1, ni)
        result += ai * Ni * yi
    return result % N

a = [2, 3, 2]
n = [3, 4, 5]
print(chinese_remainder(a, n))  # Output: 47

गुणधर्म

• यदि सभी मॉड्यूलस सहाभाज्य हैं, तो समाधान अद्वितीय है।
• यदि मॉड्यूलस सहाभाज्य नहीं हैं, तो समाधान अस्तित्व में नहीं या अद्वितीय नहीं हो सकता।
• CRT का उपयोग बड़े संख्याओं के साथ तेज़ गणनाओं में होता है।

अनुप्रयोग

• क्रिप्टोग्राफी: RSA Algorithm में CRT का उपयोग Modular Exponentiation को तेज़ बनाने के लिए।
• डेटा एन्कोडिंग: डेटा को विभिन्न चैनलों में विभाजित कर पुनर्निर्माण करने के लिए।
• कंप्यूटर नेटवर्क: पैकेट ट्रैकिंग और Synchronization।
• डेटा साइंस: Parallel Computation और Matrix Mod Operations में।

वास्तविक जीवन उदाहरण

मान लीजिए किसी मशीन में तीन अलग-अलग सेंसर हैं जो अलग-अलग मॉड्यूलस के तहत माप देते हैं। CRT का उपयोग करके हम इन तीनों के आउटपुट को एकल, संगत डेटा मान में परिवर्तित कर सकते हैं, जिससे सिस्टम का समेकित परिणाम प्राप्त होता है।

निष्कर्ष

चीनी शेष प्रमेय संख्या सिद्धांत का एक अनमोल उपकरण है, जो कई जटिल समांग समीकरणों को सरल तरीके से हल करता है। यह गणना, एन्क्रिप्शन, और डेटा प्रोसेसिंग के क्षेत्र में दक्षता को बढ़ाता है। डेटा साइंस में CRT का प्रयोग मॉड्यूलर गणनाओं, समांतर प्रसंस्करण और गणनात्मक अनुकूलन के लिए किया जाता है।