मॉड्यूलर अंकगणित

This article is about the (mod n) notation. For the binary operation mod(a,n), see modulo operation.

इस घड़ी पर टाइम-कीपिंग अंकगणित मॉड्यूल 12 का उपयोग करता है। 4 घंटे को 9 बजे जोड़ने से 1 बजे होता है, क्योंकि 13 1 मॉड्यूलो 12 के अनुरूप है।

गणित में, मॉड्यूलर अंकगणित पूर्णांक के लिए एक प्रणाली है, जहां एक निश्चित मूल्य तक पहुंचने पर संख्याएं "परिवेष्टन हैं", जिसे मापांक कहा जाता है। मॉड्यूलर अंकगणित के लिए आधुनिक दृष्टिकोण कार्ल फ्रेडरिक गॉस द्वारा 1801 में प्रकाशित अपनी पुस्तक अंकगणितीय शोध' में विकसित किया गया था।

मॉड्यूलर अंकगणित का परिचित उपयोग12 घंटे की घड़ी में होता है, जिसमें दिन को दो 12 घंटे की अवधि में विभाजित किया जाता है। यदि समय अभी 7:00 है, तो 8 घंटे बाद 3:00 बजे होंगे। सरल जोड़ का परिणाम 7 + 8 = 15 होगा, लेकिन घड़ियाँ हर 12 घंटे में "परिवेष्टन हैं"। चूंकि घंटे की संख्या 12 तक पहुंचने पर शून्य से शुरू होती है, यह अंकगणित मॉड्यूल 12 है। नीचे दी गई परिभाषा के संदर्भ में 15, 3 मॉड्यूलो 12 के अनुरूप है, इसलिए 24 घंटे की घड़ीपर "15:00" प्रदर्शित होता है "3 : 00" 12 घंटे की घड़ी पर।

सर्वांगसमता

एक पूर्णांक दिया n > 1, जिसे मापांक कहा जाता है, दो पूर्णांक a तथा b सर्वांगसम मोडुलो कहलाते हैं n, यदि n उनके अंतर का विभाजक है (अर्थात, यदि कोई पूर्णांक है k ऐसा है कि a − b = kn).

सर्वांगसमता मॉड्यूल n सर्वांगसम संबंध है, जिसका अर्थ है कि यह तुल्यता संबंध है जो जोड़, घटाव और गुणा के संचालन के साथ संगत है। सर्वांगसमता मॉड्यूल n निरूपित किया जाता है:

$a\equiv b{\pmod {n}}.$

कोष्ठक का अर्थ है (mod n) पूरे समीकरण न कि केवल दाहिनी ओर (यहाँ, b) पर लागू होता है। इस संकेतन को संकेतन के साथ भ्रमित नहीं होना है b mod n (कोष्ठक के बिना), जो मॉडुलो ऑपरेशन को संदर्भित करता है। वास्तव में, b mod n अद्वितीय पूर्णांक को दर्शाता है a ऐसा है कि 0 ≤ a < n तथा $a\equiv b\;({\text{mod}}\;n)$ (अर्थात, $b$ का शेष भाग $n$ से विभाजित किया जाता है।).

सर्वांगसमता संबंध को इस रूप में फिर से लिखा जा सकता है

$a=kn+b,$

स्पष्ट रूप से यूक्लिडियन विभाजन के साथ अपना संबंध दिखा रहा है। हालांकि यहाँ b को n. द्वारा a के विभाजन का शेष होना आवश्यक नहीं है। इसके बजाय, कथन a ≡ b (mod n) क्या दावा करता है कि a तथा b को n से विभाजित करने पर समान शेषफल प्राप्त होता है . वह है,

$a=pn+r,$

$b=qn+r,$

जहाँ पे 0 ≤ r < n सामान्य शेषफल है। इन दो व्यंजक को घटाकर, हम पिछले संबंध को पुनः प्राप्त करते हैं:

$a-b=kn,$

व्यवस्थित करके k = p − q.

उदाहरण

मापांक 12 में, कोई यह दावा कर सकता है कि:

$38\equiv 14{\pmod {12}}$

इसलिये 38 − 14 = 24, जो कि 12 का गुणज है। इसे व्यक्त करने का दूसरा तरीका यह है कि 38 और 14 दोनों को 12 से विभाजित करने पर समान शेषफल 2 प्राप्त होता है।

सर्वांगसमता की परिभाषा ऋणात्मक मानों पर भी लागू होती है। उदाहरण के लिए:

${\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv 7{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}$

गुण

सर्वांगसमता संबंध तुल्यता संबंध की सभी शर्तों को संतुष्ट करता है:

• प्रतिवर्तता: a ≡ a (mod n) *
• समरूपता: a ≡ b (mod n) यदि b ≡ a (mod n) सभी के लिए a, b, तथा n.
• संक्रामकता: यदि a ≡ b (mod n) तथा b ≡ c (mod n), फिर a ≡ c (mod n)

यदि a₁ ≡ b₁ (mod n) तथा a₂ ≡ b₂ (mod n), या अगर a ≡ b (mod n), फिर:

• a + k ≡ b + k (mod n) किसी भी पूर्णांक k के लिए (अनुवाद के साथ अनुकूलता)
• k a ≡ k b (mod n) किसी भी पूर्णांक k के लिए (प्रवर्धन के साथ अनुकूलता)
• k a ≡ k b (mod kn) किसी भी पूर्णांक k के लिए
• a₁ + a₂ ≡ b₁ + b₂ (mod n) (जोड़ के साथ अनुकूलता)
• a₁ – a₂ ≡ b₁ – b₂ (mod n) (घटाव के साथ संगतता)
• a₁ a₂ ≡ b₁ b₂ (mod n) (गुणन के साथ अनुकूलता)
• a^k ≡ b^k (mod n) किसी भी ऋणेतर पूर्णांक k के लिए (घातांक के साथ संगतता)
• p(a) ≡ p(b) (mod n), किसी भी बहुपद के लिए p(x) पूर्णांक गुणांक के साथ (बहुपद मूल्यांकन के साथ अनुकूलता)

यदि a ≡ b (mod n), तो यह सामान्यतः आभासी है कि k^a ≡ k^b (mod n). हालाँकि, निम्नलिखित सत्य है:

• यदि c ≡ d (mod φ(n)), जहाँ पे φ तब यूलर का कुल कार्य है a^c ≡ a^d (mod n)- बशर्ते कि a, n के साथ सह अभाज्य हो।

सामान्य शर्तों को रद्द करने के लिए, हमारे पास निम्नलिखित नियम हैं:

• यदि a + k ≡ b + k (mod n), जहाँ पे k कोई पूर्णांक है, तो a ≡ b (mod n)
• यदि k a ≡ k b (mod n) तथा k के साथ n सह अभाज्य है , फिर a ≡ b (mod n)
• यदि k a ≡ k b (mod kn) तथा k ≠ 0, फिर a ≡ b (mod n)

मॉड्यूलर गुणात्मक व्युत्क्रम निम्नलिखित नियमों द्वारा परिभाषित किया गया है:

• अस्तित्व: निरूपित पूर्णांक मौजूद है a^–1 ऐसा है कि aa^–1 ≡ 1 (mod n) अगर और केवल अगर a के साथ n सह अभाज्य है। यह पूर्णांक a^–1 का मॉड्यूलर गुणक व्युत्क्रम कहा जाता है a मापांक n।
• यदि a ≡ b (mod n) तथा a^–1 मौजूद है, तो a^–1 ≡ b^–1 (mod n) (गुणात्मक व्युत्क्रम के साथ अनुकूलता, और, यदि a = b, विशिष्टता मॉड्यूलो n)
• यदि a x ≡ b (mod n) तथा a सह अभाज्य है n, तो इस रैखिक सर्वांगसमता का हल निम्न द्वारा दिया जाता है x ≡ a^–1b (mod n)

गुणक उलटा x ≡ a^–1 (mod n) बेज़ाउट की पहचान | बेज़ाउट के समीकरण को हल करके कुशलतापूर्वक गणना की जा सकती है $ax+ny=1$ के लिये $x,y$- विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करना।

विशेष रूप से, अगर p एक अभाज्य संख्या है, तो a के साथ सह अभाज्य है p हरएक के लिए a ऐसा है कि 0 < a < p; इस प्रकार सभी के लिए एक गुणक व्युत्क्रम मौजूद है a जो शून्य सापेक्ष के अनुरूप नहीं है p.

सर्वांगसमता संबंधों के कुछ अधिक उन्नत गुण निम्नलिखित हैं:

• फर्मेट की छोटी प्रमेय: यदि p प्रधान है और विभाजित नहीं करता है a, फिर a ^{p – 1} ≡ 1 (mod p).
• यूलर प्रमेय: यदि a तथा n Coprime हैं, तो a ^φ(n) ≡ 1 (mod n), जहाँ पे φ यूलर का कुल कार्य है
• फ़र्मेट की छोटी प्रमेय का एक सरल परिणाम यह है कि अगर p प्रमुख है, तो a⁻¹ ≡ a ^{p − 2} (mod p) का गुणक प्रतिलोम है 0 < a < p. अधिक सामान्यतः, यूलर के प्रमेय से, यदि a तथा n Coprime हैं, तो a⁻¹ ≡ a ^{φ(n) − 1} (mod n).
• एक और सरल परिणाम यह है कि यदि a ≡ b (mod φ(n)), जहाँ पे φ तब यूलर का कुल कार्य है k^a ≡ k^b (mod n) बशर्ते k के साथ सह अभाज्य है n.
• विल्सन प्रमेय: p प्रधान है अगर और केवल अगर (p − 1)! ≡ −1 (mod p).
• चीनी शेष प्रमेय: किसी के लिए a, b और सह अभाज्य m, n, वहाँ एक अनूठा मौजूद है x (mod mn) ऐसा है कि x ≡ a (mod m) तथा x ≡ b (mod n). वास्तव में, x ≡ b m_n^–1 m + a n_m^–1 n (mod mn) जहाँ पे m_n⁻¹ का विलोम है m मापांक n तथा n_m⁻¹ का विलोम है n मापांक m.
• लैग्रेंज का प्रमेय (संख्या सिद्धांत) | लैग्रेंज का प्रमेय: सर्वांगसमता f (x) ≡ 0 (mod p), जहाँ पे p प्रमुख है, और f (x) = a₀ xⁿ + ... + a_n पूर्णांक गुणांकों वाला एक बहुपद है जैसे कि a₀ ≠ 0 (mod p), अधिक से अधिक है n जड़ें।
• प्रिमिटिव रूट मोडुलो एन | प्रिमिटिव रूट मोडुलो n: एक संख्या g एक आदिम रूट मॉड्यूलो है n अगर, हर पूर्णांक के लिए a सह अभाज्य टू n, एक पूर्णांक है k ऐसा है कि g^k ≡ a (mod n). एक आदिम रूट मॉड्यूलो n मौजूद है अगर और केवल अगर n के बराबर है 2, 4, p^k या 2p^k, जहाँ पे p एक विषम अभाज्य संख्या है और k एक सकारात्मक पूर्णांक है। यदि एक आदिम रूट मॉड्यूलो n मौजूद है, तो बिल्कुल हैं φ(φ(n)) ऐसी आदिम जड़ें, जहाँ φ यूलर का कुल कार्य है।
• द्विघात अवशेष: एक पूर्णांक a एक द्विघात अवशेष मॉड्यूल है n, यदि कोई पूर्णांक मौजूद है x ऐसा है कि x² ≡ a (mod n). यूलर की कसौटी का दावा है कि, अगर p एक विषम प्रधान है, और a का गुणज नहीं है p, फिर a एक द्विघात अवशेष मॉड्यूल है p अगर और केवल अगर

$a^{(p-1)/2}\equiv 1{\pmod {p}}.$

सर्वांगसमता वर्ग

किसी भी सर्वांगसम संबंध की तरह, सर्वांगसमता सापेक्ष n एक तुल्यता संबंध है, और पूर्णांक का तुल्यता वर्ग है a, द्वारा चिह्नित a_n, समुच्चय है {... , a − 2n, a − n, a, a + n, a + 2n, ...}. यह समुच्चय सर्वांगसम सभी पूर्णांकों से मिलकर बना है aमापांकn, को सर्वांगसमता वर्ग, अवशेष वर्ग, या केवल पूर्णांक का अवशेष कहा जाता है a मापांकn. जब मापांक n संदर्भ से ज्ञात होता है कि अवशेषों को भी निरूपित किया जा सकता है [a].

अवशेष प्रणाली

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

कम से कम अवशेष प्रणाली एक पूर्ण अवशेष प्रणाली है, और एक पूर्ण अवशेष प्रणाली बस एक सेट है जिसमें प्रत्येक अवशेष वर्ग मॉड्यूलो का ठीक एक प्रतिनिधि (गणित) होता है। n. उदाहरण के लिए। कम से कम अवशेष प्रणाली मॉड्यूलो 4 {0, 1, 2, 3} है। कुछ अन्य पूर्ण अवशेष प्रणाली मॉड्यूलो 4 में शामिल हैं:

• {1, 2, 3, 4}
• {13, 14, 15, 16}
• {−2, -1, 0, 1}
• {−13, 4, 17, 18}
• {−5, 0, 6, 21}
• {27, 32, 37, 42}

कुछ सेट जो पूर्ण अवशेष प्रणाली मॉड्यूलो 4 नहीं हैं:

• {−5, 0, 6, 22}, क्योंकि 6 22 मॉड्यूल 4 के सर्वांगसम है।
• {5, 15}, चूंकि एक पूर्ण अवशेष प्रणाली मोडुलो 4 में ठीक 4 असंगत अवशेष वर्ग होने चाहिए।

कम अवशेष प्रणाली

Main article: Reduced residue system

यूलर के कुल कार्य को देखते हुए φ(n), का कोई भी सेट φ(n) पूर्णांक जो Coprime पूर्णांक हैं n और मॉड्यूलस के तहत परस्पर असंगत n एक कम अवशेष प्रणाली मोडुलो कहा जाता है n. ऊपर से सेट {5,15}, उदाहरण के लिए, एक कम अवशेष प्रणाली मोडुलो 4 का एक उदाहरण है।

पूर्णांक मॉड्यूल एन

एक मापांक के लिए पूर्णांकों के सभी #Congruence वर्गों का समुच्चय n पूर्णांक मॉड्यूलो का वलय कहा जाता है n, और निरूपित किया जाता है ${\textstyle \mathbb {Z} /n\mathbb {Z} }$, $\mathbb {Z} /n$, या $\mathbb {Z} _{n}$. अंकन $\mathbb {Z} _{n}$ हालांकि, इसकी अनुशंसा नहीं की जाती है क्योंकि इसे P-adic#Algebraic approach| के सेट के साथ भ्रमित किया जा सकता हैn-एडिक पूर्णांक। अंगूठी (गणित) $\mathbb {Z} /n\mathbb {Z}$ गणित की विभिन्न शाखाओं के लिए मौलिक है (देखें § Applications नीचे)।

सेट को n > 0 के रूप में परिभाषित किया गया है:

$\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}\mid a\in \mathbb {Z} \right\}=\left\{{\overline {0}}_{n},{\overline {1}}_{n},{\overline {2}}_{n},\ldots ,{\overline {n{-}1}}_{n}\right\}.$

(कब n = 0, $\mathbb {Z} /n\mathbb {Z}$ खाली समुच्चय नहीं है; बल्कि, यह समरूपतावाद है $\mathbb {Z}$, जबसे a₀ = {a}.)

हम जोड़, घटाव और गुणा को परिभाषित करते हैं $\mathbb {Z} /n\mathbb {Z}$ निम्नलिखित नियमों द्वारा:

• ${\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}$
• ${\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(a-b)}}_{n}$
• ${\overline {a}}_{n}{\overline {b}}_{n}={\overline {(ab)}}_{n}.$

यह सत्यापन कि यह एक उचित परिभाषा है, पहले दिए गए गुणों का उपयोग करता है।

इस तरह, $\mathbb {Z} /n\mathbb {Z}$ क्रमविनिमेय वलय बन जाता है। उदाहरण के लिए, रिंग में $\mathbb {Z} /24\mathbb {Z}$, अपने पास

${\overline {12}}_{24}+{\overline {21}}_{24}={\overline {33}}_{24}={\overline {9}}_{24}$

24 घंटे की घड़ी के लिए अंकगणित के रूप में।

हम संकेतन का उपयोग करते हैं $\mathbb {Z} /n\mathbb {Z}$ क्योंकि यह का भागफल वलय है $\mathbb {Z}$ रिंग आदर्श द्वारा $n\mathbb {Z}$, एक सेट जिसमें सभी पूर्णांक विभाज्य हैं n, जहाँ पे $0\mathbb {Z}$ सिंगलटन सेट है {0}. इस प्रकार $\mathbb {Z} /n\mathbb {Z}$ एक क्षेत्र (गणित) है जब $n\mathbb {Z}$ एक अधिकतम आदर्श है (यानी, कब n प्रमुख है)।

इसे समूह से भी बनाया जा सकता है $\mathbb {Z}$ अकेले अतिरिक्त ऑपरेशन के तहत। अवशेष वर्ग a_n का समूह सहसमुच्चय है a भागफल समूह में $\mathbb {Z} /n\mathbb {Z}$, एक चक्रीय समूह। विशेष मामले को बाहर करने के बजाय n = 0शामिल करना अधिक उपयोगी है $\mathbb {Z} /0\mathbb {Z}$ (जो, जैसा कि पहले उल्लेख किया गया है, रिंग के लिए आइसोमोर्फिक है $\mathbb {Z}$ पूर्णांकों का)। वास्तव में, यह समावेशन एक अंगूठी (गणित) की विशेषता (बीजगणित) पर चर्चा करते समय उपयोगी होता है।

पूर्णांक मॉड्यूलो की अंगूठी n एक परिमित क्षेत्र है अगर और केवल अगर n प्रधान है (यह सुनिश्चित करता है कि प्रत्येक अशून्य तत्व में एक मॉड्यूलर गुणात्मक व्युत्क्रम होता है)। यदि $n=p^{k}$ k > 1 के साथ एक प्रमुख शक्ति है, वहाँ एक अद्वितीय (समरूपता तक) परिमित क्षेत्र मौजूद है $\mathrm {GF} (n)=\mathbb {F} _{n}$ साथ n तत्व, लेकिन यह नहीं है $\mathbb {Z} /n\mathbb {Z}$, जो एक क्षेत्र होने में विफल रहता है क्योंकि इसमें शून्य-भाजक हैं।

पूर्णांकों के गुणक समूह n को निरूपित किया जाता है $(\mathbb {Z} /n\mathbb {Z} )^{\times }$. इसमें शामिल है ${\overline {a}}_{n}$ (जहाँ एक सह अभाज्य पूर्णांक से n), जो वास्तव में गुणक व्युत्क्रम रखने वाले वर्ग हैं। यह क्रम के साथ गुणन के तहत एक क्रमविनिमेय समूह (गणित) बनाता है $\varphi (n)$.

वास्तविक संख्या में विस्तार

See also: Modulo operation

अनुप्रयोग

सैद्धांतिक गणित में, मॉड्यूलर अंकगणित संख्या सिद्धांत की नींव में से एक है, जो इसके अध्ययन के लगभग हर पहलू को छूता है, और इसका उपयोग समूह सिद्धांत, रिंग सिद्धांत, गांठ सिद्धांत और अमूर्त बीजगणित में भी व्यापक रूप से किया जाता है। अनुप्रयुक्त गणित में, इसका उपयोग कंप्यूटर बीजगणित[[सार्वजनिक कुंजी क्रिप्टोग्राफी]], कंप्यूटर विज्ञान, रसायन विज्ञान और दृश्य कला और संगीत कला में किया जाता है।

सीरियल नंबर पहचानकर्ताओं के भीतर चेकसम की गणना करना एक बहुत ही व्यावहारिक अनुप्रयोग है। उदाहरण के लिए, अंतर्राष्ट्रीय मानक पुस्तक संख्या (आईएसबीएन) त्रुटि का पता लगाने के लिए मॉडुलो 11 (10 अंकों के आईएसबीएन के लिए) या मॉड्यूलो 10 (13 अंकों के आईएसबीएन के लिए) अंकगणित का उपयोग करता है। इसी तरह, अंतर्राष्ट्रीय बैंक खाता संख्या (आईबीएएन), उदाहरण के लिए, बैंक खाता संख्या में उपयोगकर्ता इनपुट त्रुटियों को खोजने के लिए मॉडुलो 97 अंकगणितीय का उपयोग करें। रसायन विज्ञान में, CAS रजिस्ट्री संख्या का अंतिम अंक (प्रत्येक रासायनिक यौगिक के लिए एक विशिष्ट पहचान संख्या) एक चेक अंक है, जिसकी गणना CAS रजिस्ट्री संख्या के पहले दो भागों के अंतिम अंक को 1 से गुणा करके की जाती है, पिछला अंक गुणा 2, पिछला अंक 3 गुना आदि, इन सभी को जोड़कर और योग मॉड्यूलो 10 की गणना करना।

क्रिप्टोग्राफी में, मॉड्यूलर अंकगणित सार्वजनिक-कुंजी क्रिप्टोग्राफी सिस्टम जैसे आरएसए (एल्गोरिदम) और डिफी-हेलमैन कुंजी एक्सचेंज | डिफी-हेलमैन को सीधे आधार देता है, और परिमित क्षेत्र प्रदान करता है जो अण्डाकार वक्रों को रेखांकित करता है, और उन्नत सहित विभिन्न सममित कुंजी एल्गोरिदम में उपयोग किया जाता है। एन्क्रिप्शन मानक (AES), अंतर्राष्ट्रीय डेटा एन्क्रिप्शन एल्गोरिथम (IDEA), और RC4। आरएसए और डिफी-हेलमैन मॉड्यूलर घातांक का उपयोग करते हैं।

कंप्यूटर बीजगणित में, मॉड्यूलर अंकगणित आमतौर पर मध्यवर्ती गणना और डेटा में पूर्णांक गुणांक के आकार को सीमित करने के लिए उपयोग किया जाता है। इसका उपयोग बहुपद गुणनखंडन में किया जाता है, एक ऐसी समस्या जिसके लिए सभी ज्ञात कुशल एल्गोरिदम मॉड्यूलर अंकगणित का उपयोग करते हैं। इसका उपयोग पूर्णांकों और परिमेय संख्याओं पर बहुपद महानतम सामान्य भाजक, सटीक रैखिक बीजगणित और ग्रोबनेर आधार एल्गोरिदम के सबसे कुशल कार्यान्वयन द्वारा किया जाता है। जैसा कि 1980 के दशक में फिडोनेट पर पोस्ट किया गया था और रोसेटा कोड में संग्रहीत किया गया था, मॉड्यूलर अंकगणित का उपयोग एक सीडीसी 6600 सुपर कंप्यूटर द्वारा उपयोग किए गए पूर्णांक परिशुद्धता के केवल एक-चौथाई का उपयोग करके दो दशक पहले इसे अस्वीकार करने के लिए एक सिंक्लेयर क्यूएल माइक्रो कंप्यूटर पर यूलर की शक्तियों के योग का खंडन करने के लिए किया गया था। क्रूर बल खोज के माध्यम से।

कंप्यूटर विज्ञान में, मॉड्यूलर अंकगणित नि: शुल्क बिटवाइज़ संचालन और निश्चित-चौड़ाई, चक्रीय डेटा संरचनाओं से जुड़े अन्य कार्यों में लागू होता है। मॉडुलो ऑपरेशन, जैसा कि कई प्रोग्रामिंग भाषाओं और कैलकुलेटरों में लागू किया गया है, मॉड्यूलर अंकगणित का एक अनुप्रयोग है जो अक्सर इस संदर्भ में उपयोग किया जाता है। लॉजिकल ऑपरेटर एक्सओआर 2 बिट्स, मोडुलो 2 का योग करता है।

संगीत में, अंकगणित मोडुलो 12 का उपयोग बारह-स्वर समान स्वभाव की प्रणाली के विचार में किया जाता है, जहां सप्टक और सुरीले समतुल्यता होती है (अर्थात, 1:2 या 2:1 अनुपात में पिच समकक्ष हैं, और सी-शार्प ( संगीत) को डी-फ्लैट (संगीत) के समान माना जाता है)।

नाइन निकालने की विधि हाथ से निष्पादित दशमलव अंकगणितीय गणनाओं की त्वरित जांच प्रदान करती है। यह मॉड्यूलर अंकगणित मॉड्यूल 9 पर आधारित है, और विशेष रूप से 10 ≡ 1 (मॉड 9) की महत्वपूर्ण संपत्ति पर आधारित है।

अंकगणित मोडुलो 7 का उपयोग एल्गोरिदम में किया जाता है जो किसी निश्चित तिथि के लिए सप्ताह का दिन निर्धारित करता है। विशेष रूप से, ज़ेलर की सर्वांगसमता और प्रलय का दिन एल्गोरिथम मॉड्यूल -7 अंकगणित का भारी उपयोग करते हैं।

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

कम्प्यूटेशनल जटिलता

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

कुछ ऑपरेशन, जैसे असतत लघुगणक या द्विघात सर्वांगसमता पूर्णांक गुणनखंडन के समान कठिन प्रतीत होते हैं और इस प्रकार क्रिप्टोग्राफी और कूटलेखन के लिए एक प्रारंभिक बिंदु हैं। ये समस्याएं एनपी-मध्यवर्ती हो सकती हैं।

गैर-रैखिक मॉड्यूलर अंकगणितीय समीकरणों की एक प्रणाली को हल करना एनपी-पूर्ण है।

उदाहरण कार्यान्वयन

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

गणना करने का एक एल्गोरिथम तरीका $a\cdot b{\pmod {m}}$: <वाक्यविन्यास प्रकाश लैंग = सी> uint64_t mul_mod (uint64_t a, uint64_t b, uint64_t m) {

   if (!((a | b) & (0xFFFFFFFFFULL << 32))) a * b % m लौटाएं;

   uint64_t d = 0, mp2 = m >> 1;
   int मैं;
   अगर (ए> = एम) ए% = एम;
   अगर (बी> = एम) बी% = एम;
   के लिए (i = 0; i <64; ++i) {
       डी = (डी> एमपी 2)? (डी << 1) - एम: डी << 1;
       अगर (ए और 0x8000000000000000ULL) डी + = बी;
       अगर (डी> = एम) डी - = एम;
       ए <<= 1;
   }
   वापसी घ;

} </वाक्यविन्यास हाइलाइट>

कंप्यूटर आर्किटेक्चर पर जहां कम से कम 64 बिट्स मंटिसा के साथ एक विस्तारित परिशुद्धता # x86 विस्तारित प्रेसिजन प्रारूप प्रारूप उपलब्ध है (जैसे कि अधिकांश x86 सी कंपाइलर्स का लंबा डबल प्रकार), निम्न दिनचर्या लूप का उपयोग करके समाधान से तेज़ है, नियोजित करके चाल है कि, हार्डवेयर द्वारा, तैरनेवाला स्थल गुणन परिणाम उत्पाद के सबसे महत्वपूर्ण बिट्स में रखा जाता है, जबकि पूर्णांक गुणन परिणाम कम से कम महत्वपूर्ण बिट्स में रखा जाता है: <वाक्यविन्यास प्रकाश लैंग = सी> uint64_t mul_mod (uint64_t a, uint64_t b, uint64_t m) {

   लंबा डबल एक्स;
   uint64_t सी;
   int64_t आर;
   अगर (ए> = एम) ए% = एम;
   अगर (बी> = एम) बी% = एम;
   एक्स = ए;
   सी = एक्स * बी / एम;
   आर = (int64_t) (ए * बी - सी * एम)% (int64_t) एम;
   वापसी आर <0? आर + एम : आर;

}

</वाक्यविन्यास हाइलाइट>

मॉड्यूलर एक्सपोनेंटिएशन करने के लिए नीचे एक सी फ़ंक्शन है, जो इसका उपयोग करता है mul_mod समारोह ऊपर लागू किया गया।

गणना करने का एक एल्गोरिथम तरीका $a^{b}{\pmod {m}}$:

<वाक्यविन्यास प्रकाश लैंग = सी> uint64_t pow_mod (uint64_t a, uint64_t b, uint64_t m) {

   uint64_t आर = एम == 1? 0 : 1;
   जबकि (बी > 0) {
       अगर (बी और 1) आर = mul_mod (आर, ए, एम);
       बी = बी >> 1;
       ए = mul_mod (ए, ए, एम);
   }
   वापसी आर;

} </वाक्यविन्यास हाइलाइट>

हालाँकि, उपरोक्त सभी दिनचर्या के काम करने के लिए, m 63 बिट से अधिक नहीं होना चाहिए।

यह भी देखें

• बूलियन रिंग
• गोलाकार बफर
• डिवीजन (गणित)
• परिमित क्षेत्र
• लीजेंड्रे प्रतीक
• मॉड्यूलर घातांक
• मोडुलो (गणित)
• पूर्णांक मॉड्यूलो n का गुणक समूह
• पिसानो अवधि (फाइबोनैचि अनुक्रम मॉड्यूलो एन)
• आदिम रूट मॉड्यूलो एन
• द्विघात पारस्परिकता
• द्विघात अवशेष
• तर्कसंगत पुनर्निर्माण (गणित)
• कम अवशेष प्रणाली
• सीरियल नंबर अंकगणित (मॉड्यूलर अंकगणित का एक विशेष मामला)
• दो-तत्व बूलियन बीजगणित
• मॉड्यूलर अंकगणित के पीछे समूह सिद्धांत से संबंधित विषय:
  • चक्रीय समूह
  • पूर्णांक मॉड्यूलो n का गुणक समूह
• मॉड्यूलर अंकगणित से संबंधित अन्य महत्वपूर्ण प्रमेय:
  • कारमाइकल फंक्शन | कारमाइकल की प्रमेय
  • चीनी शेष प्रमेय
  • यूलर प्रमेय
  • फ़र्मेट की छोटी प्रमेय (यूलर की प्रमेय का एक विशेष मामला)
  • लैग्रेंज की प्रमेय (समूह सिद्धांत) | लैग्रेंज की प्रमेय
  • थ्यू की लेम्मा

संदर्भ

• John L. Berggren. "modular arithmetic". Encyclopædia Britannica.
• Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001. See in particular chapters 5 and 6 for a review of basic modular arithmetic.
• Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany"
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868.
• Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. ISBN 0-486-41449-3.
• Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd ed.). Lexington: D. C. Heath and Company. LCCN 77171950.
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. ISBN 9780132683005. LCCN 71081766.
• Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123.

बाहरी संबंध

• "Congruence", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• In this modular art article, one can learn more about applications of modular arithmetic in art.
• An article on modular arithmetic on the GIMPS wiki
• Modular Arithmetic and patterns in addition and multiplication tables