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

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 सह अभाज्य हैं, तो 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: 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