चीनी शेषफल प्रमेय की व्याख्या

एक संख्या को 3 से भाग देने पर 2, 5 से भाग देने पर 3 और 7 से भाग देने पर 2 शेष बचता है। वह संख्या कौन-सी है? संख्याओं को एक-एक करके आज़माएँ तो कुछ देर में 23 पर पहुँच जाएँगे, पर इस सवाल में एक प्रमेय छिपा है: जब तक भाजकों का कोई उभयनिष्ठ गुणनखंड नहीं है, उनके गुणनफल से नीचे हमेशा ठीक एक उत्तर होता है, और उसे बिना कुछ आज़माए ढूँढा जा सकता है। यह प्रमेय लगभग 1,500 साल पुराना है और आज भी कैलेंडरों में, कंप्यूटर अंकगणित में और वेब की रक्षा करने वाली क्रिप्टोग्राफ़ी में काम कर रहा है।

2 mod 3, 3 mod 5 और 2 mod 7 शेषफल देने वाली संख्याओं के निशानों की तीन पंक्तियाँ, जो 23 पर एक स्तंभ में मिलती हैं
2 mod 3, 3 mod 5 और 2 mod 7 शेषफल देने वाली संख्याओं के निशानों की तीन पंक्तियाँ, जो 23 पर एक स्तंभ में मिलती हैं

सुनज़ी सुआनजिंग की एक समस्या

सुनज़ी सुआनजिंग, तीसरी से पाँचवीं सदी की एक चीनी अंकगणित पुस्तक, ऐसी चीज़ों की गिनती पूछती है जो तीन-तीन करके गिनने पर 2, पाँच-पाँच करके गिनने पर 3 और सात-सात करके गिनने पर 2 बचाती हैं। इसका उत्तर 23 है, और इसकी विधि आज भी पढ़ाई जाती है: तीन-तीन गिनने पर बची हर चीज़ के लिए 70 लें, पाँच-पाँच गिनने पर बची हर चीज़ के लिए 21 और सात-सात गिनने पर बची हर चीज़ के लिए 15, जोड़ें, और जितनी बार हो सके 105 घटाएँ। 2 × 70 + 3 × 21 + 2 × 15 = 233, और 233 − 2 × 105 = 23। मिंग काल की एक कविता ने 70, 21, 15 और 105 को सदियों तक याद रखा। चिन जिउशाओ ने 1247 में एक सामान्य विधि दी, यही समस्या फ़िबोनाची की 1202 की लिबर अबाकी में आती है, और कार्ल फ्रेडरिक गाउस ने 1801 की अपनी डिस्क्विज़िशनेस अरिथमेटिके में प्रमेय को उसके आधुनिक रूप में लिखा।

सुन्ज़ी सुआजिंग के एक क़िंग-कालीन संस्करण का पृष्ठ। तीसरी-पाँचवीं शताब्दी की यह चीनी अंकगणित पुस्तक ऐसे संख्या की माँग करती है जो तीन, पाँच और सात से गिनने पर क्रमशः 2, 3 और 2 शेष बचे।
सुन्ज़ी सुआजिंग के एक क़िंग-कालीन संस्करण का पृष्ठ। तीसरी-पाँचवीं शताब्दी की यह चीनी अंकगणित पुस्तक ऐसे संख्या की माँग करती है जो तीन, पाँच और सात से गिनने पर क्रमशः 2, 3 और 2 शेष बचे।
कार्ल फ़्रीड्रिश गाउस, क्रिस्चियन आल्ब्रेख्त येन्सेन के 1840 के चित्र में। उन्होंने 1801 की Disquisitiones Arithmeticae में सर्वांगसमता संकेत a ≡ b (mod n) को प्रस्तुत किया।
कार्ल फ़्रीड्रिश गाउस, क्रिस्चियन आल्ब्रेख्त येन्सेन के 1840 के चित्र में। उन्होंने 1801 की Disquisitiones Arithmeticae में सर्वांगसमता संकेत a ≡ b (mod n) को प्रस्तुत किया।

प्रमेय क्या कहता है

मापांक n₁, n₂, …, nₖ लें, जिनमें से किन्हीं दो का कोई उभयनिष्ठ गुणनखंड नहीं है, और कोई भी शेषफल a₁, a₂, …, aₖ। तब 0 से N − 1 के बीच ठीक एक पूर्णांक x होता है, जहाँ N = n₁ × n₂ × … × nₖ, जिसे हर i के लिए nᵢ से भाग देने पर aᵢ शेष बचता है। बाक़ी सभी हल उससे N के गुणज जितने अलग होते हैं। मॉड्यूलर अंकगणित के संकेतन में: निकाय x ≡ aᵢ (mod nᵢ) का हल है, और वह mod N में अद्वितीय है। दूसरे शब्दों में, 0 से N − 1 तक की एक संख्या और उसके शेषफलों की सूची में ठीक वही जानकारी होती है: 3 × 5 × 7 = 105 संख्याएँ और शेषफलों की 3 × 5 × 7 = 105 संभावित सूचियाँ, हर एक का एक बार उपयोग।

हल बनाना

70, 21 और 15 कोई जादू नहीं हैं। हर एक को अपने मापांक से भाग देने पर 1 और बाक़ी मापांकों से भाग देने पर 0 बचता है: 70 = 2 × 35, 5 और 7 का गुणज है और 3 से भाग देने पर 1 बचाता है। सामान्य रूप में Nᵢ = N / nᵢ लिया जाता है, जो nᵢ को छोड़कर हर मापांक का गुणज है, और उसे yᵢ से गुणा किया जाता है, जो Nᵢ का mod nᵢ व्युत्क्रम है। व्युत्क्रम मौजूद है क्योंकि Nᵢ और nᵢ का कोई उभयनिष्ठ गुणनखंड नहीं है, और विस्तारित यूक्लिड एल्गोरिदम उसे ढूँढता है: वह महत्तम समापवर्तक के लिए यूक्लिड के भाग करता है और पीछे लौटकर बेज़ू सर्वसमिका 1 = s × nᵢ + t × Nᵢ तक पहुँचता है, ताकि t व्युत्क्रम हो। तब x = a₁N₁y₁ + a₂N₂y₂ + …, mod N में घटाया हुआ, हर समीकरण में फ़िट बैठता है, क्योंकि हर पद अपने समीकरण में फ़िट बैठता है और बाक़ी सब में ग़ायब हो जाता है।

एक-एक समीकरण करके

एक दूसरा तरीक़ा भी है, जिसमें सभी मापांकों का गुणनफल नहीं चाहिए। x ≡ 2 (mod 3) का हर हल x = 2 + 3t के रूप का होता है। इसे अगले समीकरण में रखें: 2 + 3t ≡ 3 (mod 5), यानी 3t ≡ 1 (mod 5), और 2 से गुणा करने पर, जो 3 का mod 5 व्युत्क्रम है, t ≡ 2 (mod 5) मिलता है। तब x = 2 + 3 × 2 = 8, और पहले दो समीकरण मिलकर कहते हैं x ≡ 8 (mod 15)। तीसरे समीकरण के साथ दोहराएँ: 8 + 15t ≡ 2 (mod 7) से t ≡ 1 मिलता है, इसलिए x ≡ 23 (mod 105)। यह प्रतिस्थापन संख्याओं को छोटा रखता है, कंप्यूटर आमतौर पर ऐसे निकायों को इसी तरह हल करता है, और यह तब भी काम करता है जब मापांकों का उभयनिष्ठ गुणनखंड हो।

उभयनिष्ठ गुणनखंड वाले मापांक

यदि दो मापांकों का कोई उभयनिष्ठ गुणनखंड है, तो उनके समीकरण एक-दूसरे पर चढ़ जाते हैं: x ≡ 1 (mod 4) पहले ही कहता है कि x विषम है, और x ≡ 4 (mod 6) कहता है कि x सम है, इसलिए कोई x दोनों को संतुष्ट नहीं करता। सामान्य रूप में x ≡ a (mod m) और x ≡ b (mod n) ठीक तब एक साथ सही हो सकते हैं जब a और b को g = gcd(m, n) से भाग देने पर एक ही शेषफल आए, यानी जब g, a − b को विभाजित करे। तब हल mod m × n में नहीं, बल्कि mod lcm(m, n) = m × n / g में अद्वितीय होता है। अंडों की टोकरी वाली पुरानी पहेली, जिसमें 2, 3, 4, 5 या 6 एक साथ निकालने पर 1 बचता है और 7 एक साथ निकालने पर कुछ नहीं, का उत्तर 301 है, जो हर 420 = lcm(2, 3, 4, 5, 6, 7) पर दोहराता है। किसी निकाय का हल ठीक तब होता है जब उसके हर दो समीकरण मेल खाते हों, इसलिए असंभव निकाय में हमेशा एक टकराने वाला जोड़ा होता है।

कैलेंडर, कंप्यूटर और RSA

1583 में जोसेफ़ स्कालिगर ने तीन कैलेंडर चक्रों, 28 वर्ष के सौर चक्र, 19 वर्ष के चंद्र चक्र और 15 वर्ष के इंडिक्शन, को मिलाकर 28 × 19 × 15 = 7,980 वर्ष की जूलियन अवधि बनाई। प्रमेय के अनुसार हर वर्ष के पास तीन चक्र-संख्याओं का अपना अलग संयोजन है, और अवधि 4713 ईसा पूर्व से शुरू होती है, वह आख़िरी वर्ष जब तीनों 1 थीं; खगोलशास्त्री आज भी वहीं से जूलियन दिन गिनते हैं। कंप्यूटर इस प्रमेय का उपयोग बहुत बड़ी संख्याओं को छोटे शेषफलों की सूचियों के रूप में गिनने के लिए करते हैं, जिन्हें अलग-अलग और समानांतर रूप से जोड़ा और गुणा किया जा सकता है, और अंत में मिलाया जा सकता है। RSA डिक्रिप्शन भी ऐसे ही काम करता है: n = p × q के साथ c^d mod n को mod p और mod q की दो घातों के रूप में निकाला जाता है और प्रमेय से जोड़ा जाता है, जो mod n की एक घात से लगभग चार गुना तेज़ है। मिन्योत और आसमुथ-ब्लूम जैसी गुप्त-साझेदारी योजनाएँ किसी रहस्य को शेषफलों में छिपाती हैं, ताकि पर्याप्त शेषफल मिलकर ही उसे प्रकट कर सकें।

रॉन रिवेस्ट, आदि शमीर और लेन एडलमैन (बाएँ से दाएँ)
रॉन रिवेस्ट, आदि शमीर और लेन एडलमैन (बाएँ से दाएँ)

ख़ुद आज़माएँ

कोई भी सर्वांगसमता निकाय लिखने के लिए कैलकुलेटर खोलें, अधिकतम 20 समीकरण और अधिकतम 200 अंकों की संख्याएँ, या हल किए हुए उदाहरणों में से कोई चुनें: सुनज़ी की समस्या, अंडों की टोकरी, जूलियन अवधि, दो बसों की समय-सारणी, RSA डिक्रिप्शन और बिना हल का एक निकाय। हल आपकी संख्याओं के साथ लिखा जाता है, रचना या प्रतिस्थापन से, हर व्युत्क्रम के लिए विस्तारित यूक्लिड एल्गोरिदम के साथ। चित्र हर समीकरण को संतुष्ट करने वाली संख्याओं पर निशान लगाता है, ताकि आप वह एकमात्र स्तंभ देख सकें जहाँ सब मिलते हैं, या दो समीकरणों के शेषफलों को एक ऐसी तालिका में रखता है जिसमें हर संख्या का अपना खाना है।

अक्सर पूछे जाने वाले प्रश्न

क्या सर्वांगसमता निकाय का हल अद्वितीय है?

सिर्फ़ मापांक के गुणज तक। अगर x = 23 सुनज़ी की समस्या को हल करता है, तो 23 + 105 = 128, 233 और −82 भी करते हैं, क्योंकि 105 जोड़ने से कोई शेषफल नहीं बदलता। प्रमेय कहता है कि 0 से 104 तक ठीक एक हल है; उभयनिष्ठ गुणनखंड वाले मापांकों के लिए उनके लघुत्तम समापवर्त्य से नीचे ठीक एक।

मापांकों का सहअभाज्य होना क्यों ज़रूरी है?

रचना के लिए, क्योंकि Nᵢ का mod nᵢ व्युत्क्रम होना चाहिए, और वह तभी होता है जब उनका कोई उभयनिष्ठ गुणनखंड न हो। प्रमेय के लिए, क्योंकि उभयनिष्ठ गुणनखंड कुछ समीकरणों को एक-दूसरे पर चढ़ा देते हैं: तब निकाय का या तो कोई हल नहीं होता या कम अलग-अलग हल होते हैं, और हल हर गुणनफल के बजाय हर लघुत्तम समापवर्त्य पर दोहराते हैं।

मॉड्यूलर व्युत्क्रम हाथ से कैसे निकालें?

विस्तारित यूक्लिड एल्गोरिदम से। 15 के mod 7 व्युत्क्रम के लिए: 15 = 2 × 7 + 1, इसलिए 1 = 15 − 2 × 7, और 15 × 1 ≡ 1 (mod 7): व्युत्क्रम 1 है। 35 mod 3 के लिए: 35 = 11 × 3 + 2 और 3 = 1 × 2 + 1, इसलिए 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, और 35 का mod 3 व्युत्क्रम −1 ≡ 2 है। छोटे मापांकों के लिए आप बस 1, 2, 3, … आज़मा सकते हैं जब तक गुणनफल पर 1 न बचे।

इस प्रमेय का घड़ियों से क्या संबंध है?

mod n का शेषफल n घंटों वाली घड़ी पर एक स्थिति है। 3 और 5 घंटों वाली दो घड़ियाँ, जो साथ शुरू होकर हर बार एक घंटा आगे बढ़ती हैं, शुरुआत पर लौटने से पहले स्थितियों के 15 जोड़ों में से हर एक को एक बार दिखाती हैं, क्योंकि 3 और 5 का कोई उभयनिष्ठ गुणनखंड नहीं है। 4 और 6 घंटों वाली घड़ियाँ 12 क़दमों में लौट आती हैं और 24 में से सिर्फ़ 12 जोड़े दिखाती हैं: एक विषम और एक सम स्थिति कभी साथ नहीं आतीं।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

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