चीनी शेषफल प्रमेय

सुन्ज़ी का मूल सूत्रीकरण: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) हल x = 23 + 105k, के साथ, k एक पूर्णांक के साथ

गणित में, चीनी शेषफल प्रमेय कहता है कि यदि कोई पूर्णांक n के यूक्लिडियन प्रभाग के शेषफल को कई पूर्णांकों द्वारा जानता है, तो वह n के गुणनफल द्वारा विशिष्ट रूप से विभाजन के शेष भाग को निर्धारित कर सकता है। ये पूर्णांक, इस प्रतिबन्ध के अंतर्गत कि भाजक युग्‍मानूसार सहअभाज्य हैं (1 के अतिरिक्त कोई भी दो भाजक सामान्य कारक साझा नहीं करते हैं)।

इस प्रकार से उदाहरण के लिए, यदि हम जानते हैं कि n को 3 से विभाजित करने पर शेषफल 2 है, n को 5 से विभाजित करने पर शेषफल 3 है, और n को 7 से विभाजित करने पर शेषफल 2 है, फिर n का मान जाने बिना, हम यह निर्धारित कर सकते हैं कि n को 105 (3, 5, और 7 का गुणनफल) से विभाजित करने पर शेषफल 23 है। महत्वपूर्ण रूप से, यह हमें बताता है कि यदि n 105 से कम प्राकृतिक संख्या है, तो 23 n का एकमात्र संभावित मान है।

अतः इस प्रकार से प्रमेय का सबसे पहला ज्ञात कथन चीनी गणितज्ञ सुन्ज़ी द्वारा तीसरी शताब्दी ई.पू. में सुन्ज़ी सुआन्ज्निन में दिया गया है।

चीनी शेषफल प्रमेय का व्यापक रूप से बड़े पूर्णांकों के साथ कंप्यूटिंग के लिए उपयोग किया जाता है, क्योंकि यह गणना को प्रतिस्थापित करने की अनुमति देता है जिसके लिए कई छोटे पूर्णांकों पर कई समान गणनाओं द्वारा परिणाम के आकार पर सीमा जानता है।

इस प्रकार से चीनी शेषफल प्रमेय (मॉड्यूलर अंकगणित सर्वांगसमता के संदर्भ में व्यक्त) प्रत्येक प्रमुख आदर्श डोमेन पर सत्य है। इसे किसी भी वलय (गणित) के लिए सामान्यीकृत किया गया है, जिसमें दो-पक्षीय आदर्श सम्मिलित हैं।

इतिहास

विशिष्ट संख्याओं की समस्या के रूप में प्रमेय का सबसे पहला ज्ञात कथन, चीनी गणितज्ञ सुन्ज़ी द्वारा तीसरी शताब्दी की पुस्तक सनज़ी सुआनजिंग में दिखाई देता है:

कुछ वस्तुएं ऐसी हैं जिनकी संख्या अज्ञात है। यदि हम उन्हें तीन से गिनें, तो हमारे निकट दो बचे हैं; पाँचों तक, हमारे निकट तीन बचे हैं; और सात बजते-बजते दो बच जाते हैं। कितनी वस्तुएं हैं?

इस प्रकार से सुन्ज़ी के कार्य में न तो कोई गणितीय प्रमाण है और न ही कोई पूर्ण एल्गोरिथम। इस समस्या को हल करने के लिए एल्गोरिदम कितना महत्वपूर्ण है इसका वर्णन आर्यभट्ट (छठी शताब्दी) ने किया था। चीनी शेषफल प्रमेय की विशेष स्थिति ब्रह्मगुप्त (7वीं शताब्दी) को भी ज्ञात थे, और फाइबोनैचि के अबेकस की पुस्तक (1202) में दिखाई देते हैं। परिणाम को बाद में किन जिउशाओ के 1247 गणितीय ग्रंथ में नौ खंडों में दा-यान-शू (大衍術) नामक पूर्ण हल के साथ सामान्यीकृत किया गया था, जिसका 19वीं शताब्दी के प्रारंभ में ब्रिटिश मिशनरी अलेक्जेंडर वाइली (मिशनरी) द्वारा अंग्रेजी में अनुवाद किया गया था।

चीनी शेषफल प्रमेय कार्ल फ्रेडरिक गॉस की 1801 की पुस्तक अंकगणितीय विवेचन में दिखाई देता है।

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

कथन

इस प्रकार से मान लीजिए n₁, ..., n_k 1 से बड़े पूर्णांक हैं, जिन्हें प्रायः मॉड्यूलर अंकगणित या यूक्लिडियन विभाजन कहा जाता है। आइए हम n_i के गुणनफल को N से निरूपित करें।

चीनी शेषफल प्रमेय का अनुरोध है कि यदि n_i युग्‍मानूसार सहअभाज्य हैं, और यदि a₁, ..., a_k ऐसे पूर्णांक हैं कि प्रत्येक i के लिए 0 ≤ a_i < n_i है, तो एक और मात्र एक पूर्णांक x है, जैसे कि 0 ≤ x < N और n_i द्वारा x के यूक्लिडियन विभाजन का शेष भाग प्रत्येक i के लिए a_i है।

इसे सर्वांगसमता के संदर्भ में इस प्रकार दोहराया जा सकता है: यदि $n_{i}$ युग्‍मानूसार सहअभाज्य हैं, और यदि a₁, ..., a_k कोई पूर्णांक हैं, तो पद्धति

${\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}$

का एक हल है, और कोई भी दो हल, मान लीजिए x₁ और x₂, सर्वांगसम मॉड्यूलो N हैं, अर्थात, x₁ ≡ x₂ (mod N )।

अमूर्त बीजगणित में, प्रमेय को प्रायः इस प्रकार दोहराया जाता है: यदि n_i युग्‍मानूसार सहअभाज्य है, तो प्रतिचित्र

$x{\bmod {N}}\;\mapsto \;(x{\bmod {n}}_{1},\,\ldots ,\,x{\bmod {n}}_{k})$

पूर्णांक मॉड्यूलो N की वलय और पूर्णांक मॉड्यूलो n_i के वलय के प्रत्यक्ष उत्पाद के बीच एक वलय समरूपता

$\mathbb {Z} /N\mathbb {Z} \cong \mathbb {Z} /n_{1}\mathbb {Z} \times \cdots \times \mathbb {Z} /n_{k}\mathbb {Z}$

को परिभाषित करता है। इसका अर्थ यह है कि $\mathbb {Z} /N\mathbb {Z}$ में अंकगणितीय संक्रियाओं का अनुक्रम करने के लिए प्रत्येक $\mathbb {Z} /n_{i}\mathbb {Z}$ में स्वतंत्र रूप से समान गणना कर सकता है और फिर समरूपता (दाएं से बाएं) को लागू करके परिणाम प्राप्त कर सकता है। इस प्रकार से यदि n और ऑपरेशन की संख्या बड़ी है तो यह प्रत्यक्ष गणना से कहीं अधिक तीव्र हो सकती है। पूर्णांकों या परिमेय संख्याओं पर रैखिक बीजगणित के लिए, बहु-मॉड्यूलर गणना नाम के अंतर्गत इसका व्यापक रूप से उपयोग किया जाता है।

इस प्रकार से प्रमेय को साहचर्य की भाषा में इस तथ्य के रूप में भी दोहराया जा सकता है कि पूर्णांकों की अनंत अंकगणितीय प्रगति हेली वर्ग बनाती है।

प्रमाण

अतः हल का अस्तित्व और विशिष्टता स्वतंत्र रूप से सिद्ध की जा सकती है। यद्यपि, नीचे दिया गया अस्तित्व का पहला प्रमाण, इस विशिष्टता का उपयोग करता है।

अद्वितीयता

मान लीजिए कि x और y दोनों सभी सर्वांगसमताओं के हल हैं। चूंकि x और y समान शेषफल देते हैं, जब n_i से विभाजित किया जाता है, तो उनका अंतर x - y प्रत्येक n_i का गुणज होता है। चूँकि n_i युग्‍मानूसार सहअभाज्य हैं, उनका गुणनफल N भी x - y को विभाजित करता है, और इस प्रकार x और y सर्वांगसम मॉड्यूलो N हैं। इस प्रकार से यदि x और y को गैर-ऋणात्मक और N से कम माना जाता है (जैसा कि प्रमेय के पहले कथन में है), तो उनका अंतर मात्र N का गुणज हो सकता है यदि x = y हो।

अस्तित्व (प्रथम प्रमाण)

अतः प्रतिचित्र

$x{\bmod {N}}\mapsto (x{\bmod {n}}_{1},\ldots ,x{\bmod {n}}_{k})$

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

यह प्रमाण बहुत सरल है परन्तु हल की गणना के लिए कोई प्रत्यक्ष विधि प्रदान नहीं करती है। इसके अतिरिक्त, इसे अन्य स्थितियों के लिए सामान्यीकृत नहीं किया जा सकता है जहां निम्नलिखित प्रमाण हो सकते हैं।

अस्तित्व (रचनात्मक प्रमाण)

अतः x के स्पष्ट निर्माण द्वारा अस्तित्व स्थापित किया जा सकता है। इस निर्माण को दो चरणों में विभाजित किया जा सकता है, पहले दो मॉड्यूल के स्थिति में समस्या को हल करना, और फिर इस हल को मॉड्यूल की संख्या पर गणितीय प्रेरण द्वारा सामान्य स्थिति में विस्तारित करना।

दो मॉड्यूल का स्थिति

इस प्रकार से हम पद्धति को हल करना चाहते हैं:

${\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}$

जहाँ $n_{1}$ और $n_{2}$ सहअभाज्य हैं।

बेज़ाउट की समरूपता दो पूर्णांकों $m_{1}$ और $m_{2}$ के अस्तित्व का अनुरोध करती है जैसे कि

$m_{1}n_{1}+m_{2}n_{2}=1.$

पूर्णांक $m_{1}$ और $m_{2}$ विस्तारित यूक्लिडियन एल्गोरिदम द्वारा गणना की जा सकती है।

एक हल

$x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}$ द्वारा दिया गया है।

वस्तुतः,

${\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}$

का तात्पर्य यह है कि $x\equiv a_{1}{\pmod {n_{1}}}.$ दूसरी सर्वांगसमता इसी प्रकार उपस्क्रिप्ट 1 और 2 के आदान-प्रदान से सिद्ध होती है।

सामान्य स्थिति

इस प्रकार से सर्वांगसम समीकरणों के अनुक्रम पर विचार करें:

${\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}$

जहां $n_{i}$ युग्‍मानूसार सहअभाज्य हैं। पहले दो समीकरणों का हल $a_{1,2}$ है जो पूर्व अनुभाग की विधि द्वारा प्रदान किया गया है। इन दो प्रथम समीकरणों के हलों का समुच्चय समीकरण

$x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}$ के सभी हलों का समुच्चय है।

चूँकि अन्य $n_{i}$, $n_{1}n_{2},$ के साथ सहअभाज्य हैं, इससे k समीकरणों की प्रारंभिक समस्या का हल k-1 समीकरणों के समान समस्या में बदल जाता है। प्रक्रिया को दोहराते रहने से अंततः प्रारंभिक समस्या का हल मिल जाता है।

अस्तित्व (प्रत्यक्ष निर्माण)

किसी हल के निर्माण के लिए, मॉड्यूल की संख्या पर प्रेरण बनाना आवश्यक नहीं है। यद्यपि, इस प्रकार के प्रत्यक्ष निर्माण में बड़ी संख्याओं के साथ अधिक गणना सम्मिलित होती है, जो इसे कम कुशल और कम उपयोग में लाती है। फिर भी, लैग्रेंज अंतःक्षेप इस निर्माण की विशेष स्थिति है, जो पूर्णांकों के अतिरिक्त बहुपदों पर लागू होता है।

इस प्रकार से मान लीजिए कि $N_{i}=N/n_{i}$ एक को छोड़कर सभी मॉड्यूल का उत्पाद है। चूँकि $n_{i}$ युग्‍मानूसार सहअभाज्य हैं, $N_{i}$ और $n_{i}$ सहअभाज्य हैं। इस प्रकार बेज़ाउट की समरूपता लागू होती है, और ऐसे पूर्णांक $M_{i}$ और $m_{i}$ स्थित होते हैं जैसे

$M_{i}N_{i}+m_{i}n_{i}=1.$

सर्वांगसमता प्रणाली का एक हल

$x=\sum _{i=1}^{k}a_{i}M_{i}N_{i}$ है।

वस्तुतः, चूंकि $N_{j}$ $i\neq j,$ के लिए $n_{i}$ का गुणज है, इसलिए हमारे निकट प्रत्येक $i$ के लिए

$x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},$

है।

गणना

इस प्रकार से सर्वांगसमताओं की प्रणाली पर विचार करें:

${\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\\\end{aligned}}$

जहां $n_{i}$ युग्‍मानूसार सहअभाज्य हैं, और मान लीजिए $N=n_{1}n_{2}\cdots n_{k}.$ इस अनुभाग में $x$ के लिए अद्वितीय हल की गणना करने के लिए कई विधियों का वर्णन किया गया है, जैसे कि $0\leq x<N,$ और इन विधियों को उदाहरण

${\begin{aligned}x&\equiv 0{\pmod {3}}\\x&\equiv 3{\pmod {4}}\\x&\equiv 4{\pmod {5}}\end{aligned}}$ पर लागू किया जाता है।

गणना की अनेक विधियाँ प्रस्तुत हैं। पहले दो छोटे उदाहरणों के लिए उपयोगी हैं, परन्तु उत्पाद $n_{1}\cdots n_{k}$ बड़ा होने पर बहुत अक्षम हो जाते हैं। तीसरा § अस्तित्व (रचनात्मक प्रमाण) में दिए गए अस्तित्व प्रमाण का उपयोग करता है। जब उत्पाद $n_{1}\cdots n_{k}$ बड़ा हो, या कंप्यूटर गणना के लिए यह सबसे सुविधाजनक है।

सिस्टेमेटिक सर्च

यह जांचना सरल है कि क्या x का मान एक हल है: यह प्रत्येक n_i द्वारा x के यूक्लिडियन विभाजन के शेष की गणना करने के लिए पर्याप्त है। इस प्रकार, हल सर्च करने के लिए, हल सर्च करने तक 0 से N तक के पूर्णांकों की क्रमिक रूप से जाँच करना पर्याप्त है।

यद्यपि यह विधि बहुत सरल है, फिर भी यह बहुत अप्रभावी है। यहां पर विचार किए गए सरल इस प्रकार से उदाहरण के लिए, हल सर्चने के लिए 40 पूर्णांक (0 सहित) की जांच करनी होगी, जो कि 39 है। यह एक घातीय समय एल्गोरिदम है, क्योंकि इनपुट का आकार, एक स्थिर कारक तक, N के अंकों की संख्या है, और ऑपरेशन की औसत संख्या N के क्रम की है।

इसलिए, इस पद्धति का उपयोग सम्भवतः कभी किया जाता है, न तो हस्तलिखित गणना के लिए और न ही कंप्यूटर पर।

सिएविंग सर्च

चीनी शेषफल प्रमेय समस्या के मूल सूत्रीकरण के सबसे छोटे दो हल, 23 और 128, सिएविंग का उपयोग करके पाए गए

सिएविंग से हल की सर्च नाटकीय रूप से तीव्र हो सकती है। इस पद्धति के लिए, हम मानते हैं, व्यापकता की हानि के बिना, वह $0\leq a_{i}<n_{i}$ (यदि ऐसा नहीं होता, तो प्रत्येक $a_{i}$ को उसके विभाजन के शेष भाग द्वारा $n_{i}$से प्रतिस्थापित करना पर्याप्त होगा)। इसका तात्पर्य यह है कि हल अंकगणितीय प्रगति

$a_{1},a_{1}+n_{1},a_{1}+2n_{1},\ldots$ से संबंधित है।

इन संख्याओं मॉड्यूलो $n_{2}$ के मानों का परीक्षण करके, किसी संख्या को अंततः दो प्रथम सर्वांगसमताओं का एक हल $x_{2}$ मिल जाता है। तब हल अंकगणितीय प्रगति

$x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots$ से संबंधित है।

इन संख्याओं मॉड्यूल $n_{3}$ के मानों का परीक्षण करना, और तब तक जारी रखना जब तक कि प्रत्येक मॉड्यूल का परीक्षण नहीं हो जाता, अंततः हल मिल जाता है।

इस प्रकार से यदि मॉड्यूली को घटते मान के अनुसार क्रमबद्ध किया गया है, तो यह विधि तीव्र है, अर्थात $n_{1}>n_{2}>\cdots >n_{k}.$ इस प्रकार से उदाहरण के लिए, यह निम्नलिखित गणना देता है। हम पहले उन संख्याओं पर विचार करते हैं जो 4 मॉड्यूल 5 (सबसे बड़ा मॉड्यूल) के अनुरूप हैं, जो 4, 9 = 4 + 5, 14 = 9 + 5, ... हैं। उनमें से प्रत्येक के लिए, 3 मॉड्यूल 4 के अनुरूप संख्या प्राप्त होने तक शेषफल की गणना 4 (दूसरा सबसे बड़ा मापांक) से करें। फिर प्रत्येक चरण में 20 = 5 × 4 जोड़कर और केवल 3 द्वारा शेषफल की गणना करके आगे बढ़ सकता है। यह देता

4 मॉड 4 → 0। जारी

4 + 5 = 9 मॉड 4 →1। जारी

9 + 5 = 14 मॉड 4 → 2। जारी

14 + 5 = 19 मॉड 4 → 3। ठीक है, शेष मॉड्यूल 3 पर विचार करके और प्रत्येक बार 5 × 4 = 20 जोड़कर जारी रखें

19 मॉड 3 → 1। जारी

19 + 20 = 39 मॉड 3 → 0। ठीक है, यह परिणाम है।

अतः यह विधि मॉड्यूल के उत्पाद के साथ हस्तलिखित गणना के लिए ठीक रूप से कार्य करती है जो बहुत बड़ी नहीं है। यद्यपि, मॉड्यूली के बहुत बड़े उत्पादों के लिए यह अन्य विधियों की तुलना में बहुत मंद है। यद्यपि सिस्टेमेटिक सर्च की तुलना में नाटकीय रूप से तीव्र, इस पद्धति में घातीय समय जटिलता भी है और इसलिए इसका उपयोग कंप्यूटर पर नहीं किया जाता है।

अस्तित्व निर्माण का उपयोग करना

1. रचनात्मक अस्तित्व प्रमाण से पता चलता है कि, दो मॉड्यूल की स्थिति में, हल मॉड्यूल के बेज़आउट गुणांक की गणना द्वारा प्राप्त किया जा सकता है, इसके बाद कुछ गुणा, जोड़ और कटौती मॉड्यूल $n_{1}n_{2}$(अंतराल $(0,n_{1}n_{2}-1)$ में परिणाम प्राप्त करने के लिए) किया जा सकता है। चूँकि बेज़आउट के गुणांकों की गणना विस्तारित यूक्लिडियन एल्गोरिदम के साथ की जा सकती है, संपूर्ण गणना में, अधिकतम, $O((s_{1}+s_{2})^{2})$ की द्विघात समय जटिलता होती है, जहाँ $s_{i}$ $n_{i}$ के अंकों की संख्या को दर्शाता है।

इस प्रकार से दो से अधिक मॉड्यूल के लिए, दो मॉड्यूल के लिए विधि मॉड्यूल के उत्पाद को एकल सर्वांगसम मॉड्यूल द्वारा किन्हीं दो सर्वांगसमताओं के प्रतिस्थापन की अनुमति देती है। इस प्रक्रिया को दोहराने से अंततः जटिलता के साथ हल मिलता है, जो सभी मॉड्यूल के उत्पाद के अंकों की संख्या में द्विघात है। यह द्विघात समय जटिलता उस क्रम पर निर्भर नहीं करती है जिसमें मॉड्यूल को पुन: समूहित किया जाता है। कोई पहले दो मापांकों को पुन: समूहित कर सकता है, फिर परिणामी मापांक को अगले मापांक के साथ पुन: समूहित कर सकता है, इत्यादि। इस कार्यनीति को लागू करना सबसे सरल है, परन्तु इसमें बड़ी संख्याओं को सम्मिलित करते हुए अधिक गणना की भी आवश्यकता होती है।

इस प्रकार से एक अन्य कार्यनीति में मॉड्यूल को उन जोड़ियों में विभाजित करना सम्मिलित है जिनके उत्पाद का आकार तुलनीय है (जितना संभव हो), समानांतर में, प्रत्येक युग्म के लिए दो मॉड्यूल की विधि को लागू करना, और कई मॉड्यूल को लगभग दो से विभाजित करके पुनरावृत्त करना है। यह विधि एल्गोरिथम के सरल समानांतरकरण की अनुमति देती है। इसके अतिरिक्त, यदि मूलभूत ऑपरेशन के लिए तीव्र एल्गोरिदम (अर्थात, चतुर्रेखीय समय में कार्य करने वाले एल्गोरिदम) का उपयोग किया जाता है, तो यह विधि संपूर्ण गणना के लिए एल्गोरिदम प्रदान करती है जो रैखिककल्प समय में कार्य करती है।

इस प्रकार से वर्तमान उदाहरण पर (जिसमें मात्र तीन मॉड्यूल हैं), दोनों कार्यनीतियाँ समान हैं और निम्नानुसार कार्य करती हैं।

3 और 4 के लिए बेज़ाउट की समरूपता

$1\times 4+(-1)\times 3=1$ है।

अस्तित्व को सिद्ध करने के लिए दिए गए सूत्र में इसे डालने पर दो पहली सर्वांगसमताओं के हल के लिए

$0\times 1\times 4+3\times (-1)\times 3=-9$

मिलता है, अन्य हल −9 में 3 × 4 = 12 के किसी भी गुणज को जोड़कर प्राप्त किया जा सकता है। इनमें से कोई भी हल जारी रखा जा सकता है, परन्तु हल 3 = −9 +12 छोटा है (पूर्ण मान में) और इस प्रकार संभवतः आसान गणना की ओर ले जाता है

5 और 3 × 4 = 12 के लिए बेज़आउट समरूपता

$5\times 5+(-2)\times 12=1$ है।

इस प्रकार से उसी सूत्र को दोबारा लागू करने पर, हमें समस्या का हल मिलता है:

$5\times 5\times 3+12\times (-2)\times 4=-21.$

अतः अन्य हल 3 × 4 × 5 = 60 में से किसी भी गुणज को जोड़कर प्राप्त किए जाते हैं, और सबसे छोटा धनात्मक हल −21 + 60 = 39 है।

एक रैखिक डायोफैंटाइन प्रणाली के रूप में

चीनी शेषफल प्रमेय द्वारा हल की गई सर्वांगसमताओं की प्रणाली को डायोफैंटाइन समीकरण रैखिक डायोफैंटाइन समीकरणों की प्रणाली के रूप में फिर से लिखा जा सकता है:

${\begin{aligned}x&=a_{1}+x_{1}n_{1}\\&\vdots \\x&=a_{k}+x_{k}n_{k},\end{aligned}}$

जहां अज्ञात पूर्णांक $x$ और $x_{i}$ हैं। इसलिए, ऐसी प्रणालियों को हल करने के लिए प्रत्येक सामान्य विधि का उपयोग चीनी शेषफल प्रमेय का हल सर्च करने के लिए किया जा सकता है, जैसे कि पद्धति के आव्यूह (गणित) को स्मिथ सामान्य रूप या हर्मिट सामान्य रूप में कम करना। यद्यपि, सदैव के जैसे अधिक विशिष्ट समस्या के लिए सामान्य एल्गोरिदम का उपयोग करते समय, यह दृष्टिकोण बेज़ाउट की समरूपता के प्रत्यक्ष उपयोग के आधार पर, पूर्व अनुभाग की विधि की तुलना में कम कुशल है।

प्रमुख आदर्श डोमेन पर

इस प्रकार से § कथन में, चीनी शेषफल प्रमेय को तीन अलग-अलग विधियों से कहा गया है: शेषफल के संदर्भ में, सर्वांगसमता के संदर्भ में, और वलय समरूपता के संदर्भ में। शेषफलों के संदर्भ में कथन, सामान्यतः, प्रमुख आदर्श डोमेन पर लागू नहीं होता है, क्योंकि शेषफलों को ऐसे वलय (गणित) में परिभाषित नहीं किया जाता है। यद्यपि, दो अन्य संस्करण एक प्रमुख आदर्श डोमेन R पर अर्थ रखते हैं: यह "पूर्णांक" को "डोमेन के अवयव" और $\mathbb {Z}$ को R से बदलने के लिए पर्याप्त है। प्रमेय के ये दो संस्करण इस संदर्भ में सत्य हैं, क्योंकि प्रमाण (पहले अस्तित्व प्रमाण को छोड़कर), यूक्लिड की लेम्मा और बेज़ाउट की समरूपता पर आधारित हैं, जो प्रत्येक प्रमुख डोमेन पर सत्य हैं।

यद्यपि, सामान्यतः, प्रमेय मात्र अस्तित्व प्रमेय है और हल की गणना के लिए कोई विधि प्रदान नहीं करता है, जब तक कि किसी के निकट बेज़ाउट की समरूपता के गुणांक की गणना के लिए एल्गोरिदम न हो।

एकविभिन्न बहुपद वलय और यूक्लिडियन डोमेन पर

इस प्रकार से § प्रमेय कथन में दिए गए शेषफलों के संदर्भ में कथन को किसी भी प्रमुख आदर्श डोमेन के लिए सामान्यीकृत नहीं किया जा सकता है, परन्तु यूक्लिडियन डोमेन के लिए इसका सामान्यीकरण प्रत्यक्ष है। क्षेत्र (गणित) पर अविभाज्य बहुपद यूक्लिडियन डोमेन का विशिष्ट उदाहरण है जो पूर्णांक नहीं है। इसलिए, हम क्षेत्र $K$ के लिए वलय $R=K[X]$ की स्थिति के लिए प्रमेय बताते हैं। सामान्य यूक्लिडियन डोमेन के लिए प्रमेय प्राप्त करने के लिए, यूक्लिडियन डोमेन के यूक्लिडियन फलन द्वारा बहुपद की घात को प्रतिस्थापित करना पर्याप्त है।

यह बहुपदों के लिए चीनी शेषफल प्रमेय इस प्रकार है: मान लीजिए $P_{i}(X)$ (मॉड्यूली), $i=1,\dots ,k$ के लिए, $R=K[X]$ में युग्‍मानूसार सहअभाज्य बहुपद है।मान लीजिए कि $d_{i}=\deg P_{i}$ (मापांक) है, $P_{i}(X)$की घात है, और $D$ $d_{i}$ का योग है। यदि $A_{i}(X),\ldots ,A_{k}(X)$ ऐसे बहुपद हैं कि $A_{i}(X)=0$ या $\deg A_{i}<d_{i}$ प्रत्येक i के लिए, तो, एक और केवल एक बहुपद $P(X)$ है, जैसे कि $\deg P<D$ और $P(X)$ का $P_{i}(X)$ द्वारा यूक्लिडियन विभाजन का शेष प्रत्येक i के लिए $A_{i}(X)$ है।

हल का निर्माण § अस्तित्व (रचनात्मक प्रमाण) या § अस्तित्व (प्रत्यक्ष प्रमाण) के रूप में किया जा सकता है। यद्यपि, बाद के निर्माण को विस्तारित यूक्लिडियन एल्गोरिदम के अतिरिक्त आंशिक अंश अपघटन का उपयोग करके सरल बनाया जा सकता है।

इस प्रकार, हम एक बहुपद $P(X)$ सर्च करना चाहते हैं, जो

$P(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},$

के लिए सर्वांगसमताओं $i=1,\ldots ,k$ को संतुष्ट करता है। बहुपद

${\begin{aligned}Q(X)&=\prod _{i=1}^{k}P_{i}(X)\\Q_{i}(X)&={\frac {Q(X)}{P_{i}(X)}}\end{aligned}}$ पर विचार करें।

इस प्रकार से $1/Q(X)$ का आंशिक अंश अपघटन k बहुपद $S_{i}(X)$ को घात $\deg S_{i}(X)<d_{i}$ के साथ देता है, जैसे कि

${\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {S_{i}(X)}{P_{i}(X)}},$

और इस प्रकार

$1=\sum _{i=1}^{k}S_{i}(X)Q_{i}(X).$

फिर बहुपद

$\sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X)$ द्वारा एक साथ सर्वांगसमता प्रणाली का हल दिया जाता है।

वस्तुतः, हमारे निकट $1\leq i\leq k$ के लिए

$\sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X)=A_{i}(X)+\sum _{j=1}^{k}(A_{j}(X)-A_{i}(X))S_{j}(X)Q_{j}(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},$

है।

इस प्रकार से इस हल की घात $D=\sum _{i=1}^{k}d_{i}$ से अधिक हो सकती है। $D$ से कम घात का अद्वितीय हल $A_{i}(X)S_{i}(X)$ के $P_{i}(X)$ के यूक्लिडियन विभाजन के शेष $B_{i}(X)$ पर विचार करके निकाला जा सकता है। यह हल

$P(X)=\sum _{i=1}^{k}B_{i}(X)Q_{i}(X)$ है।

लैग्रेंज अंतःक्षेप

अतः इस प्रकार से बहुपदों के लिए चीनी शेषफल प्रमेय का विशेष स्थिति लैग्रेंज अंतःक्षेप है। इसके लिए, डिग्री एक के k मोनिक बहुपदों पर विचार करें:

$P_{i}(X)=X-x_{i}.$

यदि $x_{i}$ सभी भिन्न हैं तो वे युग्‍मानूसार सहअभाज्य हैं। बहुपद $P(X)$ के $P_{i}(X)$ विभाजन का शेषफल, बहुपद शेषफल प्रमेय द्वारा $P(x_{i})$ है।

अब, मान लीजिए कि $K$ में $A_{1},\ldots ,A_{k}$ स्थिरांक (घात 0 वाले बहुपद) है। लैग्रेंज अंतःक्षेप और चीनी शेषफल प्रमेय दोनों एक अद्वितीय बहुपद $P(X)$ के अस्तित्व पर बल देते हैं, जिसकी घात $k$ से कम है, जैसे कि प्रत्येक $i$ के लिए

$P(x_{i})=A_{i}$।

लैग्रेंज अंतःक्षेप सूत्र, इस स्थिति में, हल के उपरोक्त निर्माण का निश्चित परिणाम है। अधिक यथार्थ रूप से, मान लीजिए

${\begin{aligned}Q(X)&=\prod _{i=1}^{k}(X-x_{i})\\[6pt]Q_{i}(X)&={\frac {Q(X)}{X-x_{i}}}.\end{aligned}}$

${\frac {1}{Q(X)}}$ का आंशिक अंश अपघटन

${\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}$ है।

वस्तुतः, दायीं ओर को एक सामान्य हर में घटाने से

$\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}={\frac {1}{Q(X)}}\sum _{i=1}^{k}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}}$

प्राप्त होता है, और अंश एक के बराबर होता है, क्योंकि यह $k$ से कम घात वाला बहुपद है, जो $X$ के विभिन्न मानों $k$ के लिए एक मान लेता है।

उपरोक्त सामान्य सूत्र का उपयोग करते हुए, हमें लैग्रेंज अंतःक्षेप सूत्र प्राप्त होता है:

$P(X)=\sum _{i=1}^{k}A_{i}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}}.$

हर्मिट ट्वीन

इस प्रकार से हर्माइट अंतःक्षेप, अविभाज्य बहुपदों के लिए चीनी शेष प्रमेय का अनुप्रयोग है, जिसमें यादृच्छिक घात के मॉड्यूल सम्मिलित हो सकते हैं (लैग्रेंज अंतःक्षेप में मात्र घात का मॉड्यूल सम्मिलित होता है)।

समस्या में न्यूनतम संभव घात का बहुपद ढूंढना सम्मिलित है, जैसे कि बहुपद और उसके पहले व्युत्पन्न कुछ निश्चित बिंदुओं पर दिए गए मान लेते हैं।

अधिक यथार्थ रूप से, मान लीजिए कि $x_{1},\ldots ,x_{k}$ आधार क्षेत्र $K$ का $k$ अवयव है, और, $i=1,\ldots ,k$ के लिए मान लीजिए कि $a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}$, $x_{i}$ पर मांगे गए बहुपद के पहले $r_{i}$ व्युत्पन्नों का मान है (0वें व्युत्पन्न सहित, जो स्वयं बहुपद का मान है)। समस्या एक बहुपद $P(X)$ को इस प्रकार खोजना है कि इसका j th अवकलज $i=1,\ldots ,k$ और $j=0,\ldots ,r_{j}$ के लिए $x_{i}$ पर मान $a_{i,j}$ ले। बहुपद

$P_{i}(X)=\sum _{j=0}^{r_{i}-1}{\frac {a_{i,j}}{j!}}(X-x_{i})^{j}$ पर विचार करें।

यह अज्ञात बहुपद $P(X)$ का $x_{i}$ क्रम $r_{i}-1$ का टेलर बहुपद है। इसलिए, हमारे निकट

$P(X)\equiv P_{i}(X){\pmod {(X-x_{i})^{r_{i}}}}$ होना चाहिए।

इसके विपरीत, कोई भी बहुपद $P(X)$ जो इन $k$ सर्वांगसमताओं को संतुष्ट करता है, विशेष रूप से किसी भी $i=1,\ldots ,k$

$P(X)=P_{i}(X)+o(X-x_{i})^{r_{i}-1}$

के लिए सत्यापित करता है, इसलिए $P_{i}(X)$ $x_{i}$ पर क्रम $r_{i}-1$ का टेलर बहुपद है, अर्थात, $P(X)$ प्रारंभिक हर्मिट अंतःक्षेप समस्या को हल करता है।

चीनी शेषफल प्रमेय का अनुरोध है कि $r_{i}$ के योग से कम घात वाला एक बहुपद स्थित है, जो इन $k$ सर्वांगसमताओं को संतुष्ट करता है।

हल $P(X)$ की गणना करने के कई विधि हैं। कोई § एकचर पर बहुपद वलयों और यूक्लिडियन डोमेन के प्रारंभ में वर्णित विधि का उपयोग कर सकता है। कोई § अस्तित्व (रचनात्मक प्रमाण) या § अस्तित्व (प्रत्यक्ष प्रमाण) में दिए गए निर्माणों का भी उपयोग कर सकता है।

गैर-सह अभाज्य मॉड्यूल का सामान्यीकरण

चीनी शेषफल प्रमेय को गैर-सह अभाज्य मॉड्यूली के लिए सामान्यीकृत किया जा सकता है। इस प्रकार से मान लीजिए कि $m,n,a,b$ कोई पूर्णांक है, मान लीजिए$g=\gcd(m,n)$ है; $M=\operatorname {lcm} (m,n)$, और सर्वांगसमता प्रणाली पर विचार करें:

${\begin{aligned}x&\equiv a{\pmod {m}}\\x&\equiv b{\pmod {n}},\end{aligned}}$

यदि $a\equiv b{\pmod {g}}$ है, तो इस प्रणाली का एक अद्वितीय हल $M=mn/g$ है। अन्यथा, इसका कोई हल नहीं है।

अतः यदि कोई $g=um+vn$ लिखने के लिए बेज़आउट की पहचान का उपयोग करता है, तो हल

$x={\frac {avn+bum}{g}}$ द्वारा दिया जाता है।

यह इस प्रकार से एक पूर्णांक को परिभाषित करता है, क्योंकि g, m और n दोनों को विभाजित करता है। अन्यथा, प्रमाण सह अभाज्य मॉड्यूली के समान ही है।

यादृच्छिक वलयों का सामान्यीकरण

चीनी शेषफल प्रमेय को सह अभाज्य पूर्णांक आदर्शों (जिसे सह अधिकतम आदर्श (वलय सिद्धांत) भी कहा जाता है) का उपयोग करके, किसी भी वलय में सामान्यीकृत किया जा सकता है। यदि ऐसे अवयव $i\in I$ और $j\in J$ हैं कि $i+j=1$ तो आदर्श I और J सहअभाज्य हैं। यह संबंध इस सामान्यीकरण से संबंधित प्रमाणों में बेज़ाउट की समरूपता की भूमिका निभाता है, जो अन्यथा बहुत समान हैं। सामान्यीकरण इस प्रकार बताया जा सकता है।

मान लीजिए कि I₁, ..., I_k एक वलय $R$ के दो-पक्षीय आदर्श हैं और I उनका प्रतिच्छेदन (समुच्चय सिद्धांत) है। इस प्रकार से यदि आदर्श युग्‍मानूसार सहअभाज्य हैं, तो हमारे निकट वलय समरूपता है:

भागफल वलय $R/I$ और $R/I_{i}$ के प्रत्यक्ष उत्पाद के बीच

${\begin{aligned}R/I&\to (R/I_{1})\times \cdots \times (R/I_{k})\\x{\bmod {I}}&\mapsto (x{\bmod {I}}_{1},\,\ldots ,\,x{\bmod {I}}_{k}),\end{aligned}}$

जहां $x{\bmod {I}}$आदर्श I द्वारा परिभाषित भागफल वलय में अवयव x के प्रतिबिम्ब (गणित) को दर्शाता है। इसके अतिरिक्त, यदि $R$ क्रमविनिमेय वलय है, तो युग्‍मानूसार सहअभाज्य आदर्शों का आदर्श प्रतिच्छेदन उनके उत्पाद के बराबर है; अर्थात

$I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{k},$

है यदि I_i और I_j सभी i ≠ j के लिए सहअभाज्य हैं।

इडेम्पोटेंट के संदर्भ में व्याख्या

मान लीजिए कि $I_{1},I_{2},\dots ,I_{k}$, $\bigcap _{i=1}^{k}I_{i}=0$ के साथ युग्‍मानूसार सह अभाज्य दोपक्षीय आदर्श है, और

$\varphi :R\to (R/I_{1})\times \cdots \times (R/I_{k})$

पर परिभाषित समरूपता है। मान लीजिए कि $f_{i}=(0,\ldots ,1,\ldots ,0)$, $(R/I_{1})\times \cdots \times (R/I_{k})$ का अवयव है जिसके घटक i वें को छोड़कर सभी 0 हैं जो कि 1 है, और $e_{i}=\varphi ^{-1}(f_{i})$ पर परिभाषित समरूपता है।

$e_{i}$ h> केंद्रीय निष्क्रिय हैं जो युग्‍मानूसार केंद्रीय निष्क्रिय हैं; इसका अर्थ है, विशेष रूप से, प्रत्येक i और j के लिए $e_{i}^{2}=e_{i}$ और $e_{i}e_{j}=e_{j}e_{i}=0$। इसके अतिरिक्त, किसी के निकट ${\textstyle e_{1}+\cdots +e_{n}=1,}$ और $I_{i}=R(1-e_{i})$ है।

इस प्रकार से संक्षेप में, यह सामान्यीकृत चीनी शेषफल प्रमेय शून्य प्रतिच्छेदन के साथ युग्‍मानूसार सहअभाज्य दो-पक्षीय आदर्श देने और केंद्रीय और युग्‍मानूसार लाम्बिक इडेम्पोटेंट देने के बीच समानता है जिसका योग 1 है।

अनुप्रयोग

अनुक्रम क्रमांकन

इस प्रकार से चीनी शेषफल प्रमेय का उपयोग अनुक्रमों के लिए गोडेल क्रमांकन के निर्माण के लिए किया गया है, जो गोडेल की अपूर्णता प्रमेयों के प्रमाण में सम्मिलित है।

फास्ट फूरियर रूपांतरण

अतः अभाज्य-कारक एफएफटी एल्गोरिदम (जिसे गुड-थॉमस एल्गोरिदम भी कहा जाता है) आकार $n_{1}n_{2}$ के तीव्र फूरियर रूपांतरण की गणना को कम करने के लिए चीनी शेष प्रमेय का उपयोग छोटे आकार $n_{1}$ और $n_{2}$ के दो तीव्र फूरियर रूपांतरण की गणना के लिए करता है (यद्यपि $n_{1}$ और $n_{2}$ सहअभाज्य हैं)।

एन्क्रिप्शन

अधिकांश आरएसए (क्रिप्टोपद्धति) एचटीटीपीएस प्रमाणपत्रों पर हस्ताक्षर करने और डिक्रिप्शन के समय चीनी शेष एल्गोरिदम का उपयोग करना।

चीनी शेषफल प्रमेय का उपयोग गुप्त साझाकरण में भी किया जा सकता है, जिसमें शेयरों का समुच्चय लोगों के समूह के बीच वितरित करना सम्मिलित है, जो सभी साथ (परन्तु कोई भी अकेला नहीं), शेयरों के दिए गए समुच्चय से निश्चित गोपनीयता पुनर्प्राप्त कर सकते हैं। प्रत्येक शेयर को सर्वांगसमता में दर्शाया गया है, और चीनी शेषफल प्रमेय का उपयोग करके सर्वांगसमता प्रणाली का हल पुनर्प्राप्त किया जाने वाला गोपनीय है। चीनी शेषफल प्रमेय का उपयोग करते हुए गुप्त साझाकरण, चीनी शेषफल प्रमेय के साथ, पूर्णांकों के विशेष अनुक्रमों का उपयोग करता है जो निश्चित प्रमुखता से कम वाले शेयरों के समुच्चय से गोपनीयता को पुनर्प्राप्त करने की असंभवता की गारंटी देता है।

सीमा अस्पष्टता विभेदन

Main article: सीमा अस्पष्टता विभेदन

इस प्रकार से मध्यम स्पंद पुनरावृत्ति आवृत्ति रडार के साथ उपयोग की जाने वाले क्षेत्र अस्पष्टता विभेदन तकनीकों को चीनी शेषफल प्रमेय के विशेष स्थिति के रूप में देखा जा सकता है।

परिमित एबेलियन समूहों के अनुमानों का अपघटन

अतः परिमित एबेलियन समूहों के अनुमान विशेषण फलन $\mathbb {Z} /n\to \mathbb {Z} /m$ को देखते हुए, हम ऐसे किसी भी प्रतिचित्र का पूर्ण विवरण देने के लिए चीनी शेषफल प्रमेय का उपयोग कर सकते हैं। सबसे पहले, प्रमेय समरूपताएँ

${\begin{aligned}\mathbb {Z} /n&\cong \mathbb {Z} /p_{n_{1}}^{a_{1}}\times \cdots \times \mathbb {Z} /p_{n_{i}}^{a_{i}}\\\mathbb {Z} /m&\cong \mathbb {Z} /p_{m_{1}}^{b_{1}}\times \cdots \times \mathbb {Z} /p_{m_{j}}^{b_{j}}\end{aligned}}$

जहाँ $\{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{p_{n_{1}},\ldots ,p_{n_{i}}\}$ देता है। इसके अतिरिक्त, किसी भी प्रेरित प्रतिचित्र

$\mathbb {Z} /p_{n_{k}}^{a_{k}}\to \mathbb {Z} /p_{m_{l}}^{b_{l}}$

के लिए, हमारे निकट $a_{k}\geq b_{l}$ और $p_{n_{k}}=p_{m_{l}},$ हैं क्योंकि अभाज्य संख्याओं $p,q$, के एक युग्म के लिए, मात्र गैर-शून्य अनुमान

$\mathbb {Z} /p^{a}\to \mathbb {Z} /q^{b}$

को परिभाषित किया जा सकता है यदि $p=q$ और $a\geq b$।

ये अवलोकन अनंत पूर्णांकों के वलय के निर्माण के लिए महत्वपूर्ण हैं, जिन्हें ऐसे सभी प्रतिचित्रों की व्युत्क्रम सीमा के रूप में दिया गया है।

डेडेकाइंड का प्रमेय

वर्णों की रैखिक स्वतंत्रता पर डेडेकाइंड का प्रमेय। मान लीजिए कि M मोनोइड बनें और k एक पूर्णांकीय डोमेन है, जिसे k पर गुणन पर विचार करके एक मोनॉइड के रूप में देखा जाता है। फिर अलग-अलग मोनोइड समरूपताओं का कोई भी परिमित वर्ग ( f_i )_i∈I,  f_i : M → k रेखीय रूप से स्वतंत्र है। दूसरे शब्दों में,

$\sum _{i\in I}\alpha _{i}f_{i}=0$

को संतुष्ट करने वाले अवयवों α_i ∈ k का प्रत्येक वर्ग (α_i)_i∈I वर्ग (0)_i∈I के बराबर होना चाहिए।

प्रमाण. पहले मान लीजिये कि k क्षेत्र (गणित) है, अन्यथा, पूर्णांकीय डोमेन k को उसके भागफल क्षेत्र से बदलें, और कुछ भी नहीं बदलेगा। हम मोनोइड समरूपताओं  f_i : M → k को k-बीजगणित समरूपताओं तक रैखिक रूप से विस्तारित कर सकते हैं जहां k[M], k के पर M का मोनॉयड वलय है। फिर, रैखिकता से, स्थिति

$\sum _{i\in I}\alpha _{i}f_{i}=0,$

$\sum _{i\in I}\alpha _{i}F_{i}=0$ उत्पन्न करती है।

अगला, i, j ∈ I; i ≠ jके लिए; दो k-रैखिक प्रतिचित्र F_i : k[M] → k और F_j : k[M] → k एक दूसरे के समानुपाती नहीं हैं। अन्यथा  f_i  और  f_j  भी आनुपातिक होंगे, और इस प्रकार बराबर होंगे क्योंकि मोनोइड समरूपता के रूप में वे संतुष्ट होते हैं:  f_i (1) = 1 =  f_j (1), जो इस धारणा का खंडन करता है कि वे अलग हैं।

इसलिए, कर्नेल (बीजगणित) Ker F_i और Ker F_j अलग-अलग हैं। चूँकि k[M]/Ker F_i ≅ F_i (k[M]) = k एक क्षेत्र है, Ker F_i I में प्रत्येक i के लिए k[M] अधिकतम आदर्श है। क्योंकि वे भिन्न और अधिकतम हैं, आदर्श Ker F_i और Ker F_j जब भी i ≠ j होते हैं, सहअभाज्य होते हैं। चीनी शेष प्रमेय (सामान्य वलय के लिए) समरूपता उत्पन्न करता है:

${\begin{aligned}\phi :k[M]/K&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\phi (x+K)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}$

जहाँ

$K=\prod _{i\in I}\mathrm {Ker} F_{i}=\bigcap _{i\in I}\mathrm {Ker} F_{i}.$

फलस्वरूप, प्रतिचित्र

${\begin{aligned}\Phi :k[M]&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\Phi (x)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}$

विशेषण है। इस प्रकार से समरूपता k[M]/Ker F_i → F_i (k[M]) = k के अंतर्गत प्रतिचित्र Φ से मेल खाता है:

${\begin{aligned}\psi :k[M]&\to \prod _{i\in I}k\\\psi (x)&=\left[F_{i}(x)\right]_{i\in I}\end{aligned}}$

अब, प्रतिचित्र ψ किसी फलन के प्रतिबिम्ब में प्रत्येक सदिश (u_i)_i∈I के लिए

$\sum _{i\in I}\alpha _{i}F_{i}=0$

$\sum _{i\in I}\alpha _{i}u_{i}=0$

उत्पन्न करता है। चूँकि ψ विशेषण है, इसका अर्थ है कि प्रत्येक सदिश

$\left(u_{i}\right)_{i\in I}\in \prod _{i\in I}k$

के लिए

$\sum _{i\in I}\alpha _{i}u_{i}=0$।

फलस्वरूप, (α_i)_i∈I = (0)_i∈I। है

यह भी देखें

• आवरण प्रणाली
• हस्से सिद्धांत
• अवशेष संख्या प्रणाली

संदर्भ

• Dauben, Joseph W. (2007), "Chapter 3: Chinese Mathematics", in Katz, Victor J. (ed.), The Mathematics of Egypt, Mesopotamia, China, India and Islam : A Sourcebook, Princeton University Press, pp. 187–384, ISBN 978-0-691-11485-9
• Dence, Joseph B.; Dence, Thomas P. (1999), Elements of the Theory of Numbers, Academic Press, ISBN 9780122091308
• Duchet, Pierre (1995), "Hypergraphs", in Graham, R. L.; Grötschel, M.; Lovász, L. (eds.), Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, pp. 381–432, MR 1373663। See in particular Section 2।5, "Helly Property", pp। 393–394।
• Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae, translated by Clarke, Arthur A. (Second, corrected ed.), New York: Springer, ISBN 978-0-387-96254-2
• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd ed.), Springer-Verlag, ISBN 0-387-97329-X
• Kak, Subhash (1986), "Computational aspects of the Aryabhata algorithm" (PDF), Indian Journal of History of Science, 21 (1): 62–71
• Katz, Victor J. (1998), A History of Mathematics / An Introduction (2nd ed.), Addison Wesley Longman, ISBN 978-0-321-01618-8
• Libbrecht, Ulrich (1973), Chinese Mathematics in the Thirteenth Century: the "Shu-shu Chiu-chang" of Ch'in Chiu-shao, Dover Publications Inc, ISBN 978-0-486-44619-6
• Ore, Oystein (1988) [1948], Number Theory and Its History, Dover, ISBN 978-0-486-65620-5
• Pisano, Leonardo (2002), Fibonacci's Liber Abaci, translated by Sigler, Laurence E., Springer-Verlag, pp. 402–403, ISBN 0-387-95419-8
• Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, ISBN 978-0201-57889-8
• Sengupta, Ambar N. (2012), Representing Finite Groups, A Semimsimple Introduction, Springer, ISBN 978-1-4614-1232-8
• Bourbaki, N. (1989). Algebra I. Springer. ISBN 3-540-64243-9.

अग्रिम पठन

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7। See Section 31।5: The Chinese remainder theorem, pp। 873–876।
• Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996), Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography, World Scientific Publishing, pp. 1–213, ISBN 981-02-2827-9
• Hungerford, Thomas W. (1974), Algebra, Graduate Texts in Mathematics, Vol. 73, Springer-Verlag, pp. 131–132, ISBN 978-1-4612-6101-8
• Knuth, Donald (1997), The Art of Computer Programming, vol. 2: Seminumerical Algorithms (Third ed.), Addison-Wesley, ISBN 0-201-89684-2। See Section 4।3।2 (pp। 286–291), exercise 4।6।2–3 (page 456)।

बाहरी संबंध

• "Chinese remainder theorem", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Chinese Remainder Theorem". MathWorld.
• Chinese Remainder Theorem at PlanetMath.
• Full text of the Sun-tzu Suan-ching (Chinese) – Chinese Text Project