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

This article is about (mod n) अंकन. For द्विआधारी संक्रिया mod(a,n), see मोडुलो ऑपरेशन.

इस घड़ी पर टाइम-कीपिंग अंकगणित मापांक 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 सह अभाज्य हैं, तो a ^φ(n) ≡ 1 (mod n), जहाँ पे φ यूलर का कुल फलनहै
• फ़र्मेट की छोटी प्रमेय का सरल परिणाम यह है कि अगर p अभाज्य है, तो a⁻¹ ≡ a ^{p − 2} (mod p) का गुणक व्युत्क्रम है 0 < a < p. अधिक सामान्यतः, यूलर के प्रमेय से, यदि a तथा n सह अभाज्य हैं, तो 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: लघुकृत अवशेष प्रणाली

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

पूर्णांक मापांक एन

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

समुच्चय को 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 भागफल समूह $\mathbb {Z} /n\mathbb {Z}$, चक्रीय समूह का समूह सहसमुच्चय a है।।

विशेष मामले 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}$(जहाँ a, n का सह-अभाज्य है) सम्मिलित है, जो वास्तव में गुणक रखने वाले वर्ग हैं। यह गुणन के अंतर्गत एक क्रमविनिमेय समूह (गणित) बनाता है, जिसका क्रम $\varphi (n)$ होता है।

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

See also: मोडुलो ऑपरेशन

अनुप्रयोग

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

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

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

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

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

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

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

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

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

अभिकलनात्मक जटिलता

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

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

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

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

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

गणना करने का कलन विधि तरीका $a\cdot b{\pmod {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 सी संकलनकर्ता का लंबा डबल प्रकार),निम्नलिखित दिनचर्या लूप का उपयोग करके समाधान से तेज है, चाल को नियोजित करके हार्डवेयर, फ़्लोटिंग-पॉइंट गुणन परिणाम उत्पाद के सबसे महत्वपूर्ण बिट्स में रखा जाता है, जबकि पूर्णांक गुणन के परिणामस्वरूप कम से कम महत्वपूर्ण बिट्स रखे जाते हैं: <वाक्यविन्यास प्रकाश लैंग = सी> uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {

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

}

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

मापांक घातांक करने के लिए नीचे C अभिलक्षक है, जो इसका उपयोग करता है 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
• द्विघात पारस्परिकता
• द्विघात अवशेष
• तर्कसंगत पुनर्निर्माण (गणित)
• कम अवशेष प्रणाली
• क्रम संख्या अंकगणित (मापांक अंकगणित का एक विशेष मामला)
• दो-तत्व बूलियन बीजगणित
• मापांक अंकगणित के पीछे समूह सिद्धांत से संबंधित विषय:
  • चक्रीय समूह
  • पूर्णांक मापांक 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