ചൈനീസ് ശിഷ്ട പ്രമേയം

(Chinese remainder theorem എന്ന താളിൽ നിന്നും തിരിച്ചുവിട്ടതു പ്രകാരം)

സംഖ്യാസിദ്ധാന്തത്തിലെ ഒരു പ്രമേയമാണ് ചൈനീസ് ശിഷ്ട പ്രമേയം (Chinese remainder theorem). ഒരു കൂട്ടം പൂർണ്ണസംഖ്യകളിലെ ഓരോ ജോടിയും സഹ-അഭാജ്യമാണെന്ന് കരുതുക. n എന്ന പൂർണ്ണസംഖ്യയെ ഒരു കൂട്ടത്തിലെ സംഖ്യകളിലോരോന്നിനെക്കൊണ്ടും യൂക്ലിഡിയൻ ഹരണം നടത്തിയാൽ കിട്ടുന്ന ശിഷ്ടങ്ങൾ ഉപയോഗിച്ച് n നെ കൂട്ടത്തിലെ സംഖ്യകളുടെ ഗുണനഫലം കൊണ്ട് ഹരിച്ചാൽ കിട്ടുന്ന ശിഷ്ടം കണക്കാക്കാമെന്ന് ചൈനീസ് ശിഷ്ട പ്രമേയം പറയുന്നു.

സുൻത്സി യുടെ മൂല പ്രശ്നം: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) എന്നിവയുടെ നിർദ്ധാരണമായ x = 23 + 105k, ഇവിടെ k ∈ ℤ ആണ്.

മൂന്നാം നൂറ്റാണ്ടിൽ ചൈനീസ് ഗണിതശാസ്ത്രജ്ഞനായ സുൻത്സി ആണ് സുൻത്സി സുവാൻജിങ് എന്ന ഗ്രന്ഥത്തിൽ ആദ്യമായി ഈ പ്രമേയം പ്രസിദ്ധീകരിച്ചതായി നമുക്ക് അറിവുള്ളത്. വലിയ സംഖ്യകൾക്കു മേലുള്ള കണക്കുകൂട്ടലുകളെ ചെറിയ സംഖ്യകൾക്കു മേലുള്ള അനേകം കണക്കുകൂട്ടലുകളായി മാറ്റി ഇവ എളുപ്പത്തിൽ നടത്താൻ ചൈനീസ് ശിഷ്ട പ്രമേയം സഹായിക്കുന്നു. മോഡ്യുലർ അങ്കഗണിതത്തിലെ സർവ്വസമതകളുടെ രൂപത്തിൽ എഴുതിയാൽ ചൈനീസ് ശിഷ്ട പ്രമേയം പ്രിൻസിപൽ ഗുണജ മണ്ഡലങ്ങളിലെല്ലാം സാധുവാണ്. ഗുണജങ്ങൾ ഉപയോഗിച്ച് ക്രമവിനിമേയ വലയങ്ങൾക്കായും ഇത് സാമാന്യവൽക്കരിക്കാം.

ചരിത്രം

തിരുത്തുക
 
ചാൾസ് ഫ്രഡറിക് ഗോസിന്റെ 1801-ൽ പുറത്തിറങ്ങിയ ഡിസ്ക്വിസിഷനസ് അരിത്മെറ്റികേ എന്ന ഗ്രന്ഥത്തിൽ ചൈനീസ് ശിഷ്ട പ്രമേയം പ്രത്യക്ഷപ്പെടുന്നു.[1]

മൂന്നാം നൂറ്റാണ്ടിലെ സുൻത്സിയുടെ സുൻത്സി സുവാൻജിങ് എന്ന ഗ്രന്ഥത്തിലാണ് പ്രമേയത്തിന്റെ അറിയപ്പെടുന്നതിൽ ആദ്യത്തെ രൂപം കാണാനാകുന്നത്. എന്നാൽ ഇത് പ്രമേയത്തിന്റെ സാമാന്യരൂപമല്ല, ചില നിശ്ചിതസംഖ്യകളെക്കുറിച്ചുള്ള ചോദ്യം മാത്രമായിരുന്നു:[2]

സുൻത്സിയുടെ രചനകളിൽ പ്രമേയത്തിന്റെ തെളിവോ ഒരു പൂർണ്ണ അൽഗൊരിതമോ അടങ്ങിയിട്ടില്ല..[4] ഈ പ്രശ്നത്തിന് പരിഹാരം കാണാനുള്ള അൽഗൊരിതം ആറാം നൂറ്റാണ്ടിൽ ആര്യഭടൻ വിവരിച്ചു.[5] ഏഴാം നൂറ്റാണ്ടിൽ ബ്രഹ്മഗുപ്തനും ചൈനീസ് ശിഷ്ട പ്രമേയത്തിന്റെ ചില നിശ്ചിതരൂപങ്ങൾ അറിയാമായിരുന്നു, ഫിബനാച്ചിയുടെ ലിബർ അബാസിയിൽ (1202) ഇവ പ്രത്യക്ഷപ്പെടുന്നുമുണ്ട്.[6] ദയാൻഷു (大衍術) എന്ന പേരിൽ ചൈനീസ് ശിഷ്ട പ്രമേയത്തിന്റെ പൂർണ്ണ നിർദ്ധാരണം ക്വിൻ ജിയുഷാവോ 1247-ൽ ഷുഷു ജിയുഷാങ് (數書九章‌) എന്ന ഗ്രന്ഥത്തിൽ പ്രസിദ്ധീകരിച്ചു.[7]

സർവ്വസമതകൾ എന്ന ആശയം ആദ്യമായി മുന്നോട്ടുവച്ചതും ഉപയോഗിച്ചതും ഡിസ്ക്വിഷനസ് അരിത്മെറ്റികേ എന്ന 1801-ലെ തന്റെ ഗ്രന്ഥത്തിൽ ഗോസ് ആയിരുന്നു.[8] സൗര-ചാന്ദ്ര കലൻഡറുകളും റോമൻ ഇൻഡിക്ഷനും ചാക്രികമായി വരുന്ന വർഷങ്ങൾ കണ്ടെത്തുന്ന പ്രശ്നമാണ് ഗോസ് ഇതിനുദാഹരണമായി കൊടുത്തത്."[9] മുമ്പ് ഓയ്ലർ ഉപയോഗിച്ചതും എന്നാൽ അതിനും മുമ്പ് പലയിടങ്ങളിലായി പ്രസിദ്ധീകരിക്കപ്പെട്ടതുമായ ഒരു രീതിയാണ് ഗോസ് ഇത്തരം പ്രശ്നങ്ങളുടെ നിർദ്ധാരണത്തിനായി മുന്നോട്ടുവച്ചത്.[10]

പ്രമേയം

തിരുത്തുക

n1, ..., ni , ..., nk എന്നിവ 1നെക്കാൾ വലിയ പൂർണ്ണസംഖ്യകളാണെന്നിരിക്കട്ടെ. ഇവയെ മാപാങ്കങ്ങൾ (modulus) അഥവാ ഹാരകങ്ങൾ (divisors) എന്ന് വിളിക്കുന്നു. ni യുടെ ഗുണനഫലത്തെ N കൊണ്ട് സൂചിപ്പിക്കുക.

ni കളിൽ ഏത് രണ്ടെണ്ണമെടുത്താലും അവ സഹ-അഭാജ്യമാവുകയും a1, ..., ak എന്നിവ 0 ≤ ai < ni എന്ന അസമതകളനുസരിക്കുന്ന പൂർണ്ണസംഖ്യകളാവുകയും ചെയ്താൽ 0 ≤ x < N എന്ന അസമതയനുസരിക്കുന്നതും x നെ ഓരോ ni കൊണ്ട് ഹരിച്ചാലും ai ശിഷ്ടം വരുന്നതുമായ അനന്യമായ x എന്ന പൂർണ്ണസംഖ്യയുണ്ടായിരിക്കും എന്നാണ് ചൈനീസ് ശിഷ്ട പ്രമേയ്യം പറയുന്നത്.

സർവ്വസമതാ ബന്ധങ്ങളുടെ ഭാഷയിൽ ഇങ്ങനെ പറയാം: ni ഈരണ്ടെണ്ണം വീതമെടുത്താൽ സഹ-അഭാജ്യമായ സംഖ്യകളാവുകയും a1, ..., ak എന്നിവ പൂർണ്ണസംഖ്യകളാവുകയും ചെയ്താൽ

 

എന്ന സർവ്വസമതാബന്ധങ്ങളൊക്കെയും അനുസരിക്കുന്ന x എന്ന പൂർണ്ണസംഖ്യയുണ്ടായിരിക്കും. ഇങ്ങനത്തെ ഏത് രണ്ട് പൂർണ്ണസംഖ്യകളും മോഡ്യുലോ N സർവ്വസമമായിരിക്കുകയും ചെയ്യും.[11]

അമൂർത്ത ബീജഗണിതത്തിൽ ഇപ്രകാരം എഴുതാം: ni യിലെ സംഖ്യകൾ പരസ്പരം സഹ-അഭാജ്യമാണെങ്കിൽ

 

എന്ന പ്രതിചിത്രണം ഒരു മോഡ്യുലോ N ആയ പൂർണ്ണസംഖ്യകളുടെ വലയത്തിനും മോഡ്യുലോ ni ആയ പൂർണ്ണസംഖ്യകളുടെ വലയങ്ങളുടെ direct ഗുണനഫലത്തിനും ഇടയിലുള്ള

 

എന്ന വലയ സമരൂപത നിർവചിക്കുന്നു.[12]   ൽ ക്രിയകൾ ചെയ്യുന്നതിനു പകരം   ൽ ക്രിയകൾ ചെയ്ത് ഒടുവിൽ സമരൂപതയുപയുപയോഗിച്ച് ഫലം കാണാമെന്ന് ഇതിൽ നിന്ന് മനസ്സിലാക്കം. N ഉം ക്രിയകളുടെ എണ്ണവും വലുതാണെങ്കിൽ നേരിട്ട് കണക്കുകൂട്ടുന്നതിനെക്കാൾ വേഗത്തിൽ ഈ രീതിയിൽ ഫലം ലഭിച്ചേക്കാം. പൂർണ്ണസംഖ്യകൾക്കോ ഭിന്നകസംഖ്യകൾക്കോ മേൽ രേഖീയ ബീജഗണിതത്തിൽ മൾട്ടി-മോഡ്യുലർ കണക്കുകൂട്ടലുകൾ നടത്താൻ ഇത് വ്യാപകമായി ഉപയോഗിക്കുന്നു.

സഞ്ചയനശാസ്ത്രത്തിന്റെ ഭാഷയിൽ പൂർണ്ണസംഖ്യകളുടെ സമാന്തരശ്രേണികൾ ഒരു ഹെല്ലി കുടുംബമാണെന്നും പറയാം.[13]

  1. Gauss & Clarke 1986, Art. 32–36
  2. Katz 1998, p. 197
  3. Joseph B. Dence, Thomas P. Dence. "Elements of the Theory of Numbers". Retrieved 28 August 2016.
  4. Dauben 2007, p. 302
  5. Kak 1986
  6. Leonardo Pisano; Sigler, Laurence E. (translator into English) (2002), Fibonacci's Liber Abaci, Springer-Verlag, pp. 402–403, ISBN 0-387-95419-8 {{citation}}: |first2= has generic name (help)
  7. Dauben 2007, p. 310
  8. Ireland & Rosen 1990, p. 36
  9. Ore 1988, p. 247
  10. Ore 1988, p. 245
  11. Ireland & Rosen 1990, p. 34
  12. Ireland & Rosen 1990, p. 35
  13. Duchet 1995

ഗ്രന്ഥസൂചി

തിരുത്തുക
"https://ml.wikipedia.org/w/index.php?title=ചൈനീസ്_ശിഷ്ട_പ്രമേയം&oldid=3068924" എന്ന താളിൽനിന്ന് ശേഖരിച്ചത്