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

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

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

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

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

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

ചരിത്രം

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

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

“ കൃത്യമായി എണ്ണം അറിയാത്ത ചില വസ്തുക്കളുണ്ട്. അവയെ മൂന്നെണ്ണം വീതമെടുത്താൽ രണ്ട് ബാക്കി വരും; അഞ്ചെണ്ണം വീതമെടുത്താൽ മൂന്നും ഏഴെണ്ണം വീതമെടുത്താൽ രണ്ടും ബാക്കിയാകും. എങ്കിൽ ആകെ എത്ര വസ്തുക്കളാണുള്ളത്? ”

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

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

പ്രമേയം

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

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

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

${\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}$

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

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

$x\ \operatorname {mod} N\;\mapsto \;(x\ \operatorname {mod} n_{1},\,\ldots ,\,x\ \operatorname {mod} n_{k})$

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

$\mathbb {Z} /N\mathbb {Z} \cong \mathbb {Z} /n_{1}\mathbb {Z} \times \cdots \times \mathbb {Z} /n_{k}\mathbb {Z}$

എന്ന വലയ സമരൂപത നിർവചിക്കുന്നു. $\mathbb {Z} /N\mathbb {Z}$ ൽ ക്രിയകൾ ചെയ്യുന്നതിനു പകരം $\mathbb {Z} /n_{i}\mathbb {Z}$ ൽ ക്രിയകൾ ചെയ്ത് ഒടുവിൽ സമരൂപതയുപയുപയോഗിച്ച് ഫലം കാണാമെന്ന് ഇതിൽ നിന്ന് മനസ്സിലാക്കം. N ഉം ക്രിയകളുടെ എണ്ണവും വലുതാണെങ്കിൽ നേരിട്ട് കണക്കുകൂട്ടുന്നതിനെക്കാൾ വേഗത്തിൽ ഈ രീതിയിൽ ഫലം ലഭിച്ചേക്കാം. പൂർണ്ണസംഖ്യകൾക്കോ ഭിന്നകസംഖ്യകൾക്കോ മേൽ രേഖീയ ബീജഗണിതത്തിൽ മൾട്ടി-മോഡ്യുലർ കണക്കുകൂട്ടലുകൾ നടത്താൻ ഇത് വ്യാപകമായി ഉപയോഗിക്കുന്നു.

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

ഗ്രന്ഥസൂചി

• Dauben, Joseph W. (2007), "Chapter 3: Chinese Mathematics", in Katz, Victor J. (ed.), The Mathematics of Egypt, Mesopotamia, China, India and Islam : A Sourcebook, Princeton University Press, pp. 187–384, ISBN 978-0-691-11485-9
• Duchet, Pierre (1995), "Hypergraphs", in Graham, R. L.; Grötschel, M.; Lovász, L. (eds.), Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, pp. 381–432, MR 1373663. See in particular Section 2.5, "Helly Property", pp. 393–394.
• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected ed.), New York: Springer, ISBN 978-0-387-96254-2 {{citation}}: |first2= has generic name (help)
• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd ed.), Springer-Verlag, ISBN 0-387-97329-X
• Kak, Subhash (1986), "Computational aspects of the Aryabhata algorithm" (PDF), Indian Journal of History of Science, 21 (1): 62–71
• Katz, Victor J. (1998), A History of Mathematics / An Introduction (2nd ed.), Addison Wesley Longman, ISBN 978-0-321-01618-8
• Ore, Oystein (1988) [1948], Number Theory and Its History, Dover, ISBN 978-0-486-65620-5
• Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, ISBN 978-0201-57889-8