cyanic-selkie/wikianc huggingface dataset:
വിശ്വ ഹിന്ദു പരിഷത്ത്
ചരിത്രം
ആ സമ്മേളനത്തിൽ സംഘടനയുടെ പേര് വിശ്വ ഹിന്ദു പരീഷത്ത് എന്ന് തീരുമാനിക്കുകയും ലോകത്തിലെ ഹിന്ദുക്കളുടെ ഒത്തുചേരലായ കുംഭമേള സമയത്ത്, 1996-ൽ അലഹാബാദിൽ വച്ച് സംഘടന നിലവിൽ വരുത്താനും തീരുമാനിച്ചു. കൂടാതെ, സംഘടന ഒരു രാഷ്ട്രീയേതര സംഘടയാക്കാനും മറ്റു രാഷ്ട്രീയ പാർട്ടികളിൽ സ്ഥാനം വഹിക്കുന്നവർക്ക് വി.എച്.പിയിൽ ഒരേ സമയം സ്ഥാനം പാടില്ല എന്നും തീരുമാനമെടുത്തു. സംഘടനയുടെ ലക്ഷ്യങ്ങളായി തീരുമാനിക്കപ്പെട്ടത്‌,
അയോധ്യാ വിവാദം
രാമജന്മഭൂമി-ബാബറി മസ്ജിദ്‌ തർക്കമന്ദിരത്തിന്റെ സ്ഥാനത്ത് ക്ഷേത്രം പണിയാനുള്ള 20 വർഷത്തോളം നീണ്ടു നിന്ന പ്രക്ഷോഭങ്ങൾക്ക് ശേഷം 1992-ൽ തകർത്ത സംഭവത്തിൽ വി.എച്.പിയും പങ്കാളികളായിരുന്നു. ശ്രീരാമൻറെ ജന്മഭൂമിയിൽ നിലനിന്നിരുന്ന ക്ഷേത്രം തകർത്താണ് ബാബറി മസ്ജിദ് നിർമ്മിച്ചത്‌ എന്ന് വി.എച്.പി നിലപാടെടുത്തു. 1980-ന്റെ അവസാനം ഈ വിഷയം രാജ്യത്തിന്റെ രാഷ്ട്രീയ വിഷയമാക്കി ബി.ജെ.പ്പിയും വി.എച്.പിയും രാജ്യത്തുടനീളം പ്രക്ഷോഭങ്ങൾ സംഘടിപ്പിച്ചു. ഈ വിഷയം രാജ്യത്തിലെ കോടതികളും പ്രധാന രാഷ്ട്രീയ കക്ഷിയായ കോണ്ഗ്രസും ഉപേക്ഷിച്ചിരിക്കുകയാണ് എന്നായിരുന്നു വി.എച്.പി നിലപാടെടുത്തത്. 1992 ഡിസംബർ 6-ന് വി.എച്.പി ഉൾപ്പെടുന്ന ഹിന്ദു സംഘടനകൾ തർക്കസ്ഥലത്ത് കർസേവക്കായി ഒത്തുകൂടുകയും പ്രക്ഷോഭകരിലെ ഒരു വിഭാഗം ഹിന്ദുക്കൾ തർക്ക മന്ദിരം തകർക്കുകയും ചെയ്തു. രാജ്യത്തിൽ തുടർന്ന് നിരവധി കലാപങ്ങൾ അരങ്ങേറുകയും 2000-നടുത്ത് ആളുകൾ കൊല്ലപ്പെടുകയും ചെയ്തു.
ആദർശങ്ങളും ലക്ഷ്യങ്ങളും
സംഘടനയുടെ പ്രഖ്യാപിത ലക്ഷ്യങ്ങൾ ഇവയാണ് :
വി.എച്.പി ഉയർത്തുന്ന മറ്റു ആവശ്യങ്ങൾ ഇവയാണ്,
ഹിന്ദൂയിസത്തിൻറെ അർത്ഥം
മറ്റു സംഘപരിവാർ സംഘടനകളെപ്പോലെ ഹിന്ദു എന്നാൽ ഇന്ത്യൻ ജനതയെയും ഹിന്ദുധർമ്മം എന്നാൽ ഭാതത്തിൽ നിന്നും ഉത്ഭവിച്ച ബുദ്ധ, ജൈന, സിഖ് വിശ്വാസങ്ങളെ ഉൾക്കൊള്ളുന്നതുമാണ് എന്നാണ് വി.എച്.പി വ്യാഖ്യാനിക്കുന്നത്.
ഹിന്ദൂയിസത്തിൽ നിന്നുള്ള പരിവർത്തനം
ഭാരതത്തിൻറെ വെളിയിൽ നിന്നും എത്തിയ മതങ്ങൾ ഭാരതത്തിലെ ധർമ്മങ്ങളെയും വിശ്വാസങ്ങളെയും ഇല്ലാതാക്കാനും അവഹേളിക്കാൻ ശ്രമിക്കുന്നുവെന്നും വി.എച്.പി അവകാശപ്പെടുന്നു. ക്രിസ്ത്യൻ മിഷനറിമാരും മുസ്ലീം സംഘടനകളും ഹിന്ദുക്കളെ കൂട്ടമായി മതം മാറ്റിക്കാനായി പ്രവർത്തിക്കുന്നു എന്നും അതിനായി വിദേശത്ത് നിന്നും പണം ഒഴുക്കുന്നു എന്നും അവകാശപ്പെടുന്നു. ഇത്തരം നിർബന്ധിത പരിവർത്തനങ്ങളെ തടയുന്നത് കൂടാതെ മുസ്ലീങ്ങളെയും ക്രിസ്ത്യാനികളെയും ഹിന്ദൂയിസത്തിലേക്ക് തിരിച്ചു കൊണ്ടുവരുന്ന പ്രവർത്തനങ്ങളിൽ ഏർപ്പെടുകയും വി.എച്.പി ചെയ്യുന്നു. ഇന്ത്യയിലെ ക്രിസ്ത്യാനികളും മുസ്ലീങ്ങളും ഹിന്ദുക്കളിൽ നിന്നും മതപരിവർത്തനം നടത്തിയതാണ് എന്നാണ് വി.എച്.പി വിലയിരുത്തിയിരിക്കുന്നത്.
സംഘടന
വി.എച്.പി രാജ്യത്തിന്റെ വിവിധ ഭാഗങ്ങളിൽ ശാഖകളിലൂടെ സംഘടിക്കുന്നു. ജനാധിപത്യരീതി പിന്തുടരുന്ന ഈ ദേശീയ സംഘടനയുടെ പ്രസിഡന്റ്‌, ജനറൽ സെക്രട്ടറി എന്നിവയാണ് ഉയർന്ന സ്ഥാനങ്ങൾ. എങ്കിലും മുതിർന്ന നേതാക്കൾ അടങ്ങുന്ന സെൻട്രൽ കൌൺസിൽ ആണ് വിവിധ സ്ഥാനങ്ങൾ നിശ്ചയിക്കുന്നത്. 'ധർമസൻസദ്' എന്ന ഹൈന്ദവ പാർലമെന്റിൽ ഹിന്ദു സന്യാസിമാരും മത പണ്ഡിതരും ഉൾക്കൊള്ളുന്നു. അവർ സംഘടയുടെ നിലപാടുകളുടെ വിവിധ വശങ്ങളും സാമൂഹിക-സാംസ്കാരിക ചോദ്യങ്ങളും ഉന്നയിക്കുന്നു.
വി.എച്.പി.യുടെ യുവജനവിഭാഗമായ ബജ്രംഗ് ദൾ വിവിധ സംസ്ഥാനങ്ങളിൽ ശാഖകൾ സംഘടിപ്പിക്കുകയും ആയിരക്കണക്കിന് യുവജനങ്ങൾ വിവിധ പ്രവർത്തങ്ങളിൽ ഏർപ്പെടുകയും ചെയ്യുന്നു. ദുർഗാ വാഹിനി, 1991-ൽ ആരംഭിച്ച വി.എച്.പിയുടെ വനിതാവിഭാഗമാണ്. "ശാരീരികവും മാനസികവും ആത്മീയവുമായ അറിവും പുരോഗതിയും ലഭിക്കാൻ സ്വയം അർപ്പിക്കുക" എന്നതാണ് വി.എച്.പിയുടെ വിനിതാ-യുവജന വിഭാഗങ്ങളുടെ ലക്‌ഷ്യം.
സാമുദായിക സ്പർധകൾ
ഹിന്ദുക്കൾ ക്രിസ്തീയതയിലെയ്ക്ക് മാറുന്നത് അവസാനിപ്പിക്കാൻ വി.എച്.പി നിരവധി പ്രവർത്തങ്ങൾ നടത്തി. ഇത്തരം മതം മാറ്റത്തിലൂടെ ഒരാൾക്കും ഗുണം ലഭിച്ചിട്ടില്ല എന്നതാണ് സംഘടന കണ്ടത്. അതിനാൽ ഹിന്ദൂയിസത്തിലെയ്ക്ക് തിരികെ കൊണ്ട് വരുന്നത് നേരായ മാർഗ്ഗമാണെന്ന് കാണുന്നു.
പഞ്ചാബിലെ സിക്കുകാർ, പ്രത്യേകിച്ചും അധസ്ഥിതരായ സിക്കുകാർ ക്രിസ്തീയമതം സ്വീകരിക്കുന്നത് തടയാനുള്ള പ്രവർത്തങ്ങൾ നടത്തുകയും ഉയർന്ന ജാതിയിൽ പെട്ട സിക്കുകാരിൽ നിന്ന് എതിർപ്പുകൾ നേരിടുകയും ചെയ്തുവെങ്കിലും ക്രിസ്ത്യൻ മിഷനറിമാരുടെ മതപരിവർത്തനങ്ങൾക്ക് തടയിട്ടു.
2005–2009 കാലഘട്ടത്തിലെ കേരളത്തിലെ ലൗ ജിഹാദ് വിവാദം ക്രിസ്ത്യൻ സംഘടനകളുമായി ചേർന്ന് ഉയർത്തിക്കൊണ്ടു വന്നത് വി.എച്.പി ആയിരുന്നു. കേരളത്തിലും കർണ്ണാടകയിലും അമുസ്ലിം യുവതികളെ പ്രണയം നടിച്ച് ഇസ്‌ലാം മതത്തിലേക്ക് പരിവർത്തനം ചെയ്യുവാനായി സംഘടിത തീവ്രവാദ പ്രവർത്തനങ്ങൾ നടത്തുന്നുണ്ടെന്ന ആരോപണത്തെ തുടർന്ന് ഉയർന്നു വന്ന വിവാദമാണ് ലൗ ജിഹാദ് വിവാദം.
പുറത്തേയ്ക്കുള്ള കണ്ണികൾ
വർഗ്ഗം:സംഘ പരിവാർ വർഗ്ഗം:വിശ്വ ഹിന്ദു പരിഷത്ത്
നൂൽപ്പാലം കടക്കുന്നവർ
വൈശാഖൻ രചിച്ച നൂൽപ്പാലം കടക്കുന്നവർ എന്ന കൃതിക്കാണ് 1989-ൽ ചെറുകഥാസാഹിത്യത്തിനുള്ള കേരള സാഹിത്യ അക്കാദമി പുരസ്കാരം ലഭിച്ചത്. .
അവലംബം
വർഗ്ഗം:കേരള സാഹിത്യ അക്കാദമി പുരസ്കാരം ലഭിച്ച കൃതികൾ വർഗ്ഗം:മലയാളചെറുകഥകൾ
യൂക്ലിഡിന്റെ അൽഗൊരിതം
രണ്ട് എണ്ണൽ സംഖ്യകളുടെ ഉത്തമ സാധാരണ ഘടകം (ഉസാഘ) കാര്യക്ഷമമായി കണ്ടുപിടിക്കാനുള്ള ഒരു ഉപായമാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതം അഥവാ യൂക്ലിഡിയൻ അൽഗൊരിതം. പ്രാചീന ഗ്രീസിലെ ഗണിതശാസ്ത്രജ്ഞനായിരുന്ന യൂക്ലിഡിന്റെ പേരിലാണ് ഇത് അറിയപ്പെടുന്നത്. ക്രിസ്തുവിന് മുന്നൂറ് വർഷം മുമ്പ് എലിമെന്റ്സ് എന്ന തന്റെ ഗ്രന്ഥത്തിൽ യൂക്ലിഡാണ് ആദ്യമായി ഈ രീതി വിവരിച്ചത്. ഒരു പ്രശ്നത്തിന്റെ നിർദ്ധാരണത്തിന് പടിപടിയായി ഉപയോഗിക്കുന്ന നിശ്ചിതമായ ക്രിയകളുടെ ശ്രേണിയായ അൽഗൊരിതത്തിന് ഉത്തമോദാഹരണമാണിത്. ഭിന്നസംഖ്യകളെ ലഘൂകരിക്കാനും സംഖ്യാസിദ്ധാന്തത്തിലെയും ഗൂഢാലേഖനവിദ്യയിലെയും മറ്റനേകം കണക്കുകൂട്ടലുകളിലും ഈ അൽഗൊരിതം ഉപയോഗിക്കുന്നു.
രണ്ടു സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കുമ്പോൾ വലിയ സംഖ്യയ്ക്കു പകരം സംഖ്യകളുടെ വ്യത്യാസം ഉപയോഗിച്ചാൽ ഉസാഘയിൽ വ്യത്യാസം വരുന്നില്ല എന്ന തത്ത്വമാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് അടിസ്ഥാനം. ഉദാഹരണമായി, 252, 105 എന്നീ സംഖ്യകളുടെ ഉസാഘ 21 ആണ് (252 = 21 × 12, 105 = 21 × 5). 252നു പകരം അതിൽ നിന്ന് 105 കുറച്ചാൽ കിട്ടുന്ന 147 ഉപയോഗിച്ചാൽ ഉസാഘ 21 തന്നെ ലഭിക്കുന്നു (252 − 105 = 147 = 21 × 7). ഇങ്ങനെ വരുത്തുന്ന മാറ്റം ഓരോ പടിയിലും വലിയ സംഖ്യയുടെ വില കുറയ്ക്കുന്നതിനാൽ സംഖ്യകൾ ചെറുതായി വരുകയും ഒടുവിൽ തുല്യമാവുകയും ചെയ്യും. ആ അവസരത്തിൽ സംഖ്യകളുടെ വില ഉസാഘയ്ക്ക് തുല്യമായിരിക്കും. ഇതിനു ശേഷം അൽഗൊരിതത്തെ പിന്നോട്ടോടിച്ചാൽ ആദ്യത്തെ രണ്ട് സംഖ്യകളെ ഏത് പൂർണ്ണസംഖ്യകൾ കൊണ്ട് ഗുണിച്ച് അവയുടെ തുക കണ്ടാലാണ് ഉസാഘ ലഭിക്കുക എന്ന് കണ്ടുപിടിക്കാം. മുകളിലെ ഉദാഹരണമെടുത്താൽ, 21 = 5 × 105 + (−2) × 252. രണ്ട് സംഖ്യകളുടെ ഉസാഘയെ എല്ലായ്പ്പോഴും അവയുടെ രേഖീയസഞ്ചയമായി എഴുതാൻ സാധിക്കും എന്നത് ബെസു അനന്യത എന്നറിയപ്പെടുന്നു.
അൽഗൊരിതം മേൽ വിവരിച്ച പ്രകാരമാണ് ചെയ്യുന്നതെങ്കിൽ വലിയ സംഖ്യയിൽ നിന്ന് ചെറിയ സംഖ്യ ഒരുപാടു പ്രാവശ്യം കുറയ്ക്കേണ്ടി വന്നേക്കാം. ആദ്യത്തെ സംഖ്യ മറ്റേതിനെക്കാൾ വളരെയധികം വലുതാണെങ്കിലാണ് ഇങ്ങനെ സംഭവിക്കുക. സംഖ്യകൾ കുറയ്ക്കുന്നതിനു പകരം ഹരിച്ചാൽ കിട്ടുന്ന ശിഷ്ടം ഉപയോഗിച്ചാൽ അൽഗൊരിതത്തിന്റെ കാര്യക്ഷമത വളരെയധികം വർദ്ധിക്കുന്നു. സംഖ്യകൾ തുല്യമാകുന്നതിനു പകരം ഒരു സംഖ്യ പൂജ്യമാകുമ്പോഴാണ് ക്രിയകൾ അവസാനിപ്പിക്കേണ്ടതെന്നു മാത്രം. ചെറിയ സംഖ്യയിൽ (ദശാംശ സമ്പ്രദായത്തിൽ) എത്ര അക്കങ്ങളുണ്ടോ അതിന്റെ അഞ്ചു മടങ്ങിൽ കുറവ് ക്രിയകൾ മാത്രമേ കാര്യക്ഷമമായ അൽഗൊരിതത്തിൽ വേണ്ടിവരൂ എന്ന് 1844-ൽ ഗബ്രിയേൽ ലാമേ തെളിയിച്ചു. ഇതാണ് അൽഗൊരിതങ്ങളുടെ ഗണനപരമായ സങ്കീർണ്ണതാസിദ്ധാന്തത്തിന് തുടക്കം കുറിച്ചത്. അൽഗൊരിതത്തിന്റെ കാര്യക്ഷമത വർദ്ധിപ്പിക്കാനുള്ള കൂടുതൽ വഴികൾ ഇരുപതാം നൂറ്റാണ്ടിൽ കണ്ടുപിടിച്ചിട്ടുണ്ട്.
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് സൈദ്ധാന്തികമായും പ്രായോഗികമായും വളരെയധികം പ്രയോജനങ്ങളുണ്ട്. ഭിന്നസംഖ്യകളെ ലഘൂകരിക്കാനും മോഡ്യുലാർ അങ്കഗണിതത്തിൽ ഹരണം നടത്താനും ഇത് ഉപയോഗിക്കാം. ഇന്റർനെറ്റിൽ ആശയവിനിമയം നടത്താനുപയോഗിക്കുന്ന ഗൂഢാലേഖനവിദ്യയുടെ (ക്രിപ്റ്റോഗ്രാഫി) അടിസ്ഥാനം യൂക്ലിഡിന്റെ അൽഗൊരിതമാാണ്, ഈ ഗൂഢാലേഖനവിദ്യകളെ തകർക്കാൻ വേണ്ടി വലിയ സംഖ്യകളുടെ ഘടകങ്ങൾ കണ്ടെത്താനും ഈ അൽഗൊരിതം ഉപയോഗിക്കുന്നു. ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കുക, ചൈനീസ് ശിഷ്ട പ്രമേയമുപയോഗിച്ച് സർവ്വസമതകളുടെ വ്യവസ്ഥകൾക്ക് നിർദ്ധാരണം കാണുക, സതതഭിന്നങ്ങൾ നിർമ്മിക്കുക, അഭിന്നകങ്ങളെ ഭിന്നസംഖ്യകളുപയോഗിച്ച് ഏകദേശനം ചെയ്യുക എന്നതിനെല്ലാം സഹായിക്കുന്നതിനു പുറമെ സംഖ്യാസിദ്ധാന്തത്തിലെ പ്രമേയങ്ങൾ തെളിയിക്കാനും ഈ അൽഗൊരിതം സഹായിക്കുന്നു. ലഗ്രാഞ്ചിന്റെ നാല് വർഗ്ഗ പ്രമേയം, അഭാജ്യ ഘടകക്രിയയുടെ അനന്യത എന്നിവ ഇങ്ങനെ തെളിയിക്കാവുന്നവയാണ്. ആദിമ അൽഗൊരിതം സംഖ്യകൾക്കും നീളങ്ങൾക്കും വേണ്ടി മാത്രമുള്ളതായിരുന്നെങ്കിലും പത്തൊമ്പതാം നൂറ്റാണ്ടിൽ ഗോസിയൻ പൂർണ്ണസംഖ്യകൾ, ഒരു ചരത്തിലുള്ള ബഹുപദങ്ങൾ മുതലായവയ്ക്കും ഉപയോഗിക്കാവുന്ന രീതിയിൽ സാമാന്യവൽക്കരിച്ചു. അമൂർത്തബീജഗണിതത്തിലെ ആധുനിക വിഭാവനമായ യൂക്ലിഡിയൻ മണ്ഡലം ഇതിനെ അടിസ്ഥാനമാക്കിയുള്ളതാണ്.
പശ്ചാത്തലം: ഉത്തമ സാധാരണ ഘടകം
a, b എന്ന രണ്ട് എണ്ണൽ സംഖ്യകളുടെ ഉത്തമ സാധാരണ ഘടകം (ഉസാഘ) കണ്ടുപിടിക്കാനാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കുന്നത്. g ഇവയുടെ ഉസാഘയാണെങ്കിൽ a, b എന്നിവയെ g കൊണ്ടു ഹരിച്ചാൽ ശിഷ്ടം വരാത്ത ഏറ്റവും വലിയ സംഖ്യയായിരിക്കുമത്. ഇംഗ്ലീഷിലെ പല പേരുകളിലൊന്ന് greatest common divisor എന്നായതിനാൽ gcd(a, b) എന്നാണ് സാധാരണയായി ഇതിനെ സൂചിപ്പിക്കുന്നത്. (a, b) എന്ന് കൂടുതൽ ലളിതമായി എഴുതാമെങ്കിലും വലയസിദ്ധാന്തത്തിൽ ഗുണജത്തെ (ideal) സൂചിപ്പിക്കാനും ഈ പ്രതീകമുപയോഗിക്കുന്നതിനാൽ ആശയക്കുഴപ്പമുണ്ടാകാം.
ഉസാഘയെ ഈ വിധത്തിൽ ചിത്രീകരിക്കാം. a × b വിസ്തീർണ്ണമുള്ള ഒരു ചതുരമെടുക്കുക, രണ്ട് വശങ്ങളുടെയും ഭാജകമായ ഒരു c ഉണ്ടെന്നും കരുതുക. എങ്കിൽ വശങ്ങളെ രണ്ടിനെയും c നീളമുള്ള ഭാഗങ്ങളായി മുറിക്കാൻ സാധിക്കും, അതുവഴി ചതുരത്തെ c×c വിസ്തീർണ്ണമുള്ള സമചതുരങ്ങളായും ഭാഗിക്കാം. ഇങ്ങനത്തെ ഏറ്റവും വലിയ സമചതുരത്തിന്റെ വശത്തിന്റെ നീളമാണ് a, b എന്നിവയുടെ ഉസാഘ. ഉദാഹരണമായി, നീളം 60ഉം വീതി 24ഉം ഉള്ള ചതുരത്തെ 1×1, 2×2, 3×3, 4×4, 6×6 അഥവാ 12×12 വിസ്തീർണ്ണമുള്ള സമചതുരങ്ങളായി ഭാഗിക്കാം. അതിനാൽ 24, 60 എന്നീ സംഖ്യകളുടെ ഉസാഘ 12 ആണ്. 24×60 ചതുരത്തെ 12×12 വിസ്തീർണ്ണമുള്ള സമചതുരങ്ങളാക്കിയാൽ വീതിയുടെ ഭാഗത്ത് രണ്ടും (24/12 = 2) നീളത്തിന്റെ ഭാഗത്ത് അഞ്ചും (60/12 = 5) സമചതുരങ്ങളാണുണ്ടാവുക.
വലയസിദ്ധാന്തം പോലുള്ള ഉയർന്ന ഗണിതശാസ്ത്രശാഖകളിൽ ഉപയോഗം വരുന്ന മറ്റൊരു വിധത്തിലും ഉസാഘയെ നിർവചിക്കാം: രണ്ട് സംഖ്യകളുടെ പൂർണ്ണസംഖ്യകൾകൊണ്ടുള്ള രേഖീയസഞ്ചയങ്ങളിൽ (linear combinations) വച്ച് ഏറ്റവും ചെറിയ ധനസംഖ്യയാണ് ഉസാഘ. അതായത്, u, v എന്നിവ പൂർണ്ണസംഖ്യകളായുള്ള ua + vb എന്ന തരത്തിലുള്ള ഏറ്റവും ചെറീയ ധനസംഖ്യ. a, b എന്നിവയുടെ പൂർണ്ണസംഖ്യകൾ കൊണ്ടുള്ള രേഖീയസഞ്ചയങ്ങളുടെ ഗണം g യുടെ ഗുണിതങ്ങളുടെ (mg, ഇവിടെ m ഒരു പൂർണ്ണസംഖ്യയാണ്) ഗണം തന്നെയാണ്. ആധുനിക ഗണിതശാസ്ത്രത്തിന്റെ ഭാഷയിൽ പറഞ്ഞാൽ, a, b എന്നിവ ജനകങ്ങളായുള്ള ഗുണജം g മാത്രം ജനകമായുള്ള ഗുണജത്തിന് തുല്യമാണ്. ഒറ്റ അംഗം ജനകമായുള്ള ഗുണജത്തെ പ്രിൻസിപൽ ഗുണജം എന്ന് വിളിക്കുന്നു. പൂർണ്ണസംഖ്യകളുടെ ഗുണജങ്ങളെല്ലാം തന്നെ പ്രിൻസിപൽ ആണ്. ഉസാഘയുടെ ചില ഗുണധർമ്മങ്ങൾ തെളിയിക്കാൻ ഈ നിർവചനമാണ് കൂടുതൽ സഹായകമാവുക. ഉദാഹരണമായി, രണ്ട് സംഖ്യകളുടെ പൊതുഭാജകങ്ങളെല്ലാം അവയുടെ ഉസാഘയുടെ ഭാജകമായിരിക്കണമെന്നത് നിർവചനത്തിൽ നിന്ന് നേരിട്ട് നിരീക്ഷിക്കാം. ഈ നിർവചനങ്ങളുടെയെല്ലാം തുല്യത താഴെ തെളിയിക്കുന്നുണ്ട്.
മൂന്നോ അധികമോ സംഖ്യകളുടെ ഉസാഘ അവയുടെ പൊതുവായ അഭാജ്യഘടകങ്ങളുടെ ഗുണനഫലമാണ്. സംഖ്യകളെ ഈരണ്ടെണ്ണമായെടുത്ത് ഉസാഘ കണ്ടാലും മതി.. ഉദാഹരണമായി,
gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b).
അതിനാൽ രണ്ട് സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കാനുതകുന്ന യൂക്ലിഡിന്റെ അൽഗൊരിതം രണ്ടിൽ കൂടുതൽ സംഖ്യകൾക്കു വേണ്ടിയും ഉപയോഗിക്കാം.
നടപടിക്രമം
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിൽ ഒരേ ക്രിയ തന്നെ അൽഗൊരിതത്തിന്റെ അവസാനം വരെ കറേ തവണ ആവർത്തിക്കുന്നു. ഓരോ ക്രിയയുടെയും ഫലം അടുത്ത പടിയിൽ ഉപയോഗിക്കും. ഇതുവരെ ചെയ്ത ക്രിയകളുടെ എണ്ണം k ആണെന്നെടുക്കുക. അൽഗൊരിതത്തിന്റെ തുടക്കത്തിൽ k = 0 ആയിരിക്കും, അടുത്ത പടിയിൽ k = 1 അങ്ങനെ വർദ്ധിച്ചുവരുന്നു.
ഓരോ ക്രിയയുടെയും ഇൻപുട്ട് rk−1, rk−2 എന്ന രണ്ട് ശിഷ്ടങ്ങളാണ്, ഇവ രണ്ടും ധനപൂർണ്ണസംഖ്യകളോ പൂജ്യമോ ആയിരിക്കും. അൽഗൊരിതത്തിന്റെ ഓരോ പടിയിലും ശിഷ്ടങ്ങൾ കുറഞ്ഞുവരുന്നതിനാൾ rk−1 അതിന്റെ മുൻഗാമിയായ rk−2 നെക്കാൾ ചെറുതായിരിക്കും. താഴെ കൊടുത്തിരിക്കുന്ന സമവാക്യത്തിന് നിർദ്ധാരണമായി qk എന്ന ഹരണഫലവും rk എന്ന ശിഷ്ടവും കണ്ടുപിടിക്കുകയാണ് kആമത്തെ പടിയുടെ ലക്ഷ്യം. ഈ നിർദ്ധാരണത്തിൽ rk < rk−1 ആയിരിക്കുകയും വേണം. മറ്റൊരു രീതിയിൽ പറഞ്ഞാൽ, ഫലം rk−1ൽ കുറവാകുന്നതു വരെ rk−2ൽ നിന്ന് rk−1 കുറയ്ക്കുന്നു. ഇതിന്റെ അവസാനം കിട്ടുന്ന സംഖ്യയാണ് rk. അൽഗൊരിതത്തിന്റെ തുടക്കത്തിൽ (k = 0) ശിഷ്ടങ്ങളായ r−2, r−1 എന്നിവ ഉസാഘ കാണേണ്ട സംഖ്യകളായ a, b എന്നിവയായിരിക്കും. അടുത്ത പടിയിൽ (k = 1) bയും മുൻപത്തെ പടിയിലെ ഫലമായ r0 യുമാണ് ശിഷ്ടങ്ങളായി ഉപയോഗിക്കുക. ഇങ്ങനെ നമുക്ക് അൽഗൊരിതത്തെ സമവാക്യങ്ങളുടെ ഒരു ശ്രേണിയായി എഴുതാം a തുടക്കത്തിൽ b യെക്കാൾ ചെറുതാണെങ്കിൽ ആദ്യത്തെ പടി അവയെ പരസ്പരം വച്ചുമാറ്റുക മാത്രമേ ചെയ്യൂ. ഈ ക്രിയയുടെ ഫലങ്ങളായ ഹരണഫലം q0 പൂജ്യവും ശിഷ്ടം r0 aയും ആയതിനാലാണിത്. അതിനാൽ k ≥ 0 ആകുമ്പോഴൊക്കെ ശിഷ്ടം rk അതിന്റെ മുൻഗാമിയായ rk−1 നെക്കാൾ ചെറുതാണെന്നു വരുന്നു. ശിഷ്ടങ്ങൾ ഓരോ പടിയിലും ചെറുതാവും, എന്നാൽ ഒരിക്കലും പൂജ്യത്തിൽ കുറവാവുകയുമില്ല എന്നതിനാൽ ഒടുവിൽ ശിഷ്ടം rN പൂജ്യമാവുന്ന അവസ്ഥയുണ്ടാവണം. അതോടെ അൽഗൊരിതം അവസാനിപ്പിക്കുന്നു. പൂജ്യത്തിനു തൊട്ടുമുമ്പ് ലഭിച്ച ശിഷ്ടമായ rN−1 ആണ് a, b എന്ന സംഖ്യകളുടെ ഉസാഘ. തുടക്കത്തിലെ ശിഷ്ടമായ r0നും rNനും ഇടയിലെ പൂർണ്ണസംഖ്യകളുടെ എണ്ണം പരിമിതമായതിനാൽ N ഒരിക്കലും അനന്തമാവുകയില്ല.
തെളിവ്
യൂക്ലിഡിന്റെ അൽഗൊരിതം ശരിയായി ഉസാഘ കണ്ടുപിടിക്കുന്നു എന്ന് തെളിയിക്കുന്നത് രണ്ടു പടിയായാണ്. പൂജ്യത്തിനു മുമ്പായി കിട്ടുന്ന ശിഷ്ടമായ rN−1 ഉസാഘ കാണേണ്ട a, b എന്ന സംഖ്യകളുടെ ഭാജകമാണ് എന്ന് തെളിയിക്കുകയാണ് ആദ്യത്തെ പടി. പൊതു ഭാജകമായതിനാൽ അത് ഉസാഘയായ gയെക്കാൾ വലുതായിരിക്കില്ല എന്ന് വരുന്നു. രണ്ടാമത്തെ പടിയിൽ a, b എന്ന സംഖ്യകൾക്കും പൊതുവായുള്ള ഉസാഘയുൾപ്പെടെയുള്ള ഏത് ഭാജകവും rN−1ന്റെയും ഭാജകമാണെന്ന് തെളിയിക്കുന്നു. അതിനാൽ ഉസാഘ ഈ സംഖ്യയെക്കാൾ ചെറുതോ അതിന് തുല്യമോ ആയിരിക്കണം. ഈ രണ്ട് പ്രസ്താവനകളും പരസ്പരവിരുദ്ധമാവാതിരിക്കാനുള്ള ഒരേയൊരു വഴി rN−1 = g ആവുകയാണ്.
ആദ്യ പടിയായി a, b എന്നിവയുടെ ഭാജകമാണ് rN−1 എന്ന് ഇപ്രകാരം തെളിയിക്കാം. ആദ്യമായി, rN−1 അതിന്റെ മുൻഗാമിയായ rN−2ന്റെ ഭാജകമാണെന്ന് നിരീക്ഷിക്കുക
rN−2 = qN rN−1
അവസാനത്തെ ശിഷ്ടമായ rN പൂജ്യമായതിനാലാണിത്. ഇതിനു മുമ്പത്തെ പടിയിലെ സമവാക്യമെടുത്താൽ
rN−3 = qN−1 rN−2 + rN−1
വലതുഭാഗത്തെ രണ്ട് പദങ്ങളും rN−1 ന്റെ ഗുണിതങ്ങളായതിനാൽ rN−1 അതിന്റെ അടുത്ത മുൻഗാമിയായ rN−3ന്റെയും ഭാജകമാണെന്നു കാണാം. ഈ വിധത്തിൽ തുടരുകയാണെങ്കിൽ rN−1 അതിനു മുമ്പുള്ള എല്ലാ ശിഷ്ടങ്ങളുടെയും ഭാജകമാണെന്നു വരുന്നു, ഈ ശിഷ്ടങ്ങളിൽ a, b എന്നിവയും പെടുന്നു എന്നത് പ്രധാനമാണ്. rN−1നു മുമ്പ് ലഭിച്ച ശിഷ്ടങ്ങളായ rN−2, rN−3 മുതലായവയൊന്നും തന്നെ ശിഷ്ടം വരുന്നതിനാൽ a യുടെയോ b യുടെയോ ഭാജകങ്ങളാവില്ല. rN−1 എന്നത് a, b എന്നിവയുടെ പൊതു ഭാജകമായതിനാൽ rN−1 ≤ g.
a, b എന്നീ സംഖ്യകളുടെ ഭാജകമായ ഏത് cയും അൽഗൊരിതത്തിലെ എല്ലാ ശിഷ്ടങ്ങളുടെയും ഭാജകമായിരിക്കും എന്ന് തെളിയിക്കുകയാണ് അടുത്ത പടി. നിർവചനമനുസരിച്ച് aയെയും bയെയും cയുടെ ഗുണിതങ്ങളായി എഴുതാം: a = mc, b = nc. ഇവിടെ m, n എന്നിവ എണ്ണൽ സംഖ്യകളാണ്. അൽഗൊരിതത്തിന്റെ ആദ്യത്തെ പടിയെടുത്താൽ അതായത്, c ആദ്യത്തെ പടിയിലെ ശിഷ്ടമായ r0യുടെ ഭാജകമാണ്. ഇതേ വാദമുപയോഗിച്ചാൽ c ഇതെത്തുടർന്നു വരുന്ന പടികളിലെ ശിഷ്ടങ്ങളായ r1, r2 മുതലായവയുടെയും ഭാജകമാണെന്ന് കാണാം. അതായത്, rN−1ന്റെ ഭാജകമാണ് ഉസാഘയായ g എന്നും, അതിനാൽത്തന്നെ g ≤ rN−1 എന്നും വരുന്നു. ഇതിന്റെ വിപരീതം (rN−1 ≤ g) നേരത്തെ തെളിയിച്ചിട്ടുള്ളതിനാൽ g = rN−1 എന്ന് ലഭിക്കുന്നു. അതായത്, ഇതിനു മുമ്പുള്ള എല്ലാ ജോടികളുടെയും ഉസാഘ g തന്നെയാണ്:
g = gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = … = gcd(rN−2, rN−1) = rN−1.
ഉദാഹരണം
യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് a = 1071, b = 462 എന്നിവയുടെ ഉസാഘ കാണേണ്ടതുണ്ടെന്ന് കരുതുക. ശിഷ്ടം 462-ൽ കുറവാകുന്നതുവരെ 462-ന്റെ ഗുണിതങ്ങൾ 1071-ൽ നിന്ന് കുറയ്ക്കുകയാണ് ആദ്യ പടി. രണ്ടുതവണയേ (q0 = 2) ഇങ്ങനെ കുറയ്ക്കാൻ പറ്റുകയുള്ളൂ, അതോടെ 147 ശിഷ്ടമായി ലഭിക്കും:
1071 = 2 × 462 + 147.
462 = 3 × 147 + 21.
അടുത്ത പടിയിൽ 21-ന്റെ ഗുണിതങ്ങളെ 147ൽ നിന്ന് കുറയ്ക്കുന്നു. ഏഴ് തവണ (q2 = 7) കുറച്ചാൽ ഒന്നും ബാക്കി വരാതെ സംഖ്യ പൂജ്യമാവും:
147 = 7 × 21 + 0.
അവസാനത്തെ ശിഷ്ടം പൂജ്യമായതിനാൽ 1071,462 എന്ന സംഖ്യകളുടെ ഉസാഘയായി 21 (മുമ്പത്തെ പടിയിലെ ശിഷ്ടം) കണ്ടുപിടിച്ച് അൽഗൊരിതം അവസാനിക്കുന്നു.
1071 = 3^2 × 7 × 17, 462 = 2 × 3 × 7 × 11
എന്നിങ്ങനെ സംഖ്യകളുടെ ഘടകക്രിയ ചെയ്താൽ ഈ ഉത്തരം ശരിയാണെന്നു കാണാം. അൽഗഗൊരിതത്തിലെ പടികൾ ഇവിടെ പട്ടികപ്പെടുത്തിയിരിക്കുന്നു
ചിത്രീകരണം
മേലെ ഉസാഘയെ ജ്യാമിതീയമായ വ്യാഖ്യാനിച്ച രീതിയിൽ അൽഗൊരിതത്തിലെ ക്രിയകളെയും ചിത്രീകരിക്കാം. a×b വിസ്തീർണ്ണമുള്ള (ഇവിടെ a, bയെക്കാൾ വലുതാണ്) ഒരു ചതുരത്തെ സമചതുരങ്ങൾ കൊണ്ട് നിറയ്ക്കണമെന്ന് കരുതുക. ആദ്യം നമുക്ക് ചതുരത്തെ b×b സമചതുരങ്ങൾ കൊണ്ട് മൂടാൻ ശ്രമിക്കാം. പക്ഷെ ആവുന്നത്ര സമചതുരങ്ങൾ ചേർത്തുകഴിഞ്ഞാൽ ഒരു r0×b ചതുരം ബാക്കിയാവും. ഇതിനെ പിന്നീട് r0×r0 സമചതുരങ്ങൾ കൊണ്ട് മൂടാൻ ശ്രമിക്കാം. ഇതിന്റെ അവസാനം ഒരു r1×r0 ചതുരം ബാക്കിയാവുകയും അതിനെ അടുത്ത പടിയിൽ r1×r1 സമചതുരങ്ങൾ കൊണ്ട് മൂടാൻ ശ്രമിക്കുകയും ചെയ്യാം. ഒരു പടിയിൽ ചതുരത്തെ സമചതുരങ്ങൾ കൊണ്ട് പൂർണ്ണമായി മൂടാൻ സാധിക്കുകമ്പോഴാണ് ഈ ക്രിയാശ്രേണി അവസാനിക്കുന്നത്. ഒടുവിൽ ചേർത്ത ഏറ്റവും ചെറിയ സമചതുരത്തിന്റെ വശത്തിന്റെ നീളമാണ് ആദ്യത്തെ ചതുരത്തിന്റെ വശങ്ങളുടെ ഉസാഘ. ഉദാഹരണമായി, ആനിമേഷനിലെ തുടക്കത്തിലെ പച്ച ചതുരത്തിന്റെ വശങ്ങളുടെ നീളം 1071, 462 ആണ്, ഇവയുടെ ഉസാഘയായ 21 ആണ് ഏറ്റവും ചെറിയ ചുവന്ന സമചതുരമത്തിന്റെ വശം.
യൂക്ലിഡിയൻ ഹരണം
kആമത്തെ പടിയിൽ rk−1, rk−2 എന്നീ സംഖ്യകളുപയോഗിച്ച് ഹരണഫലമായ qkയും ശിഷ്ടമായ rkയും കണ്ടുപിടിക്കുകയാണ് ചെയ്യേണ്ടത്.
ഇവിടെ rkയുടെ കേവലവില rk−1ന്റേതിനെക്കാൾ കുറവായിരിക്കണം. യൂക്ലിഡിയൻ ഹരണത്തിന് അടിസ്ഥാനമായ പ്രമേയം ഈ നിഷ്കർഷയോടെ ഹരണഫലവും ശിഷ്ടവും കണ്ടുപിടിക്കുന്നത് സാധ്യമാണെന്നും ഫലം അനന്യമാണെന്നും പറയുന്നു.
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മൂലരൂപത്തിൽ ആവർത്തിച്ച് വ്യവകലനം ചെയ്തുകൊണ്ടാണ് ഹരണഫലവും ശിഷ്ടവും കണ്ടിരുന്നത്. അതായത്, ഫലം rk−1ൽ കുറവാവുന്നതു വരെ rk−2ൽ നിന്ന് rk−1 ആവർത്തിച്ച് കുറയ്ക്കുന്നു. ഇതിനുശേഷം rk, rk−1 എന്നിവയെ പരസ്പരം വച്ചുമാറിയ ശേഷം പ്രക്രിയ തുടരുന്നു. ഇങ്ങനെ ആവർത്തിച്ച് വ്യവകലനം ചെയ്യുന്നതിനു പകരം ഒറ്റ ക്രിയകൊണ്ടുതന്നെ ഹരണഫലവും ശിഷ്ടവും കാണാൻ യൂക്ലിഡിയൻ ഹരണം വഴി സാധിക്കുന്നു. കാര്യക്ഷമത വർദ്ധിപ്പിക്കുന്നതിനു പുറമെ, ഹരണഫലങ്ങൾ ആവശ്യമില്ലാത്തതിനാൽ ശിഷ്ടം മാത്രം നൽകുന്ന മോഡ്യുലോ സംക്രിയ ഉപയോഗിക്കാനും സാധിക്കുന്നു. അതിനാൽ യൂക്ലിഡിയൻ ഹരണം ഉപയോഗിച്ചുള്ള അൽഗൊരിതത്തിന്റെ ക്രിയകളെ ഇപ്രകാരം എഴുതാം
rk = rk−2 mod rk−1.
പ്രയോഗത്തിൽ
അൽഗൊരിതത്തിന്റെ പ്രയോഗം സ്യൂഡോകോഡ് ഉപയോഗിച്ച് വ്യക്തമാക്കാം. ഉദാഹരണത്തിന് ഹരണം ഉപയോഗിക്കുന്ന അൽഗൊരിതം ഇപ്രകാരം എഴുതാം
function gcd(a, b)    while b ≠ 0 t := b;        b := a mod b;         a := t;      return a;
k ആമത്തെ പടിയുടെ ആരംഭത്തിൽ b മുമ്പത്തെ ശിഷ്ടമായ rk−1 ഉം a മുൻഗാമിയായ rk−2 ഉം ആയിരിക്കും. b := a mod b എന്ന ക്രിയ മേൽ വിവരിച്ച rk ≡ rk−2 mod rk−1 എന്ന ആവർത്തനബന്ധത്തിന്റെ പ്രയോഗമാണ്. താൽക്കാലികമായ ചരമായ t ശിഷ്ടങ്ങളെ പരസ്പരം വച്ചുമാറാനാണ് ഉപയോഗിക്കുന്നത്. പടിയുടെ അവസാനം ശിഷ്ടമായ rk യുടെ വില b യിലും, മുമ്പത്തെ പടിയിലെ ശിഷ്ടമായ rk−1 ന്റെ വില a യിലും എത്തുന്നു.
ഹരണത്തിനു പകരം വ്യവകലനമാണ് യൂക്ലിഡിന്റെ മൂല അൽഗൊരിതത്തിൽ ഉപയോഗിക്കുന്നത്. ശിഷ്ടം കണ്ടുപിടിക്കാൻ (b = a mod b) ആവർത്തിച്ച് സംഖ്യ കുറയ്ക്കുന്നു. ഹരണം ഉപയോഗിക്കുന്ന അൽഗൊരിതത്തിൽ നിന്ന് വ്യത്യസ്തമായി പൂർണ്ണസംഖ്യകൾക്കു (ധനസംഖ്യയാകണമെന്ന നിർബന്ധമില്ല) പകരം എണ്ണൽസംഖ്യകളാണ് ഇവിടെ ഉപയോഗിക്കുന്നത്, a = b ആവുമ്പോൾ അൽഗൊരിതം അവസാനിപ്പിക്കുകയും ചെയ്യും.
function gcd(a, b)    while a ≠ b          if a > b            a := a − b;          else b := b − a;     return a;
മുമ്പത്തെ ശിഷ്ടങ്ങളായ rk−1, rk−2 എന്നിവയുടെ വിലകൾ a, b എന്ന ചരങ്ങൾ മാറിമാറി സ്വീകരിക്കുന്നു. ഒരു പടിയുടെ തുടക്കത്തിൽ a യുടെ വില b യെക്കാൾ വലുതാണെന്ന് കരുതുക; എങ്കിൽ rk−2 > rk−1 ആയതിനാൽ a എന്ന ചരത്തിലുള്ളത് rk−2 ന്റെ വിലയാണെന്ന് വരുന്നു. a യുടെ വില b യെക്കാൾ ചെറുതാവുന്നത് വരെ b യെ a യിൽ നിന്ന് കുറയ്ക്കുന്നു. പുതിയ ശിഷ്ടമായ rk യുടെ വില അപ്പോൾ a യിലെത്തുന്നു. തുടർന്ന് b യുടെ വില a യിൽ കുറവാവുന്നത് വരെ a കുറച്ച് അടുത്ത ശിഷ്ടമായ rk+1 കണ്ടുപിടിക്കുന്നു, ഇങ്ങനെയാണ് അൽഗൊരിതം പുരോഗമിക്കുന്നത്.
ഓരോ പടിയിലെയും സംഖ്യാജോടിയുടെ ഉസാഘ തുല്യമാണ് എന്നതും അൽഗൊരിതം അവസാനിപ്പിക്കാൻ gcd(rN−1, 0) = rN−1 എന്ന നിബന്ധനയും അടിസ്ഥാനമാക്കി സ്വാവർത്തനം ഉപയോഗിക്കുന്ന രീതിയിലും അൽഗൊരിതം എഴുതാം.
function gcd(a, b)    if b = 0 return a;     else return gcd(b, a mod b);
ഉദാഹരണമായി gcd(1071, 462) കണ്ടുപിടിക്കാൻ സ്വാവർത്തനം ഉപയോഗിച്ച് gcd(462, 1071 mod 462) = gcd(462, 147) കണ്ടെത്താൻ ശ്രമിക്കുന്നു. ഇതിനുള്ള സ്വാവർത്തനം gcd(147, 462 mod 147) = gcd(147, 21) കണ്ടുപിടിക്കുന്നതിലേക്കും തുടർന്ന് gcd(21, 147 mod 21) = gcd(21, 0) യിലേക്കും നയിക്കുന്നു. ഇവിടെ രണ്ടാമത്തെ സംഖ്യ പൂജ്യമായതിനാൽ ഉസാഘ ആദ്യത്തെ സംഖ്യയായ 21 ആണ്.
ശിഷ്ടത്തിന്റെ കുറഞ്ഞ കേവലവില ഉപയോഗിക്കുന്ന രീതി
ശിഷ്ടത്തിന്റെ ഋണവിലകളും കൂടി ഉപയോഗിക്കുന്ന തരത്തിലും യൂക്ലിഡിന്റെ അൽഗൊരിതം പ്രയോഗവൽക്കരിക്കാം. അൽഗൊരിതത്തിന്റെ ഒരു പടിയിൽ ലഭിക്കുന്ന ഹരണഫലത്തോട് 1 കൂട്ടുകയാണെങ്കിൽ ശിഷ്ടം ഋണസംഖ്യയായി മാറും. ഈ ഋണശിഷ്ടത്തിന്റെ കേവലവില ഹരണഫലത്തോട് 1 കൂട്ടാതെ ലഭിക്കുന്ന ധനശിഷ്ടത്തെക്കാൾ കുറവാണെങ്കിൽ പരിഷ്കരിച്ച ഹരണഫലവും ശിഷ്ടവും ഉപയോഗിച്ചുകൊണ്ടാണ് ഈ അൽഗൊരിതം പുരോഗമിക്കുന്നത്. ഇതുവരെ
rk−2 = qk rk−1 + rk
എന്ന സമവാക്യത്തിൽ
rk−1
ആണെന്നായിരുന്നു നാം കല്പിച്ചിരുന്നത്. എന്നാൽ ഇതിൽ നിന്ന് വ്യത്യസ്തമായി ഒരു ഋണശിഷ്ടം
ek
ഇപ്രകാരം കണ്ടുപിടിക്കാം:
rk−1 > 0
ആണെങ്കിൽ
rk−2 = (qk + 1) rk−1 + ek
അഥവാ
ആവുന്ന അവസരത്തിൽ
rk
യ്ക്കു പകരം
ek.
ഉപയോഗിക്കുകയാണെങ്കിൽ ഓരോ പടിയിലും താഴെ കൊടുത്തിരിക്കുന്ന നിഷ്കർഷ അനുസരിക്കുന്ന അൽഗൊരിതം ലഭിക്കുന്നു:
അൽഗൊരിതത്തിന്റെ എല്ലാ ഭാഷ്യങ്ങളിലും വച്ച് ഇതിനാണ് ഏറ്റവും കുറവ് പടികൾ ആവശ്യമായി വരിക എന്ന് ലിയോപോൾഡ് ക്രോണെക്കർ തെളിയിച്ചിട്ടുണ്ട്. സാമാന്യവൽക്കരിക്കുകയാണെങ്കിൽ, a, b എന്ന സംഖ്യകളുടെ ഉസാഘ കാണാനാവശ്യമായ പടികളുടെ എണ്ണം ഏറ്റവും കുറവാകുന്നത് ആവുന്ന തരത്തിൽ
qk
ഗ്രാമസഭ
ഗ്രാമസഭയുടെ യോഗം 3 മാസത്തിലൊരിക്കൽ വിളിച്ചുകൂട്ടുന്നതിൽ തുടർച്ചയായി രണ്ടുതവണ വീഴ്ചവരുത്തിയാൽ ബന്ധപ്പെട്ട അംഗത്തിന്റെ അംഗത്വം നഷ്ടമാകും. മുൻവർഷത്തെ വികസന പരിപാടികളും നടപ്പുവർഷത്തിൽ ഏറ്റെടുക്കാനുദ്ദേശിക്കുന്ന വികസന പരിപാടികളും ഇതിനുവേണ്ടിവരുന്ന ചെലവുകൾ സംബന്ധിച്ച ഒരു റിപ്പോർട്ടും മുൻവർഷത്തെ വാർഷികക്കണക്കുകളുടെ ഒരു സ്റ്റേറ്റ്മെന്റും ഭരണ നിർവ്വഹണാധികാരസ്ഥന്റെ (സെക്രട്ടറിയുടെ) ഒരു റിപ്പോർട്ടും ആദ്യയോഗത്തിൽ ഗ്രാമസഭ മുമ്പാകെ വയ്ക്കുന്നു. ഗ്രാമസഭകളുടെ ശുപാർശകൾക്കും നിർദ്ദേശങ്ങൾക്കും ത്രിതല പഞ്ചായത്തുകൾ അർഹമായ പരിഗണന നൽകുന്നു. ഗ്രാമസഭകൾക്ക് പ്രത്യേക ചുമതലകളും പഞ്ചായത്തീരാജ് നിയമത്തിൽ വ്യവസ്ഥ ചെയ്തിട്ടുണ്ട്. വിവിധ ക്ഷേമപദ്ധതികൾക്കുള്ള ഗുണഭോക്താക്കളെ തെരഞ്ഞെടുക്കാനുള്ള ചുമതല ഗ്രാമസഭകൾക്കാണ്. ഗ്രാമസഭയിലൂടെയാണ് ഗ്രാമപ്പഞ്ചായത്തുകളുടെ പദ്ധതികൾ ഉരുത്തിരിയുന്നത്. പദ്ധതിയാസൂത്രണത്തിലും നിർവ്വഹണത്തിലും ഗ്രാമസഭകൾക്ക് നിർണ്ണായകമായ സ്ഥാനം നിയമം വ്യവസ്ഥ ചെയ്തിട്ടുണ്ട്.ഗ്രാമസഭയിൽ പാസ്സാക്കിയ ഒരു കാര്യം റദ്ദാക്കുന്നതിന് പാർലമെന്റിന് പോലും അധികാരമില്ല.
യൂക്ലിഡിന്റെ അൽഗൊരിതം
ശിഷ്ടത്തിന്റെ കുറഞ്ഞ കേവലവില ഉപയോഗിക്കുന്ന രീതി
തിരഞ്ഞെടുക്കുമ്പോഴാണ് (ഇവിടെ \varphi സുവർണ്ണാനുപാതമാണ്).
ചരിത്രം
സാധാരണയായി ഉപയോഗിക്കപ്പെടുന്ന അൽഗൊരിതങ്ങളിൽ ഏറ്റവും പഴക്കമേറിയവയിലാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സ്ഥാനം. ക്രിസ്തുവിനും മുന്നൂറുവർഷത്തോളം മുമ്പ് യൂക്ലിഡ് എഴുതിയ എലിമെന്റ്സ് എന്ന ഗ്രന്ഥത്തിൽ ഈ അൽഗൊരിതം പ്രത്യക്ഷപ്പെടുന്നു (ഏഴാം പുസ്തകം വാദം 1-2, പത്താം പുസ്തകം വാദം 2-3). ഏഴാം പുസ്തകത്തിൽ പൂർണ്ണസംഖ്യകൾക്കുവേണ്ടിയും പത്താം പുസ്തകത്തിൽ രേഖാഖണ്ഡങ്ങളുടെ നീളങ്ങൾക്കു വേണ്ടിയുമാണ് അൽഗൊരിതം ആസൂത്രണം ചെയ്തിരിക്കുന്നത്. ആധുനിക ഗണിതശാസ്ത്രത്തിൽ വാസ്തവികസംഖ്യകളുടെ ഉസാഘ കാണുന്നതിന് സമാനമാണ് ഇങ്ങനെ നീളങ്ങളുടെ ഉസാഘ കണ്ടുപിടിക്കുന്നത്. എന്നാൽ യൂക്ലിഡിന്റെ കാലത്ത് വാസ്തവികസംഖ്യകൾ എന്ന ആശയം ഉരുത്തിരിഞ്ഞിട്ടില്ലായിരുന്നു. a, b എന്നീ നീളങ്ങളുടെ ഉസാഘ g അവയെ രണ്ടിനെയും പൂൂർണ്ണസംഖ്യ എണ്ണം ഭാഗങ്ങളായി അളക്കാൻ സാധിക്കുന്ന ഏറ്റവും വലിയ നീളമാണ്. അതായത്, a, b എന്നിവ രണ്ടും gയുടെ പൂർണ്ണസംഖ്യാഗുണിതങ്ങളായി വരുന്ന തരത്തിലുള്ള ഏറ്റവും വലിയ നീളമാണ് g.
ഗ്രാമസഭ
അവലംബം
വർഗ്ഗം:ഇന്ത്യയിലെ തദ്ദേശസ്വയംഭരണം
യൂക്ലിഡിന്റെ അൽഗൊരിതം
ചരിത്രം
നൂറ്റാണ്ടുകൾക്കു ശേഷം ഇന്ത്യയിലും ചൈനയിലും യൂക്ലിഡിന്റെ അൽഗൊരിതം വീണ്ടും സ്വതന്ത്രമായി കണ്ടുപിടിക്കപ്പെട്ടു. ജ്യോതിഃശാസ്ത്രത്തിൽ കണക്കുകൂട്ടലുകൾ നടത്താനും കൃത്യതയാർന്ന കലണ്ടറുകൾ ഉണ്ടാക്കാനും വേണ്ടി ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കുന്നതിനായായിരുന്നു ഇത്. ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കുന്നതിൽ വളരെ ഫലപ്രദമായതിനാൽ അഞ്ചാം നൂറ്റാണ്ടിലെ ഗണിതശാസ്ത്രജ്ഞനും ജ്യോതിഃശാസ്ത്രജ്ഞനുമായ ആര്യഭടൻ അൽഗൊരിതത്തെ വിശേഷിപ്പിച്ചത് തവിടുപൊടിയാക്കുന്നത് (pulverizer) എന്നായിരുന്നു. ചൈനീസ് ശിഷ്ടപ്രമേയത്തിന്റെ ഒരു വിശിഷ്ടഭാഷ്യം (special case) സുൻസി സുവാൻജിങ് (Sunzi Suanjing) എന്ന ചൈനീസ് ഗ്രന്ഥത്തിൽ മുമ്പേ വിവരിച്ചിരുന്നുവെങ്കിലും 1247-ൽ ക്വിൻ ജിയുഷാവോ ആണ് ഷുഷു ജിയുസാങ് (Shushu Jiuzhang 數書九章) എന്ന ഗ്രന്ഥത്തിൽ പ്രമേയത്തിന്റെ സാമാന്യഭാഷ്യത്തിന്റെ നിർദ്ധാരണം പ്രസിദ്ധീകരിച്ചത്. യൂറോപ്പിൽ യൂക്ലിഡിന്റെ അൽഗൊരിതം ആദ്യമായി വിവരിക്കപ്പെടുന്നത് ക്ലോദ് ഗസ്പാർദ് ബാഷെ ദെ മെസിറിയാക് എഴുതിയ പ്രോബ്ലെം പ്ലെയ്സാന്ത് എ ദെലെക്താബ്ല് (Problèmes plaisants et délectables, ഹൃദ്യവും ആസ്വാദ്യവുമായ പ്രശ്നങ്ങൾ) എന്ന ഗ്രന്ഥത്തിന്റെ രണ്ടാം പതിപ്പിലാണ്. ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കാനും സതതഭിന്നങ്ങൾ കണ്ടുപിടിക്കാനുമാണ് യൂറോപ്പിൽ അൽഗൊരിതം ഉപയോഗിച്ചിരുന്നത്. അൽഗൊരിതത്തിന്റെ വികസിതരൂപം (വികസിത യൂക്ലിഡിയൻ അൽഗൊരിതം) പ്രസിദ്ധീകരിച്ചത് ഇംഗ്ലീഷ് ഗണിതശാസ്ത്രജ്ഞനായ നിക്കോളാസ് സോണ്ടേർസണായിരുന്നു. സതതഭിന്നങ്ങൾ കാര്യക്ഷമമായി കണക്കുകൂട്ടാൻ വേണ്ടി റോജർ കോട്സ് ആണ് ഈ രീതി കണ്ടുപിടിച്ചത് എന്നാണ് സോണ്ടേഴ്സൺ പറഞ്ഞത്.
പത്തൊമ്പതാം നൂറ്റാണ്ടിൽ ഗോസ്സിയൻ പൂർണ്ണസംഖ്യകൾ, ഐസൻസ്റ്റൈൻ പൂർണ്ണസംഖ്യകൾ മുതലായ പുതിയ സംഖ്യാവ്യവസ്ഥകൾ വികസിപ്പിച്ചെടുത്തത് യൂക്ലിഡിന്റെ അൽഗൊരിതം അടിസ്ഥാനമാക്കിയാണ്. 1815-ൽ ഗോസ്സിയൻ പൂർണ്ണസംഖ്യകളെ അനന്യമായി ഘടകക്രിയ ചെയ്യാമെന്ന് തെളിയിക്കാൻ കാൾ ഫ്രെഡറിക് ഗോസ്സ് ഈ അൽഗൊരിതം ഉപയോഗിച്ചു (1832-ലാണ് ഈ ഫലം പ്രസിദ്ധീകരിച്ചത്). 1801-ൽ പ്രസിദ്ധീകരിച്ച തന്റെ ഡിസ്ക്വിസിഷൻസ് അരിത്മെറ്റികേ (Disquisitiones Arithmeticae) എന്ന ഗ്രന്ഥത്തിൽ ഗോസ്സ് അൽഗൊരിതത്തെ മുമ്പേ പരാമർശിച്ചിരുന്നുവെങ്കിലും അത് സതതഭിന്നങ്ങൾ കണ്ടുപിടിക്കാനുള്ള ഒരു രീതി എന്ന നിലയിലായിരുന്നു. പീറ്റർ ഗുസ്താവ് ലെജോൻ ദിരിക്ലേ ആണ് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെ സംഖ്യാസിദ്ധാന്തത്തിന്റെ അടിസ്ഥാനശിലയായി വിവരിച്ചത്. പൂർണ്ണസംഖ്യകൾക്കു മാത്രമല്ല, യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാൻ സാധിക്കുന്ന മറ്റേത് സംഖ്യാവ്യവസ്ഥയും അനന്യമായ ഘടകക്രിയ ഉൾപ്പെടെയുള്ള സംഖ്യസിദ്ധാന്തപ്രമേയങ്ങൾ അനുസരിക്കും എന്ന് ദിരിക്ലേ നിരീക്ഷിച്ചു. സംഖ്യാസിദ്ധാന്തത്തെക്കുറിച്ചുള്ള ദിരിക്ലേയുടെ പ്രഭാഷണങ്ങൾ സംശോധനം ചെയ്യുകയും വ്യാപിപ്പിക്കുകയും ചെയ്ത റിച്ചാർഡ് ഡെഡിക്കിന്റ് ബീജീയ പൂർണ്ണസംഖ്യകൾ എന്ന പൂർണ്ണസംഖ്യകളുടെ പുതിയ സാമാന്യവൽക്കരണത്തെക്കുറിച്ച് പഠിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിച്ചു. ഗോസ്സിയൻ പൂർണ്ണസംഖ്യകളുടെ അനന്യമായ ഘടകക്രിയ ഉപയോഗിച്ച് ഡെഡിക്കിന്റ് ഫെർമയുടെ രണ്ട് വർഗ്ഗ പ്രമേയം ആദ്യമായി തെളിയിച്ചു. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സാമാന്യവൽക്കരണങ്ങൾ അനുസരിക്കുന്ന സംഖ്യാവ്യവസ്ഥകളായ യൂക്ലിഡിയൻ മണ്ഡലങ്ങളെ നിർവചിച്ചതും ഡെഡിക്കിന്റ് തന്നെ. പത്തൊമ്പതാം നൂറ്റാണ്ടിന്റെ അവസാനത്തോടെ ഡെഡിക്കിന്റിന്റെ ഗുണജങ്ങളുടെ സാമാന്യസിദ്ധാന്തം യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെക്കാൾ പ്രചാരം നേടി.
പത്തൊമ്പതാം നൂറ്റാണ്ടിൽ യൂക്ലിഡിന്റെ അൽഗൊരിതം വേറെയും ആവശ്യങ്ങൾക്ക് ഉപയോഗിക്കാൻ തുടങ്ങി. ഒരു ബഹുപദത്തിന് ഏതെങ്കിലും ഇടവേളയിൽ എത്ര വാസ്തവിക നിർദ്ധാരണങ്ങളുണ്ടെന്ന് കണ്ടുപിടിക്കാനുപയോഗിക്കുന്ന സ്റ്റുർമ് ശൃംഖലകൾ സൃഷ്ടിക്കുന്നതിന് ഈ അൽഗൊരിതം സഹായകമാണെന്ന് 1829-ൽ ചാൾസ് സ്റ്റുർമ് തെളിയിച്ചു. ഒരു വാസ്തവികസംഖ്യാഗണത്തിലെ സംഖ്യകളെ ഏത് പൂർണ്ണസംഖ്യാ ഗുണോത്തരങ്ങൾ കൊണ്ട് ഗുണിച്ച് തുക കണ്ടാലാണ് (അത് സാധ്യമെങ്കിൽ) പൂജ്യം ഫലമായി ലഭിക്കുക എന്ന് കണ്ടുപിടിക്കാനുപയോഗിക്കുന്ന Integer relation അൽഗൊരിതങ്ങളിൽ ആദ്യത്തേതാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതം. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ പിൻഗാമികളായി ഈ ആവശ്യത്തിനായി മറ്റനേകം അൽഗൊരിതങ്ങൾ അടൂത്തകാലത്തായി കണ്ടുപിടിച്ചിട്ടുണ്ട്.
1969-ൽ കോളും ഡേവിയും യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെ അടിസ്ഥാനമാക്കി രണ്ടുപേർക്കു കളിക്കാവുന്ന ഒരു കളി വികസിപ്പിച്ചു. യൂക്ലിഡിന്റെ കളി (The game of Euclid) എന്നാണ് ഇതിന്റെ പേര്. a, b വീതം എണ്ണം കല്ലുകളുള്ള രണ്ട് കൂമ്പാരങ്ങളാണ് കളിയുടെ തുടക്കത്തിലുണ്ടാവുക. ഓരോ കളിക്കാരിയും അവരുടെ അവസരമെത്തുമ്പോൾ ചെറിയ കൂമ്പാരത്തിന്റെ ഒരു ഗുണിതം എണ്ണം കല്ലുകൾ വലിയ കൂമ്പാരത്തിൽ നിന്ന് കുറയ്ക്കുന്നു. അതായത്, ഒരു അവസരത്തിന്റെ തുടക്കത്തിൽ കൂമ്പാരങ്ങളിൽ x, y വീതം കല്ലുകളാണുള്ളതെന്നും x നെക്കാളും ചെറുതാണ് y എന്നും ഇരിക്കട്ടെ. അടുത്ത അവസരത്തിൽ കളിക്കാരി x കല്ലുകളുള്ള വലിയ കൂമ്പാരത്തിൽ നിന്നും ചെറിയ കൂമ്പാരത്തിലെ കല്ലുകളുടെ എണ്ണമായ y യുടെ m ഇരട്ടി കുറച്ച് x − my കല്ലുകൾ ബാക്കിയാക്കുന്നു (ഈ സംഖ്യ പൂജ്യത്തിൽ കുറവാകുന്നത് അനുവദിനീയമല്ല). ഒരു കൂമ്പാരത്തിലെ കല്ലുകളെല്ലാം നീക്കുന്ന കളിക്കാരിയാണ് കളിയിലെ വിജയി. ഈ കളിയിൽ രണ്ടുപേരും നന്നായി കളിച്ചാൽ ആരാണ് ജയിക്കുകയെന്നും എങ്ങനെയാണ് ജയം കരസ്ഥമാക്കാൻ കഴിയുക എന്നും തുടക്കത്തിലെ കല്ലുകളിലെ എണ്ണത്തിൽ നിന്നു തന്നെ കണ്ടുപിടിക്കാം.
ബെസു അനന്യത
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിലെ സമവാക്യങ്ങൾ വിപരീതക്രമത്തിലെടുക്കുകയാണെങ്കിൽ ഹരണഫലങ്ങളായ q0, q1 മുതലായവ ഉപയോഗിച്ച് s, t എന്നിവയുടെ വിലകൾ കണക്കുകൂട്ടാം. അവസാനത്തെ സമവാക്യത്തിനു തൊട്ടു മുമ്പത്തേത് അനുസരിച്ച് g യുടെ വില ഹരണഫലമായ qN−1, മുമ്പത്തെ രണ്ട് പടികളിലെ ശിഷ്ടങ്ങളായ rN−2, rN−3 എന്നിവയുടെ വിലകളുമായി ബന്ധിപ്പിക്കാം
g = rN−1 = rN−3 − qN−1 rN−2.
ഇതേ രീതിയിൽ വലതുഭാഗത്തെ ശിഷ്ടങ്ങളെ മുൻ പടികളിലെ ഹരണഫലങ്ങളുടെയും ശിഷ്ടങ്ങളുടെയും അടിസ്ഥാനത്തിൽ എഴുതാം
rN−2 = rN−4 − qN−2 rN−3
,
rN−3 = rN−5 − qN−3 rN−4.
ആദ്യത്തെ സമവാക്യത്തിൽ rN−2, rN−3 എന്നിവയ്ക്കു പകരം ഈ രണ്ട് സമവാക്യങ്ങളുടെ വലതുഭാഗങ്ങൾ കൊടുത്താൽ g യെ ശിഷ്ടങ്ങളായ rN−4, rN−5 എന്നിവയുടെ രേഖീയസഞ്ചയമായി എഴുതാം. തുടക്കത്തിലെ സംഖ്യകളായ a, b എന്നിവ എത്തുന്നതു വരെ ഈ പ്രക്രിയ തുടരുന്നു:
r2 = r0 − q2 r1
r1 = b − q1 r0
r0 = a − q0 b.
ശിഷ്ടങ്ങളായ r0, r1 മുതലായവയ്ക്കുള്ള സമവാക്യങ്ങളെല്ലാം ഒന്നിനുപുറകെ ഒന്നായി ഉപയോഗിച്ചാൽ കിട്ടുന്ന സമവാക്യം g യെ a, b എന്നിവയുടെ രേഖീയസഞ്ചയമായി വിവരിക്കുന്നതായിരിക്കും: g = sa + tb. ബെസു അനന്യതയും ഈ പ്രക്രിയയും മറ്റ് യൂക്ലിഡിയൻ മണ്ഡലങ്ങളിലും ഉപയോഗിക്കാവുന്നതാണ്.
ഗുണജങ്ങൾ
ബെസു അനന്യത ഉപയോഗിച്ച് a, b എന്ന രണ്ടു സംഖ്യകളുടെ ഉസാഘയായ g യെ വേറൊരു തരത്തിൽ നിർവചിക്കാം. u, v എന്നിവ പൂർണ്ണസംഖ്യകളായി വരുന്ന വിധത്തിൽ ua + vb എന്ന രൂപത്തിൽ എഴുതാൻ സാധിക്കുന്ന എല്ലാ സംഖ്യകളുടെയും ഗണമെടുക്കുക. a യും b യും g യുടെ ഗുണിതങ്ങളായതിനാൽ ഈ ഗണത്തിലെ അംഗങ്ങളെല്ലാം തന്നെ g യുടെ ഗുണിതങ്ങളാണ്. a, b എന്നിവയുടെ ഏത് പൊതു ഘടകത്തിന്റെ കാര്യത്തിലും ഈ പ്രസ്താവന ശരിയാണ് — അതായത്, ഗണത്തിലെ അംഗങ്ങളെല്ലാം തന്നെ ഏത് പൊതു ഘടകത്തിന്റെയും ഗുണിതമായി വരും. എന്നാൽ മറ്റ് പൊതു ഘടകങ്ങളിൽ നിന്ന് വ്യത്യസ്തമായി, ഉസാഘ ഈ ഗണത്തിലെ അംഗമാണെന്ന് ബെസു അനന്യത പറയുന്നു (ഗണത്തിലെ അംഗങ്ങളുടെ നിർവചനത്തിൽ ബെസു അനന്യതയിലെ ഗുണോത്തരങ്ങൾ ഉപയോഗിച്ച് u = s, v = t എന്നെടുത്താൽ കിട്ടുന്ന അംഗത്തിന്റെ വില g ആയിരിക്കും‌). g യുടെ ഗുണിതമാണ് ഓരോ അംഗവും എന്നതിനാൽ മറ്റ് പൊതു ഘടകങ്ങളൊന്നും ഗണത്തിലെ അംഗങ്ങളാവാൻ സാധിക്കില്ല. g യുടെ ഗുണിതങ്ങളെല്ലാം തന്നെ ഗണത്തിൽ ഉൾപ്പെടുന്നുവെന്നും എളുപ്പത്തിൽ നിരീക്ഷിക്കാം, mg എന്ന ഗുണിതം ലഭിക്കാൻ u = ms, v = mt എന്ന ഗുണോത്തരങ്ങളെടുത്താൽ മതിയാവും. ബെസു അനന്യതയെ m കൊണ്ട് ഗുണിച്ചാൽ ഇത് തെളിയിക്കാം
ua + vb എന്ന രീതിയിൽ എഴുതാൻ സാധിക്കുന്ന സംഖ്യകളുടെ ഗണം ഉസാഘയുടെ ഗുണിതങ്ങളുടെ ഗണം തന്നെയാണെന്ന് ഇതുവഴി കാണാം. അതായത്, a, b എന്ന സംഖ്യകളെ പൂർണ്ണസംഖ്യകളെക്കൊണ്ട് ഗുണിച്ച് തുക കണ്ടാൽ ലഭിക്കുന്ന സംഖ്യകളുടെ ഗണം gcd(a, b) യുടെ ഗുണിതങ്ങളുടെ ഗണമാണ്. അതിനാൽ a, b എന്നിവയുടെ ഗുണജത്തിന്റെ (ideal) ജനകമാണ് (generator) അവയുടെ ഉസാഘയായ g. ഉസാഘയുടെ ഈ നിർവചനമാണ് ആധുനിക അമൂർത്തബീജഗണിതത്തിലെ സങ്കല്പങ്ങളായ പ്രിൻസിപൽ ഗുണജങ്ങൾ (ഒറ്റ അംഗം ജനകമായുള്ള ഗുണജം), പ്രിൻസിപൽ ഗുണജ മണ്ഡലം (ഓരോ ഗുണജവും പ്രിൻസിപൽ ആയുള്ള മണ്ഡലം) എന്നിവയുടെ അടിസ്ഥാനം.
ഈ ഫലമുപയോഗിച്ച് ചില ഗണിതപ്രശ്നങ്ങൾ നിർവചിക്കാനാകും. ഉദാഹരണമായി a, b വ്യാപ്തമുള്ള രണ്ട് ഗ്ലാസുകളെടൂക്കുക. ആദ്യത്തെ ഗ്ലാസ്സിന്റെ u ഗുണിതങ്ങളും രണ്ടാമത്തെ ഗ്ലാസ്സിന്റെ v ഗുണിതങ്ങളും കൂട്ടുകയോ കുറയ്ക്കുകയോ ചെയ്താൽ ua + vb എന്ന തരത്തിലെഴുതാവുന്ന ഏത് വ്യാപ്തവും കൃത്യമായി അളക്കാൻ സാധിക്കും. ഈ അളവുകളെല്ലാം തന്നെ g = gcd(a, b) യുടെ ഗുണിതങ്ങളാണെന്ന് കാണാം.
വികസിത യൂക്ലിഡിയൻ അൽഗൊരിതം
ബെസു അനന്യതയിലെ s, t എന്ന ഗുണോത്തരങ്ങളെ വികസിത യൂക്ലിഡിയൻ അൽഗൊരിതം ഉപയോഗിച്ച് കണ്ടുപിടിക്കാം. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തോട് രണ്ട് സമാവർത്തന സമവാക്യങ്ങൾ ചേർത്താണ് ഇത് സാധിക്കുന്നത്
sk = sk−2 − qksk−1
tk = tk−2 − qktk−1
സമാവർത്തനത്തിന്റെ തുടക്കത്തിലെ വിലകൾ ഇവയാണ്
s−2 = 1, t−2 = 0
N+1 പടികൾക്കൊടുവിൽ ശിഷ്ടം rN+1 = 0 ആകുമ്പോൾ അൽഗൊരിതം അവസാനിക്കുകയും s = sN, t = tN എന്നിങ്ങനെ ബെസു അനന്യതയിലെ ഗുണോത്തരങ്ങൾ ലഭിക്കുകയും ചെയ്യുന്നു.
ഇങ്ങനെ ലഭിക്കുന്ന സംഖ്യകൾ ബെസു അനന്യതയിലെ ഗുണോത്തരങ്ങളാണെന്ന് ഗണിതീയാഗമനം വഴി തെളിയിക്കാം. k − 1 പടികൾ വരെ സമാവർത്തനബന്ധം ശരിയാണെന്ന് കരുതുക. അതായത്, j യുടെ വില k യിൽ കുറവാകുമ്പോഴൊക്കെ താഴെ കൊടുത്തിരിക്കുന്ന സമവാക്യം ശരിയാണെന്നിരിക്കട്ടെ
rj = sj a + tj b
അൽഗൊരിതത്തിന്റെ k ആമത്തെ പടിയിൽ
rk = rk−2 − qkrk−1.
എന്ന സമവാക്യം ലഭിക്കുന്നു. സമാവർത്തനബന്ധം rk−2, rk−1 എന്നിവയ്ക്ക് ശരിയാണെന്നാണ് ഗണിതീയാഗമനത്തിൽ സങ്കല്പിച്ചിരിക്കുന്നത് എന്നതിനാൽ അവയെ യോജിച്ച s, t വിലകളുടെ അടിസ്ഥാനത്തിൽ എഴുതാം
rk = (sk−2 a + tk−2 b) − qk(sk−1 a + tk−1 b).
rk = sk a + tk b = (sk−2 − qksk−1) a + (tk−2 − qktk−1) b.
അൽഗൊരിതത്തിന്റെ തുടക്കത്തിലെ r−2, r−1 എന്നീ ശിഷ്ടങ്ങൾക്കും സമാവർത്തനസമവാക്യം ശരിയായതിനാൽ ഒടുവിൽ N ആമത്തെ പടിയിൽ
g = rN = sN a + tN b
എന്ന സമവാക്യം ലഭിക്കുന്നു. ബെസു അനന്യതയിലെ ഗുണോത്തരങ്ങൾ വലതുഭാഗത്തു കാണാം.
മാട്രിക്സ് രീതി
s, t എന്ന സംഖ്യകളെ തത്തുല്യമായ മാട്രിക്സ് രീതി ഉപയോഗിച്ചും കണ്ടുപിടിക്കാം. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിലെ പടികളിലെ സമവാക്യങ്ങളായ എന്നിവയെ ഹരണഫലങ്ങളുടെ 2×2 മാട്രിക്സുകളെക്കൊണ്ട് ശിഷ്ടങ്ങളുടെ ദ്വിമാന സദിശങ്ങളെ (vector) ഗുണിക്കുന്ന രീതിയിൽ എഴുതാം
എല്ലാ ഹരണഫല മാട്രിക്സുകളുടെയും ഗുണനഫലത്തെ M കൊണ്ട് സൂചിപ്പിച്ചാൽ യൂക്ലിഡിയൻ അൽഗൊരിതത്തെ ഇങ്ങനെ ലഘൂകരിച്ച് എഴുതാം g യെ a യുടെയും b യുടെയും രേഖീയസഞ്ചയമായി എഴുതാൻ ഈ സമവാക്യത്തിന്റെ രണ്ടു ഭാഗങ്ങളെയും M ന്റെ മാട്രിക്സ് വിപരീതത്തെക്കൊണ്ട് ഗുണിച്ചാൽ മതിയാകും. ഓരോ ഹരണഫല മാട്രിക്സിന്റെയും സാരണികം (determinant) -1 ആയതിനാൽ അവയുടെ ഗുണനഫലമായ M ന്റെ സാരണികം (−1)N+1 ആണ്. ഇത് ഒരിക്കലും പൂജ്യമാവുകയില്ല എന്നതിനാൽ M ന്റെ മാട്രിക്സ് വിപരീതം കണ്ടുപിടിക്കുന്നതും സമവാക്യം നിർദ്ധരിക്കുന്നതും എപ്പോഴും സാധ്യമാണ്. ഈ മാട്രിക്സ് സമവാക്യത്തിന്റെ ആദ്യത്തെ വരി
g = (−1)N+1 ( m22 a − m12 b)
എന്നായതിനാൽ ബെസു അനന്യതയിലെ പൂർണ്ണസംഖ്യാ ഗുണോത്തരങ്ങൾ s = (−1)N+1m22, t = (−1)Nm12 എന്നിവയാണെന്നു കാണാം. ഓരോ പടിയിലും രണ്ട് ഗുണനങ്ങളും രണ്ട് സങ്കലനങ്ങളും ആവശ്യം വരുന്നതിനാൽ മാട്രിക്സ് രീതി തത്തുല്യമായ സമാവർത്തനത്തിന്റെ അത്ര തന്നെ കാര്യക്ഷമമാണെന്നു വരുന്നു.
യൂക്ലിഡിന്റെ പ്രമേയികയും അനന്യമായ ഘടകക്രിയയും
യൂക്ലിഡിന്റെ അൽഗൊരിതം പ്രയോഗിക്കുന്ന മിക്ക അവസരങ്ങളിലും ബെസു അനന്യത അത്യന്താപേക്ഷിതമാണ്. പൂർണ്ണസംഖ്യകളെ അഭാജ്യസംഖ്യകളുടെ ഗുണനഫലമായി എഴുതുന്ന രീതി അനന്യമാണെന്ന അങ്കഗണിതത്തിലെ അടിസ്ഥാന സിദ്ധാന്തം ഇതിന്നുദാഹരണമാണ്.
L എന്ന സംഖ്യ u, v എന്നീ സംഖ്യകളുടെ ഗുണനഫലമാണെന്നു കരുതുക. അതായത്, L = uv. ഇനി w എന്ന മറ്റൊരു സംഖ്യ L ന്റെ ഘടകമാണെന്നു കരുതുക. u വിനോട് സഹ അഭാജ്യമാണ് w എങ്കിൽ അത് v യുടെ ഘടകമായിരിക്കണം എന്ന് ഇപ്രകാരം തെളിയിക്കാം: u, w എന്ന സംഖ്യകളുടെ ഉസാഘ 1 ആയതിനാൽ ബെസു അനന്യത ഉപയോഗിച്ച്
1 = su + tw
എന്ന സമവാക്യത്തിന് നിർദ്ധാരണമായി s, t എന്ന പൂർണ്ണസംഖ്യകൾ കണ്ടുപിടിക്കാനാകും. സമവാക്യത്തിന്റെ രണ്ടു ഭാഗവും v കൊണ്ടു ഗുണിച്ചാൽ
v = suv + twv = sL + twv
യൂക്ലിഡിന്റെ പ്രമേയിക ഉപയോഗിച്ച് ഏതൊരു പൂർണ്ണസംഖ്യയുടെയും ഘടകക്രിയ അനന്യമാണെന്ന് തെളിയിക്കാം. ഇങ്ങനെയല്ല, L നെ m, n വീതം ഘടകങ്ങളുള്ള രണ്ട് രീതികളിൽ ഘടകക്രിയ ചെയ്യാം എന്ന് കരുതുക
p എന്ന ഓരോ അഭാജ്യസംഖ്യയും L ന്റെ ഘടകമായതിനാൽ അത് q ഘടകങ്ങളിലൊന്നിന്റെയും ഘടകമായിരിക്കണം. എന്നാൽ q യും ഒരു അഭാജ്യസംഖ്യയായതുകൊണ്ട് p = q എന്ന് വരുന്നു. ഇങ്ങനെ അഭാജ്യ ഘടകങ്ങളെയെല്ലാം ഓരോന്നോരോന്നായി ജോടികളാക്കിയ ശേഷം L ൽ നിന്ന് ഹരിച്ചെടുത്ത് ഈ പ്രക്രിയ തുടരുകയാണെങ്കിൽ ഘടകങ്ങളൊന്നും ബാക്കിയാവില്ലെന്നു കാണാം. അതായത്, അഭാജ്യഘടകങ്ങളുടെ ക്രമത്തിൽ വ്യതാസമുണ്ടാകാമെന്നതൊഴിച്ചാൽ ഏതു സംഖ്യയെയും അഭാജ്യസംഖ്യകളായി ഘടകക്രിയ ചെയ്യുന്ന രീതി അനന്യമാണ്. ഈ ഫലം ഗണിതത്തിലെ ഒട്ടേറെ തെളിവുകളിൽ പ്രധാന പങ്കു വഹിക്കുന്നു.
രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ
ax + by = c
ഇവിടെ a, b, c എന്നിവ തന്നിരിക്കുന്ന പൂർണ്ണസംഖ്യകളാണ്; x, y എന്നിവ കണ്ടൂപിടിക്കേണ്ട പൂർണ്ണസംഖ്യകളും. ഇതിനെ മോഡ്യുലർ അങ്കഗണിതമുപയോഗിച്ച് x നുള്ള സമവാക്യമായി എഴുതാം:
ax ≡ c mod b.
a യുടെയും b യുടെയും ഉസാഘയാണ് g എന്നിരിക്കട്ടെ. ax + by യിലെ രണ്ട് പദങ്ങളും g യുടെ ഗുണിതങ്ങളായതിനാൽ c യും ഗുണിതമായിരിക്കണമെന്നു വരുന്നു, അല്ലാത്തപക്ഷം സമവാക്യത്തിന് നിർദ്ധാരണങ്ങളുണ്ടാവില്ല. സമവാക്യത്തിന്റെ രണ്ടു ഭാഗത്തെയും c/g കൊണ്ടു ഹരിച്ചാൽ സമവാക്യം ബെസു അനന്യതയുടെ രൂപത്തിലേക്കു മാറുന്നു
sa + tb = g
ഇവിടെ s ന്റെയും t യുടെയും വില വികസിത യൂക്ലിഡിയൻ അൽഗൊരിതം ഉപയോഗിച്ച് കണ്ടുപിടിക്കാം. ഡയൊഫന്റൈൻ സമവാക്യത്തിന്റെ ഒരു നിർദ്ധാരണം ഇങ്ങനെ കണ്ടുപിടിക്കാം: x1 = s (c/g), y1 = t (c/g).
സാധാരണ ഗതിയിൽ ഒരു രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യത്തിന്റെ പരിഹാരങ്ങളുടെ എണ്ണം പൂജ്യമോ അനന്തമോ ആണ്. പരിഹാരങ്ങൾ അനന്തമാണെങ്കിൽ കണ്ടുപിടിക്കുന്നതെങ്ങനെയെന്നു നോക്കാം. ഒരേ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യത്തിന്റെ നിർദ്ധാരണങ്ങളാണ് (x1, y1), (x2, y2) എന്നു കരുതുക. അതായത്,
ax1 + by1 = c = ax2 + by2
അഥവാ
a(x1 − x2) = b(y2 − y1).
അതായത്, രണ്ട് പരിഹാരങ്ങളുടെ x വിലകൾക്കിടയിലുള്ള കുറഞ്ഞ വ്യത്യാസം b/g യും y വിലകൾക്കിടയിലുള്ള കുറഞ്ഞ വ്യത്യാസം a/g യുമാണ്. അതായത്, സമവാക്യത്തിന്റെ നിർദ്ധാരണങ്ങളെ സാമാന്യരൂപത്തിൽ ഇങ്ങനെയെഴുതാം:
x = x1 − bu/g
y = y1 + au/g
. u വിന്റെ വില എല്ലാ പൂർണ്ണസംഖ്യകളുമെടുത്താൽ (x1, y1) എന്ന ഒറ്റ നിർദ്ധാരണത്തിൽ നിന്ന് അനന്തം എണ്ണം പരിഹാരങ്ങളെല്ലാം കണ്ടുപിടിക്കാം. പരിഹാരത്തിലെ സംഖ്യകളെല്ലാം എണ്ണൽസംഖ്യകളാകണമെന്ന് നിഷ്കർഷിച്ചാൽ (x > 0, y > 0) പരിഹാരങ്ങളുടെ എണ്ണം പരിമിതമാണെന്നു വരാം. ചരങ്ങളെക്കാൾ എണ്ണം സമവാക്യങ്ങളുള്ള ചില ഡയൊഫന്റൈൻ വ്യവസ്ഥകൾക്ക് പരിമിതമായ പരിഹാരങ്ങൾ മാത്രമുണ്ടാകാൻ ഈ നിഷ്കർഷ കാരണമാകാം; പൂർണ്ണസംഖ്യകൾക്ക് പകരം വാസ്തവികസംഖ്യകൾ ഉപയോഗിച്ച് നിർദ്ധരിക്കുന്ന രേഖീയ സമവാക്യ വ്യവസ്ഥകളിൽ ഇത് ഒരിക്കലും സംഭവിക്കില്ല.
ഗുണനവിപരീതവും ആർ.എസ്.എ. അൽഗൊരിതവും
a ഇത്തരമൊരു ക്ഷേത്രത്തിലെ പൂജ്യമല്ലാത്ത അംഗമാണെങ്കിൽ അതിന് അനന്യമായ മോഡ്യുലർ ഗുണനവിപരീതം ഉണ്ടായിരിക്കും. a യുടെ മോഡ്യുലർ ഗുണനവിപരീതം എന്നത് aa−1 = a−1a ≡ 1 mod m. എന്ന സമവാക്യം അനുസരിക്കുന്ന a−1 എന്ന സംഖ്യയാണ്. ax ≡ 1 mod m, എന്ന സർവ്വസമതയ്ക്ക് നിർദ്ധാരണം കാണുന്നതു വഴി ഈ സംഖ്യ കണ്ടുപിടിക്കാം. ഇത് താഴെക്കൊടുത്തിരിക്കുന്ന രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യം നിർദ്ധരിക്കുന്നതിന് തുല്യമാണ്
ax + my = 1.
ഈ സമവാക്യം മേൽ വിവരിച്ചതുപോലെ യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് നിർദ്ധരിക്കാം. മൊഡ്യുലാർ ഗുണനവിപരീതങ്ങൾ കാണുന്നത് ഇകൊമേഴ്സിൽ വ്യാപകമായി ഉപയോഗിക്കുന്ന ആർ.എസ്.എ. അൽഗൊരിതത്തിന്റെ അവശ്യഭാഗമാണ്. ക്ഷേത്രങ്ങൾക്കു പകരം വലയങ്ങളാണ് ആർ.എസ്.എ. അൽഗൊരിതത്തിൽ ഉപയോഗിക്കുന്നതെങ്കിലും വലയങ്ങളിലും (ഗുണനവിപരീതമുള്ള) അംഗങ്ങളുടെ ഗുണനവിപരീതം യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് കണ്ടുപിടിക്കാം. വാർത്താവിനിമയത്തിൽ തെറ്റുകൾ തിരുത്താനുപയോഗിക്കുന്ന എറർ കറക്റ്റിങ് കോഡുകളിലും യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് ഉപയോഗമുണ്ട്. ഉദാഹരണമായി, ഗാൽവ ക്ഷേത്രങ്ങൾ ഉപയോഗിക്കുന്ന ബി.സി.എച്. കോഡ്, റീഡ്-സോളമൻ കോഡ് എന്നിവ ഡീകോഡ് ചെയ്യാൻ ബെർൽകാംപ്-മാസ്സേ അൽഗൊരിതത്തിനു പകരമായി ഇത് ഉപയോഗിക്കാം.
ചൈനീസ് ശിഷ്ട പ്രമേയം
ഒന്നിലേറെ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കാനും യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം.. ഇത്തരം സമവാക്യങ്ങൾ ചൈനീസ് ശിഷ്ട പ്രമേയത്തിൽ (Chinese remainder theorem) കാണാം. പൂർണ്ണസംഖ്യകളെ വിവരിക്കാനുള്ള ഒരു വ്യത്യസ്തമായ രീതിയാണിത്. സംഖ്യകളെ അവയുടെ അക്കങ്ങളുപയോഗിച്ച് വിവരിക്കുന്നതിനു പകരം mi എന്ന പരസ്പരം സഹ-അഭാജ്യമായ N സംഖ്യകൾ കൊണ്ടു ഹരിച്ചാൽ കിട്ടുന്ന ശിഷ്ടങ്ങളായ xi എന്നിവ കൊണ്ട് സൂചിപ്പിക്കുന്നു. ഈ സർവ്വസമതകളെ ഇപ്രകാരം എഴുതാം:
xi എന്ന ശിഷ്ടങ്ങളുപയോഗിച്ച് x കണ്ടുപിടിക്കുകയാണ് ലക്ഷ്യം. ഈ സമവാക്യങ്ങളെയെല്ലാം കൂട്ടിച്ചേർത്ത് mi എന്ന മാപാങ്കങ്ങളുടെ (moduli) ഗുണനഫലമായ M മാപാങ്കമായുള്ള ഒറ്റ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യമായി മാറ്റുക വഴി ഇത് സാധിക്കാം. mi ഒഴികെയുള്ള മാപാങ്കങ്ങളുടെ ഗുണനഫലത്തെ Mi എന്ന് വിളിക്കുക: താഴെ കൊടുത്തിരിക്കുന്ന സമവാക്യമനുസരിക്കുന്ന (യഥാർത്ഥത്തിൽ N സമവാക്യങ്ങൾ) സംഖ്യകൾ കണ്ടുപിടിക്കുകയാണ് നിർദ്ധാരണത്തിലെ പ്രധാന പടി hi എന്ന സംഖ്യകളിൽ നിന്നും x കണ്ടുപിടിക്കാൻ ഈ സൂത്രവാക്യമുപയോഗിക്കാം
hi എന്ന സംഖ്യകൾ Mi എന്നിവയുടെ ഗുണനവിപരീതങ്ങളായതിനാൽ മുൻപത്തെ ഭാഗത്ത് വിവരിച്ചതുപോലെ അവയെ യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് കണ്ടുപിടിക്കാം.
സ്റ്റേൺ-ബ്രോക്കോട്ട് ട്രീ
എല്ലാ ധന ഭിന്നകസംഖ്യകളെയും ഒരു അനന്ത ബൈനറി സർച്ച് ട്രീയുടെ രൂപത്തിൽ ക്രമീകരിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം. ഈ ട്രീ സ്റ്റേൺ-ബ്രോക്കോട്ട് ട്രീ എന്നറിയപ്പെടുന്നു. 1 എന്ന സംഖ്യയെ 1/1 എന്ന ഭിന്നസംഖ്യയുടെ രൂപത്തിൽ ട്രീയുടെ മൂലത്തിൽ (root) നിക്ഷേപിക്കാം. a/b എന്ന മറ്റേത് സംഖ്യയുടെയും ട്രീയിലെ സ്ഥാനം നിർണ്ണയിക്കുന്നത് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മൂലരൂപമുപയോഗിച്ച് ഉസാഘയായ gcd(a,b) കണ്ടാണ്. അൽഗൊരിതത്തിന്റെ മൂലരൂപത്തിൽ ശിഷ്ടം കാണുന്നതിനു പകരം വലിയ സംഖ്യയിൽ നിന്ന് ചെറുത് കുറയ്ക്കുകയും സംഖ്യകൾ തുല്യമാകുമ്പോൾ നിർത്തുകയുമാണല്ലോ ചെയ്യുന്നത്. ആദ്യത്തെ സംഖ്യയിൽ നിന്ന് രണ്ടാമത്തേത് കുറയ്ക്കുകയാണെങ്കിൽ ട്രീയിലെ ഒരു ശീഷത്തിൽ നിന്ന് അതിന്റെ വലത്തെ പിൻഗാമിയിലേക്ക് (right child) നീങ്ങുന്നു, പകരം രണ്ടാമത്തെ സംഖ്യയിൽ നിന്ന് ആദ്യത്തേതാണ് കുറയ്ക്കുന്നതെങ്കിൽ ഇടത്തെ പിൻഗാമിയിലേക്കാണ് (left child) നീങ്ങുക. മൂലത്തിൽ നിന്ന് തുടങ്ങി ഈ നിയമമനുസരിച്ച് നീങ്ങിയാൽ അൽഗൊരിതം അവസാനിക്കുമ്പോൾ എത്തുന്ന ശീർഷമാണ് ട്രീയിൽ a/b യുടെ സ്ഥാനം. ഈ പഥത്തിന്റെ നീളവും ക്രമവും a/b അതിന്റെ ലഘൂകരിച്ച രൂപത്തിലാണോ സൂചിപ്പിച്ചിരിക്കുന്നത് എന്നതിനെ ആശ്രയിക്കുന്നില്ല. അതിനാൽ ഓരോ ധനഭിന്നകസംഖ്യയുടെയും ട്രീയിലെ സ്ഥാനം അനന്യമാണെന്നു വരുന്നു.
ഉദാഹരണമായി, 3/4 ന്റെ ശീർഷത്തിലെത്താൻ ട്രീയുടെ മൂലത്തിൽ തുടങ്ങി ഇടത്തേക്ക് ഒരു തവണയും തുടർന്ന് വലത്തേക്ക് രണ്ടു തവണയും നീങ്ങുന്നു:
ഭിന്നകസംഖ്യകളുടെ മറ്റൊരു ബൈനറി ട്രീ ആയ കാൽകിൻ-വിൽഫ് ട്രീയുമായും യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് ബന്ധമുണ്ട്. പഥം വിപരീതക്രമത്തിലാണ് നിർമ്മിക്കുന്നത് എന്നതാണ് വ്യത്യാസം: അതായത്, ട്രീയുടെ മൂലത്തിൽ നിന്ന് സംഖ്യയുടെ ശീർഷത്തിലേക്കുള്ള പഥത്തിനു പകരം സംഖ്യയുടെ ശീർഷത്തിൽ നിന്ന് ട്രീയുടെ മൂലത്തിലേക്ക് പോകുന്നു.
സതതഭിന്നം
സതതഭിന്നങ്ങളുമായും (continued fraction) യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് അടുത്ത ബന്ധമുണ്ട്. അൽഗൊരിതത്തിലെ പടികളുടെ സമവാക്യങ്ങളെ ഇപ്രകാരവും എഴുതാം: ഓരോ സമവാക്യത്തിന്റെയും വലതുഭാഗത്തെ രണ്ടാമത്തെ പദം അടുത്ത സമവാക്യത്തിന്റെ ഇടതുഭാഗത്തിന്റെ വ്യുൽക്രമമാണ്. അതിനാൽ ആദ്യത്തെ രണ്ട് സമവാക്യങ്ങളെയും ഈ വിധത്തിൽ കൂട്ടിച്ചേർക്കാം മൂന്നാമത്തെ സമവാക്യമുപയോഗിച്ച് ഛേദത്തിലെ r1/r0 എന്ന പദത്തെ വികസിപ്പിക്കാം ഓരോ പടിയിലെയും rk/rk−1 എന്ന ശിഷ്ടങ്ങളുടെ അനുപാതത്തെ ഇങ്ങനെ അടുത്ത സമവാക്യമുപയോഗിച്ച് വികസിപ്പിക്കാം. അവസാനത്തെ സമവാക്യവും ഇങ്ങനെ ഉപയോഗിച്ചു കഴിയുമ്പോൾ ഒരു സതതഭിന്നം ലഭിക്കുന്നു മുകളിൽ gcd(1071, 462) കണ്ടുപിടിച്ചപ്പോൾ qk എന്ന ഹരണഫലങ്ങളായി ലഭിച്ചത് 2, 3, 7 എന്ന സംഖ്യകളായിരുന്നു. അതിനാൽ 1071/462 എന്ന ഭിന്നസംഖ്യയെ സതതഭിന്നരൂപത്തിൽ ഇപ്രകാരം എഴുതാം ഇത് ശരിയാണെന്ന് നേരിട്ട് കണക്കുകൂട്ടിയാൽ കാണാൻ വിഷമമില്ല. ഇപ്രകാരം ഏത് ഭിന്നകസംഖ്യയുടെയും സതതഭിന്നരൂപം യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് കണ്ടുപിടിക്കാം.
ഫാക്റ്ററൈസേഷൻ അൽഗൊരിതങ്ങൾ
വലിയ സംഖ്യകളുടെ ഘടകക്രിയ ചെയ്യാനുപയോഗിക്കുന്ന ഫാക്റ്ററൈസേഷൻ അൽഗൊരിതങ്ങളിലെ ഒരു പ്രധാന പടിയാണ് ഉസാഘ കാണുന്നത്. പൊളാർഡ്സ് റോ അൽഗൊരിതം, ഷോർ അൽഗൊരിതം, ഡിക്സൺ രീതി ലെൻസ്ട്ര എലിപ്റ്റിക് കർവ് ഫാക്റ്ററൈസേഷൻ എന്നിവയെല്ലാം ഇങ്ങനെ ഉസാഘ ആവശ്യമുള്ള അൽഗൊരിതങ്ങളാണ്. ഇതിനായ ഉസാഘ കാണാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം. സതതഭിന്ന ഫാക്റ്ററൈസേഷൻ രീതിയിൽ സതതഭിന്നങ്ങൾ കണ്ടുപിടിക്കാനും അൽഗൊരിതം സഹായിക്കുന്നു.
ഗണനപരമായ സങ്കീർണ്ണത
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ ഗണനപരമായ സങ്കീർണ്ണത സമഗ്രമായി പഠിക്കപ്പെട്ടിട്ടുണ്ട്. അൽഗൊരിതത്തിന്റെ കാര്യക്ഷമത കണ്ടുപിടിക്കാൻ അൽഗൊരിതത്തിലെ പടികളുടെ എണ്ണത്തെ ഒരു പടിയുടെ ഗണനപരമായ ചിലവ്വുകൊണ്ട് ഗുണിച്ചാൽ മതി. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെക്കുറിച്ച് ഇത്തരത്തിലുള്ള ആദ്യത്തെ പഠനം നടത്തിയത് 1811-ൽ എ.എ.എൽ. റെയ്നോഡ് ആണ്, u, v എന്ന സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കാൻ v പടികൾ മതിയെന്ന് കണ്ടുപിടിക്കുകയും പിന്നീട് ഈ സീമ v/2 + 2 ആയി മെച്ചപ്പെടുത്തുകയും ചെയ്തു. എമിൽ ലെഷെർ 1837-ൽ അൽഗൊരിതം ഏറ്റവുമധികം പടികളെടൂക്കുന്ന അവസ്ഥയെക്കുറിച്ച് പഠിച്ചു. അനുക്രമമായ ഫിബനാച്ചി ശ്രേണികളുടെ ഉസാഘ കണ്ടുപിടിക്കുമ്പോഴാണ് ഇത് സംഭവിക്കുന്നത്. ഇതിനു ശേഷം 1841-ൽ പിയേർ ജോസെഫ് എറ്റിയെൻ ഫിങ്ക് പടികളുടെ എണ്ണം 2 log2 v + 1 മതിയെന്നും അതിനാൽ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത ഇൻപുട്ട് വലിപ്പത്തിന്റെ ബഹുപദമാണെന്നും (polynomial time) കണ്ടെത്തി. ഫിങ്കിന്റെ അപഗ്രഥനം പരിഷ്കരിച്ച ഗബ്രിയേൽ ലാമേ ചെറിയ സംഖ്യയായ b യെ ദശാംശസമ്പ്രദായത്തിൽ എഴുതാനെടുക്കുന്ന അക്കങ്ങളുടെ എണ്ണമായ h ന്റെ അഞ്ചിരട്ടി പടികളേ അൽഗൊരിതത്തിൽ ആവശ്യം വരൂ എന്ന് തെളിയിച്ചു.
ഒരു സംഖ്യ എത്ര വലുതാണെങ്കിലും അതിനെ കമ്പ്യൂട്ടറിന്റെ മെമ്മറിയിൽ ഒറ്റ മഷീൻ വാക്കിൽ സൂക്ഷിക്കാം എന്ന് കരുതുകയാണെങ്കിൽ സംഖ്യകൾക്കു മേൽ ഹരണം, ശിഷ്ടം മുതലായ സംക്രിയകൾ നടത്താൻ എടുക്കുന്ന സമയം സ്ഥിരമാണ് (സംഖ്യയുടെ വലിപ്പത്തെ ആശ്രയിക്കുന്നില്ല). ഈ കല്പനയെ uniform cost model എന്നാണ് അൽഗൊരിതങ്ങളുടെ ഗണനപരമായ സങ്കീർണ്ണതാസിദ്ധാന്തത്തിൽ വിളിക്കുന്നത്. ഈ അനുമാനത്തിനു കീഴിൽ അൽഗൊരിതത്തിന്റെ ഓരോ പടിയും ചെയ്യാനെടുക്കുന്ന സമയം ഒരു സ്ഥിരാങ്കമാണെന്നും അതിനാൽ അൽഗൊരിതത്തിന്റെ ആകെ സങ്കീർണ്ണത O(h) ആണെന്നും വരുന്നു. എന്നാൽ ഒരു മഷീൻ വാക്കിലൊതുങ്ങാത്ത വലിയ സംഖ്യകളുടെ കാര്യത്തിൽ ഈ കല്പന ശരിയാവില്ല. വലിയ സംഖ്യകളുടെ ശിഷ്ടം കാണാനെടൂക്കുന്ന അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത O(h2) വരെ ആകാം എന്നതിനാൽ ടെലിസ്കോപിങ് സീരീസ് ഉപയോഗിച്ച് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മൊത്തം സങ്കീർണ്ണതയും O(h2) ആണെന്നു കാണാം. വലിയ സംഖ്യകളെ കാര്യക്ഷമമായി ഗുണിക്കാനുപയോഗിക്കുന്ന ഷോൺഹാഗെ-സ്ട്രാസെൻ അൽഗൊരിതം മുതലായവ ഉപയോഗിച്ച് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത ഇനിയും കുറച്ച് ക്വാസിലീനിയർ (quasilinear) വരെയാക്കാം.
പടികളുടെ എണ്ണം
T(a, b) = T(m, n)
എന്നു ലഭിക്കുന്നു (യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിലെ എല്ലാ പടികളെയും g കൊണ്ട് ഹരിച്ചാൽ ഇത് കാണാം) a, b എന്ന സംഖ്യകളെ രണ്ടിനെയും w എന്ന സംഖ്യകൊണ്ട് ഗുണിച്ചാലും പടികളുടെ എണ്ണത്തിൽ മാറ്റം വരില്ല, T(a, b) = T(wa, wb). അതിനാൽ അടുത്തടുത്ത സംഖ്യകളുടെ കാര്യത്തിൽ പോലും ഉസാഘ കാണാനെടുക്കുന്ന പടികളുടെ എണ്ണം വ്യത്യാസപ്പെടാം. അതായത്, T(a, b) യും T(a, b + 1) യും കാണാനാവശ്യമായ പടികൾ അവയുടെ ഉസാഘയനുസരിച്ച് വളരെ വ്യത്യസ്തമാണെന്നു വരാം.
യൂക്ലിഡിന്റെ അൽഗൊരിതം സമാവർത്തനമുപയോഗിക്കുന്നതിനാൽ താഴെ കൊടുത്തിരിക്കുന്ന സമവാക്യം ലഭിക്കുന്നു
T(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1.
ഇവിടെ T(x, 0) = 0 എന്ന് കല്പിച്ചിരിക്കുന്നു.
കൂടിയ വില
ഉസാഘ കണ്ടുപിടിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിൽ N പടികൾ ആവശ്യമായ ഏറ്റവും ചെറിയ സംഖ്യാജോടി ഫിബനാച്ചി സംഖ്യകളായ FN+2, FN+1 എന്നിവയാണ്. കൂടുതൽ കൃത്യമായി പറയുകയാണെങ്കിൽ, യൂക്ലിഡിന്റെ അൽഗൊരിതം a > b ആയ രണ്ടു സംഖ്യകളുടെ ഉസാഘ കാണാൻ N പടികളെടുക്കുന്നുവെങ്കിൽ a ≥ FN+2, b ≥ FN+1 ആയിരിക്കും. ഗണിതീയാഗമനം വഴി ഇത് തെളിയിക്കാം. N = 1 ആണെങ്കിൽ a യുടെ ഭാജകമായിരിക്കണം b. ഇങ്ങനെ വരുന്ന ഏറ്റവും ചെറിയ സംഖ്യകൾ b = 1, a = 2 ആണ്. ഇവ യഥാക്രമം ഫിബനാച്ചി സംഖ്യകളായ F2, F3 എന്നിവയാണെന്നു കാണാം. N ന്റെ M − 1 വരെയുള്ള എല്ലാ വിലകൾക്കും ഈ പ്രസ്താവന ശരിയാണെന്നു കരുതുക. M പടികളുള്ള അൽഗൊരിതത്തിന്റെ ആദ്യത്തെ ക്രിയ a = q0b + r0 കാണുകയാണ്, ഇതിനു ശേഷം b > r0 എന്നിവയുടെ ഉസാഘ M − 1 പടികളുപയോഗിച്ച് കാണുന്നു. ഗണിതീയാഗമനത്തിലെ പരികല്പനയനുസരിച്ച് b ≥ FM+1, r0 ≥ FM ആണല്ലോ. അതിനാൽ ഇതാണ് M ആമത്തെ പടിയിൽ തെളിയിക്കേണ്ടിയിരുന്ന അസമത. 1944-ൽ ഗബ്രിയേൽ ലാമേ ആണിത് തെളിയിച്ചത്. ഗണനപരമായ സങ്കീർണ്ണതാസിദ്ധാന്തത്തിന് തുടക്കം കുറിച്ചത് ഈ ഫലമാണ്, ഫിബനാച്ചി സംഖ്യകളുടെ ആദ്യത്തെ പ്രായോഗികമായ ഉപയോഗവും ഈ തെളിവിലായിരുന്നു.