मॉड्यूलर अंकगणित की व्याख्या

हर कोई पहले से ही मॉड्यूलर अंकगणित करता है: 8 बजे के 10 घंटे बाद 6 बजते हैं, और रविवार के बाद का दिन सोमवार होता है। n कदमों के बाद फिर से 0 से शुरू होने वाली गिनती का अपना एक पूरा अंकगणित निकलता है, जिसमें नियम हैं, आश्चर्य हैं, और संख्या सिद्धांत में तथा इंटरनेट की सुरक्षा करने वाली क्रिप्टोग्राफ़ी में एक केंद्रीय स्थान है।

0 से 11 तक क्रमांकित बारह स्थानों वाली एक घड़ी और एक सर्पिल रास्ता जो 9 से 2 तक डायल के चारों ओर एक बार घूमता है
0 से 11 तक क्रमांकित बारह स्थानों वाली एक घड़ी और एक सर्पिल रास्ता जो 9 से 2 तक डायल के चारों ओर एक बार घूमता है

शेषफल और सर्वांगसमता

a को n से भाग दें और केवल शेषफल रखें: यही a mod n है, 0 से n − 1 तक की एक संख्या। 26 mod 7 = 5, क्योंकि 26 = 3 × 7 + 5। समान शेषफल वाली संख्याएँ mod n में एक जैसा व्यवहार करती हैं, इसलिए हम उन्हें सर्वांगसम कहते हैं: 26 ≡ 5 ≡ −2 (mod 7)। कार्ल फ़्रीड्रिख़ गॉस ने यह संकेतन 1801 की अपनी पुस्तक Disquisitiones Arithmeticae में शुरू किया, और इसने फ़र्मा और ऑयलर के पुराने अवलोकनों को एक स्वतंत्र अंकगणित बना दिया। n स्थानों वाली घड़ी पर हर पूर्ण संख्या अपने शेषफल पर पहुँचती है; पूरे चक्कर भुला दिए जाते हैं।

कार्ल फ़्रीड्रिश गाउस, क्रिस्चियन आल्ब्रेख्त येन्सेन के 1840 के चित्र में। उन्होंने 1801 की Disquisitiones Arithmeticae में सर्वांगसमता संकेत a ≡ b (mod n) को प्रस्तुत किया।
कार्ल फ़्रीड्रिश गाउस, क्रिस्चियन आल्ब्रेख्त येन्सेन के 1840 के चित्र में। उन्होंने 1801 की Disquisitiones Arithmeticae में सर्वांगसमता संकेत a ≡ b (mod n) को प्रस्तुत किया।

जोड़ना, घटाना और गुणा करना

तीनों सामान्य संक्रियाएँ हमेशा की तरह काम करती हैं, और आप जब चाहें mod n में घटा सकते हैं: किसी योग का शेषफल शेषफलों के योग का शेषफल होता है, और यही बात अंतर और गुणनफल पर भी लागू होती है। 37 × 48 का अंतिम अंक जानने के लिए केवल अंतिम अंकों को गुणा करें: 7 × 8 = 56, इसलिए यह 6 पर समाप्त होता है। यही बात मॉड्यूलर अंकगणित को कंप्यूटरों के लिए इतना उपयोगी बनाती है: संख्याएँ कितनी भी बड़ी हों, बीच के मान कभी n² से अधिक नहीं होते।

भाग के लिए व्युत्क्रम चाहिए

भाग अपवाद है। 2 × 3 ≡ 2 × 8 (mod 10), क्योंकि दोनों mod 10 में 6 हैं, फिर भी 3 और 8 अलग हैं, इसलिए आप 2 को सीधे काट नहीं सकते। a से भाग देने का अर्थ है उसके व्युत्क्रम से गुणा करना, यानी वह संख्या x जिसके लिए a × x ≡ 1, और यह ठीक तभी मौजूद होता है जब a और n का कोई उभयनिष्ठ गुणनखंड न हो। विस्तारित यूक्लिडियन एल्गोरिदम इसे ढूँढता है: यह महत्तम समापवर्तक के लिए यूक्लिड के भाग वाले चरण चलाता है और हर चरण पर एक गुणक का हिसाब रखता है, ताकि जब शेषफल 1 पर पहुँचे, तो वह गुणक ही व्युत्क्रम हो। जब n अभाज्य होता है, तो 0 को छोड़कर हर संख्या का व्युत्क्रम होता है, और भाग हमेशा संभव होता है।

घातें, फ़र्मा और ऑयलर

घातें दोहराती हैं। mod 7 में 3 की घातें लें: 3, 2, 6, 4, 5, 1, और फिर से 3। उस चक्र की लंबाई 3 की कोटि है। 1640 में पियरे द फ़र्मा ने देखा कि अभाज्य p के लिए, जब भी p, a को विभाजित नहीं करता, a^(p − 1) ≡ 1 (mod p), इसलिए हर कोटि p − 1 को विभाजित करती है। लियोनहार्ड ऑयलर ने इसे सिद्ध किया और इसे किसी भी n तक विस्तारित किया, जिसमें p − 1 की जगह n के सहअभाज्य मानों की संख्या आती है। बहुत बड़ी घातें बार-बार वर्ग करके निकाली जाती हैं: a, a², a⁴, a⁸ … हर एक पिछले का वर्ग, mod n में घटाया हुआ, फिर घातांक के बाइनरी अंकों के अनुसार गुणा किया जाता है।

पियर द फ़र्मा का चित्र
पियर द फ़र्मा का चित्र
लियोनहार्ड यूलर का चित्र
लियोनहार्ड यूलर का चित्र

जाँच अंक और कैलेंडर

मॉड्यूलर अंकगणित गलतियाँ पकड़ता है। ISBN-10 का अंतिम अंक इस तरह चुना जाता है कि सभी दस अंकों का भारित योग 11 का गुणज हो, इसलिए कोई भी एक गलत अंक और दो पड़ोसी अंकों की कोई भी अदला-बदली पकड़ी जाती है। बैंक कार्ड नंबर mod 10 वाली Luhn जाँच का उपयोग करते हैं, और IBAN mod 97 वाली जाँच का। कैलेंडर mod 7 पर चलते हैं: किसी भी तारीख का वार कुछ शेषफलों से निकाला जा सकता है, और स्थायी कैलेंडर तथा डूम्सडे नियम इसी तरह काम करते हैं।

क्रिप्टोग्राफ़ी

आधुनिक क्रिप्टोग्राफ़ी उन मॉड्यूलर घातों पर बनी है जिनकी गणना आसान है और जिन्हें उलटना कठिन। 1976 के डिफ़ी–हेलमैन कुंजी विनिमय में दो लोग एक बड़ी अभाज्य संख्या के mod में घातों का आदान-प्रदान करके एक खुली लाइन पर साझा रहस्य तय करते हैं। RSA, जिसे 1977 में रिवेस्ट, शमीर और एडलमैन ने प्रकाशित किया, संदेश m को m^e mod n के रूप में एन्क्रिप्ट करता है, जहाँ n दो बड़ी अभाज्य संख्याओं का गुणनफल है, और एक दूसरे घातांक d से डिक्रिप्ट करता है जिसकी गणना केवल वही कर सकता है जो दोनों अभाज्य संख्याएँ जानता हो। पाठ्यपुस्तक वाले उदाहरण में n = 3233 = 61 × 53, e = 17 और d = 413: 65, 2790 बन जाता है, और 2790 फिर से 65 बन जाता है।

ख़ुद आज़माएँ

30 अंकों तक की संख्याओं के लिए a mod n, योग, अंतर, गुणनफल, घातें, व्युत्क्रम और mod n में भागफल निकालने के लिए मॉड्यूलर घड़ी खोलें। हर उत्तर अपने चरणों के साथ आता है: शेषफल सहित भाग, बार-बार वर्ग करने से मिली घातें, या विस्तारित यूक्लिडियन एल्गोरिदम की तालिका। घड़ी दिखाती है कि उत्तर तक कैसे पहुँचा जाता है, जोड़ के सर्पिल से लेकर घातों के चक्र तक, और छोटे n के लिए संक्रिया की तालिका सभी उत्तर एक साथ दिखाती है।

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

चिह्न ≡ का क्या अर्थ है?

a ≡ b (mod n) का अर्थ है कि n से भाग देने पर a और b का शेषफल समान होता है, या समतुल्य रूप से n, a − b को विभाजित करता है। 38 ≡ 2 (mod 12), क्योंकि 38 − 2 = 36, 12 का गुणज है।

क्या mod प्रोग्रामिंग के % ऑपरेटर जैसा ही है?

धनात्मक संख्याओं के लिए, हाँ। ऋणात्मक संख्याओं के लिए C, Java और JavaScript जैसी कई भाषाएँ ऋणात्मक शेषफल लौटाती हैं: वहाँ −7 % 3 का मान −1 है, जबकि −7 mod 3 = 2। Python का % धनात्मक n के लिए गणितीय परिपाटी का पालन करता है।

mod n में किसी संख्या की कोटि क्या है?

वह सबसे छोटा k > 0 जिसके लिए a^k ≡ 1 (mod n)। यह केवल तब मौजूद होती है जब a और n का कोई उभयनिष्ठ गुणनखंड न हो। mod 7 में 2 की कोटि 3 है, क्योंकि 2³ = 8 ≡ 1, और mod 7 में 3 की कोटि 6 है, इसलिए 3 की घातें हर शून्येतर शेषफल से होकर गुज़रती हैं: 3, mod 7 का एक आदिम मूल है।

मॉड्यूलर अंकगणित का आविष्कार किसने किया?

शेषफलों का उपयोग बहुत पहले से होता था, उदाहरण के लिए तीसरी से पाँचवीं शताब्दी के चीनी शेषफल प्रमेय में, और फ़र्मा तथा ऑयलर द्वारा। गॉस ने 1801 में सर्वांगसमताओं के संकेतन के साथ इसे एक व्यवस्थित अंकगणित बनाया।

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

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

मॉड्यूलर घड़ी खोलें