മോഡ്യുലർ അങ്കഗണിതം

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/Modular_arithmetic

പൂർണ്ണസംഖ്യകളിൽ സംക്രിയകൾ ചെയ്യുമ്പോൾ ലഭിക്കുന്ന ഫലം ഒരു നിശ്ചിത വിലയ്ക്കു മുകളിലെത്തിയാൽ അതിനെ പൂജ്യമായി കണക്കാക്കി അതിനു മുകളിലുള്ള വ്യത്യാസം മാത്രമെടുക്കുന്ന അങ്കഗണിത രീതിയാണ് മോഡ്യുലർ അങ്കഗണിതം (modular arithmetic). ഈ ഉയർന്ന നിശ്ചിത വിലയെ മാപാങ്കം (modulus) എന്നു വിളിക്കുന്നു. മോഡ്യുലർ അങ്കഗണിതത്തിന്റെ ആധുനികരൂപം വികസിപ്പിച്ചത് 1801-ൽ ഡിസ്ക്വിസിഷനെസ് അരിത്മെറ്റികേ എന്ന ഗ്രന്ഥത്തിൽ കാൾ ഫ്രഡറിക് ഗോസ് ആയിരുന്നു.

സമയവുമായി ബന്ധപ്പെട്ട അങ്കഗണിതത്തിൽ ആറുമണിയോട് എട്ടു മണിക്കൂർ കൂട്ടിയാൽ രണ്ടുമണിയാവുന്നത് സാധാരണ ഗതിയിൽ മാപാങ്കം 12 ആയുള്ള മോഡ്യുലർ അങ്കഗണിതം ചെയ്യുന്നതിനാലാണ് (മാപാങ്കം 24 വരുന്ന രീതിയിലും ചെയ്യാറുണ്ട്). സാധാരണ അങ്കഗണിതത്തിൽ 6 + 8 = 14 ആണെങ്കിലും പതിനാലുമണി എന്ന് പറയാത്തത് ഓരോ പന്ത്രണ്ട് മണിക്കൂറീലും സമയത്തിന്റെ വില ചുറ്റി വരുന്നതിനാലാണ് (wrap around). 12 എന്നത് പൂജ്യത്തോടും സർവ്വസമമായതിനാൽ "12:00" എന്ന സമയത്തെ "0:00" എന്നും പറയാം.

സങ്കലനം, വ്യവകലനം, ഗുണനം എന്ന സംക്രിയകൾ സാധാരണ പൂർണ്ണസംഖ്യകളെപ്പോലെത്തന്നെ ചെയ്യാവുന്ന രീതിയിൽ ഒരു സർവ്വസമതാ ബന്ധത്തിന്റെ (congruence relation) നിർവചനമാണ് മോഡ്യുലർ അങ്കഗണിതത്തിന് അടിസ്ഥാനം. n ഒരു പൂർണ്ണസംഖ്യയാണെങ്കിൽ a, b എന്ന പൂർണ്ണസംഖ്യകൾ congruent modulo n ആണെന്നു പറയുന്നത് അവയുടെ വ്യത്യാസമായ a − b എന്നത് n ന്റെ പൂർണ്ണസംഖ്യാഗുണിതമാവുമ്പോഴാണ്. അതായത്, a − b = kn എന്ന സമവാക്യമനുസരിക്കുന്ന k എന്ന പൂർണ്ണസംഖ്യയുണ്ടാകണം. a യും b യും പൂർണ്ണസംഖ്യകളാകുമ്പോഴാണ് ഈ സർവ്വസമത സാധാരണ ഉപയോഗിക്കാറുള്ളത്, ഇതിനെ

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

എന്ന് സൂചിപ്പിക്കുന്നു. n നെ സർവ്വസമതയുടെ മാപാങ്കം (modulus) എന്നു വിളിക്കുന്നു.

യൂക്ലിഡിയൻ ഹരണവുമായുള്ള ബന്ധം വ്യക്തമാക്കാൻ

${\displaystyle a=kn+b}$

എന്ന രൂപത്തിലും സർവ്വസമതയെ എഴുതാവുന്നതാണ്. എന്നാൽ b എന്നത് a യെ n കൊണ്ട് ഹരിച്ചാൽ ലഭിക്കുന്ന ശിഷ്ടം തന്നെയായിരിക്കണമെന്ന് നിർബന്ധമില്ല. കൃത്യമായി പറഞ്ഞാൽ, a ≡ b mod n എന്ന സർവ്വസമത പറയുന്നത് a യെയും b യെയും n കൊണ്ടു ഹരിച്ചാൽ കിട്ടുന്ന ശിഷ്ടങ്ങൾ തുല്യമാണെന്നാണ്. അതായത്,

${\displaystyle a=pn+r,}$

${\displaystyle b=qn+r,}$

ഇവിടെ 0 ≤ r < n തുല്യമായ ശിഷ്ടമാണ്. ഈ സമവാക്യങ്ങളുടെ വ്യത്യാസം കണ്ടാൽ നേരത്തെപ്പോലെ:

${\displaystyle a-b=kn,}$

എന്നു ലഭിക്കുന്നു (k = p − q).

ഉദാഹരണമായി,

${\displaystyle 38\equiv 14{\pmod {12}}\,.}$

38 − 14 = 24 എന്നത് 12 ന്റെ ഗുണിതമായതിനാലാണിത്. 38 നെയും 14 നെയും 12 കൊണ്ട് ഹരിച്ചാൽ ശിഷ്ടം 2 വരുന്നതിനാലാണ് എന്നും പറയാം.

ന്യൂനസംഖ്യകൾക്കും ഇതേ നിയമം ബാധകമാണ്:

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

ഒരേ പ്രശ്നത്തിൽ തന്നെ ഒന്നിലേറെ മാപാങ്കങ്ങൾ പലപ്പോഴും ഉപയോഗിക്കേണ്ടി വരുന്നതിനാൽ ആശയക്കുഴപ്പമൊഴിവാക്കാനാണ് ചിഹ്നത്തിൽ തന്നെ മാപാങ്കം വ്യക്തമാക്കുന്നത്. എന്നിരുന്നാലും ഒരു നിശ്ചിത മാപാങ്കത്തിന് സർവ്വസമത ഒരു ദ്വയാങ്ക ബന്ധമാണ് (ത്രയാങ്ക ബന്ധമായി കണക്കാക്കില്ല)

സർവ്വസമതാ ബന്ധം തുല്യതാബന്ധത്തിന്റെ (equivalence relation) എല്ലാ നിയമങ്ങളും പാലിക്കുന്നു:

• പ്രതിസമത: a ≡ a (mod n)
• സമമിതി: a ≡ b (mod n) ആകുന്നത് കൃത്യം b ≡ a (mod 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), എന്ന സർവ്വസമതകൾ സാധുവാണെങ്കിൽ താഴെക്കൊടുത്തിരിക്കുന്നവയും സാധുവാകും:

• k ഒരു പൂർണ്ണസംഖ്യയാണെങ്കിൽ a + k ≡ b + k (mod n) (നീക്കവുമായുള്ള പൊരുത്തം)
• k ഒരു പൂർണ്ണസംഖ്യയാണെങ്കിൽ k a ≡ k b (mod n)(scaling ഉമായുള്ള പൊരുത്തം)
• a₁ + a₂ ≡ b₁ + b₂ (mod n) (സങ്കലനവുമായുള്ള പൊരുത്തം)
• a₁ – a₂ ≡ b₁ – b₂ (mod n) (വ്യവകലനവുമായുള്ള പൊരുത്തം)
• a₁ a₂ ≡ b₁ b₂ (mod n) (ഗുണനവുമായുള്ള പൊരുത്തം)
• k പൂജ്യത്തിൽ കുറയാത്ത ഒരു പൂർണ്ണസംഖ്യയാണെങ്കിൽ a^k ≡ b^k (mod n) (ഘാതവുമായുള്ള പൊരുത്തം)
• p(x) പൂർണ്ണസംഖ്യാഗുണോത്തരങ്ങളുള്ള ബഹുപദമാണെങ്കിൽ p(a) ≡ p(b) (mod n) (ബഹുപദങ്ങളുടെ മൂല്യനിർണ്ണയത്തിലെ പൊരുത്തം)

a ≡ b (mod n) ആയതുകൊണ്ടു മാത്രം k^a ≡ k^b (mod n) ആകണമെന്നില്ല. എന്നാൽ:

• c ≡ d (mod φ(n)) ആണെങ്കിൽ (ഇവിടെ φ ഓയ്‌ലറുടെ ടോഷ്യന്റ് ഫലനമ്മാണ്) a, n എന്നിവ സഹ-അഭാജ്യമാകുമ്പോൾ a^c ≡ a^d (mod n) എന്നു വരുന്നു.

പൊതുവായ പദങ്ങളെ ഒഴിവാക്കാനുള്ള നിയമങ്ങൾ:

• k ഒരു പൂർണ്ണസംഖ്യയാണെങ്കിൽ a + k ≡ b + k (mod n) ആകുമ്പോഴൊക്കെ a ≡ b (mod n) ആണ്
• k, n എന്നിവ സഹ-അഭാജ്യമായ പൂർണ്ണസംഖ്യകളാണെങ്കിൽ k a ≡ k b (mod n) ആകുമ്പോഴൊക്കെ a ≡ b (mod n) ആണ്

മോഡ്യുലർ ഗുണനവിപരീതത്തിന്റെ നിയമങ്ങൾ:

• അസ്തിത്വം: a, n എന്നിവ സഹ-അഭാജ്യമാവുന്ന അവസരങ്ങളിൽ aa^–1 ≡ 1 (mod n) എന്ന സർവ്വസമതയനുസരിക്കുന്ന a^–1 എന്ന പൂർണ്ണസംഖ്യയുണ്ടാകും. a^–1 നെയാണ് a യുടെ മോഡ്യുലോ n ആയുള്ള മോഡ്യുലർ ഗുണനവിപരീതം (modular multiplicative inverse) എന്നു വിളിക്കുന്നത്.
• a ≡ b (mod n) ആവുകയും a^–1 ഉണ്ടായിരിക്കുകയും ചെയ്താൽ a^–1 ≡ b^–1 (mod n) (ഗുണനവിപരീതവുമായുള്ള പൊരുത്തം)
• a x ≡ b (mod n) ആവുകയും a, n എന്നിവ സഹ-അഭാജ്യമായിരിക്കുകയും ചെയ്താൽ ഈ രേഖീയ സർവ്വസമതയുടെ പരിഹാരം x ≡ a^–1b (mod n) ആണ്.

p ഒരു അഭാജ്യസംഖ്യയും a അതിൽ ചെറിയതും (0 < a < p) അതിനോട് സഹ-അഭാജ്യവുമായ ഒരു പൂർണ്ണസംഖ്യയുമാണെങ്കിൽ a യ്ക്ക് ഒരു ഗുണനവിപരീതമുണ്ടാകുമെന്ന് ഇതിൽ നിന്നും കാണാം.

• 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. LCCN 71081766.
• Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123.

സംഖ്യാസിദ്ധാന്തവുമായി ബന്ധപ്പെട്ട ഈ ലേഖനം അപൂർണ്ണമാണ്‌. ഇതു വികസിപ്പിക്കുവാൻ സഹായിക്കുക.