![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Euclid%2527s_algorithm_Book_VII_Proposition_2_3.png/640px-Euclid%2527s_algorithm_Book_VII_Proposition_2_3.png&w=640&q=50)
യൂക്ലിഡിന്റെ അൽഗൊരിതം
രണ്ട് സംഖ്യകളുടെ ഉത്തമ സാധാരണ ഘടകം കണ്ടുപിടിക്കാനുള്ള അൽഗൊരിതം / From Wikipedia, the free encyclopedia
രണ്ട് എണ്ണൽ സംഖ്യകളുടെ ഉത്തമ സാധാരണ ഘടകം (ഉസാഘ) കാര്യക്ഷമമായി കണ്ടുപിടിക്കാനുള്ള ഒരു ഉപായമാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതം അഥവാ യൂക്ലിഡിയൻ അൽഗൊരിതം. പ്രാചീന ഗ്രീസിലെ ഗണിതശാസ്ത്രജ്ഞനായിരുന്ന യൂക്ലിഡിന്റെ പേരിലാണ് ഇത് അറിയപ്പെടുന്നത്. ക്രിസ്തുവിന് മുന്നൂറ് വർഷം മുമ്പ് എലിമെന്റ്സ് എന്ന തന്റെ ഗ്രന്ഥത്തിൽ യൂക്ലിഡാണ് ആദ്യമായി ഈ രീതി വിവരിച്ചത്. ഒരു പ്രശ്നത്തിന്റെ നിർദ്ധാരണത്തിന് പടിപടിയായി ഉപയോഗിക്കുന്ന നിശ്ചിതമായ ക്രിയകളുടെ ശ്രേണിയായ അൽഗൊരിതത്തിന് ഉത്തമോദാഹരണമാണിത്. ഭിന്നസംഖ്യകളെ ലഘൂകരിക്കാനും സംഖ്യാസിദ്ധാന്തത്തിലെയും ഗൂഢാലേഖനവിദ്യയിലെയും മറ്റനേകം കണക്കുകൂട്ടലുകളിലും ഈ അൽഗൊരിതം ഉപയോഗിക്കുന്നു.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Euclid%27s_algorithm_Book_VII_Proposition_2_3.png/320px-Euclid%27s_algorithm_Book_VII_Proposition_2_3.png)
രണ്ടു സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കുമ്പോൾ വലിയ സംഖ്യയ്ക്കു പകരം സംഖ്യകളുടെ വ്യത്യാസം ഉപയോഗിച്ചാൽ ഉസാഘയിൽ വ്യത്യാസം വരുന്നില്ല എന്ന തത്ത്വമാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് അടിസ്ഥാനം. ഉദാഹരണമായി, 252, 105 എന്നീ സംഖ്യകളുടെ ഉസാഘ 21 ആണ് (252 = 21 × 12, 105 = 21 × 5). 252നു പകരം അതിൽ നിന്ന് 105 കുറച്ചാൽ കിട്ടുന്ന 147 ഉപയോഗിച്ചാൽ ഉസാഘ 21 തന്നെ ലഭിക്കുന്നു (252 − 105 = 147 = 21 × 7). ഇങ്ങനെ വരുത്തുന്ന മാറ്റം ഓരോ പടിയിലും വലിയ സംഖ്യയുടെ വില കുറയ്ക്കുന്നതിനാൽ സംഖ്യകൾ ചെറുതായി വരുകയും ഒടുവിൽ തുല്യമാവുകയും ചെയ്യും. ആ അവസരത്തിൽ സംഖ്യകളുടെ വില ഉസാഘയ്ക്ക് തുല്യമായിരിക്കും. ഇതിനു ശേഷം അൽഗൊരിതത്തെ പിന്നോട്ടോടിച്ചാൽ ആദ്യത്തെ രണ്ട് സംഖ്യകളെ ഏത് പൂർണ്ണസംഖ്യകൾ കൊണ്ട് ഗുണിച്ച് അവയുടെ തുക കണ്ടാലാണ് ഉസാഘ ലഭിക്കുക എന്ന് കണ്ടുപിടിക്കാം. മുകളിലെ ഉദാഹരണമെടുത്താൽ, 21 = 5 × 105 + (−2) × 252. രണ്ട് സംഖ്യകളുടെ ഉസാഘയെ എല്ലായ്പ്പോഴും അവയുടെ രേഖീയസഞ്ചയമായി എഴുതാൻ സാധിക്കും എന്നത് ബെസു അനന്യത എന്നറിയപ്പെടുന്നു.
അൽഗൊരിതം മേൽ വിവരിച്ച പ്രകാരമാണ് ചെയ്യുന്നതെങ്കിൽ വലിയ സംഖ്യയിൽ നിന്ന് ചെറിയ സംഖ്യ ഒരുപാടു പ്രാവശ്യം കുറയ്ക്കേണ്ടി വന്നേക്കാം. ആദ്യത്തെ സംഖ്യ മറ്റേതിനെക്കാൾ വളരെയധികം വലുതാണെങ്കിലാണ് ഇങ്ങനെ സംഭവിക്കുക. സംഖ്യകൾ കുറയ്ക്കുന്നതിനു പകരം ഹരിച്ചാൽ കിട്ടുന്ന ശിഷ്ടം ഉപയോഗിച്ചാൽ അൽഗൊരിതത്തിന്റെ കാര്യക്ഷമത വളരെയധികം വർദ്ധിക്കുന്നു. സംഖ്യകൾ തുല്യമാകുന്നതിനു പകരം ഒരു സംഖ്യ പൂജ്യമാകുമ്പോഴാണ് ക്രിയകൾ അവസാനിപ്പിക്കേണ്ടതെന്നു മാത്രം. ചെറിയ സംഖ്യയിൽ (ദശാംശ സമ്പ്രദായത്തിൽ) എത്ര അക്കങ്ങളുണ്ടോ അതിന്റെ അഞ്ചു മടങ്ങിൽ കുറവ് ക്രിയകൾ മാത്രമേ കാര്യക്ഷമമായ അൽഗൊരിതത്തിൽ വേണ്ടിവരൂ എന്ന് 1844-ൽ ഗബ്രിയേൽ ലാമേ തെളിയിച്ചു. ഇതാണ് അൽഗൊരിതങ്ങളുടെ ഗണനപരമായ സങ്കീർണ്ണതാസിദ്ധാന്തത്തിന് തുടക്കം കുറിച്ചത്. അൽഗൊരിതത്തിന്റെ കാര്യക്ഷമത വർദ്ധിപ്പിക്കാനുള്ള കൂടുതൽ വഴികൾ ഇരുപതാം നൂറ്റാണ്ടിൽ കണ്ടുപിടിച്ചിട്ടുണ്ട്.
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് സൈദ്ധാന്തികമായും പ്രായോഗികമായും വളരെയധികം പ്രയോജനങ്ങളുണ്ട്. ഭിന്നസംഖ്യകളെ ലഘൂകരിക്കാനും മോഡ്യുലാർ അങ്കഗണിതത്തിൽ ഹരണം നടത്താനും ഇത് ഉപയോഗിക്കാം. ഇന്റർനെറ്റിൽ ആശയവിനിമയം നടത്താനുപയോഗിക്കുന്ന ഗൂഢാലേഖനവിദ്യയുടെ (ക്രിപ്റ്റോഗ്രാഫി) അടിസ്ഥാനം യൂക്ലിഡിന്റെ അൽഗൊരിതമാാണ്, ഈ ഗൂഢാലേഖനവിദ്യകളെ തകർക്കാൻ വേണ്ടി വലിയ സംഖ്യകളുടെ ഘടകങ്ങൾ കണ്ടെത്താനും ഈ അൽഗൊരിതം ഉപയോഗിക്കുന്നു. ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കുക, ചൈനീസ് ശിഷ്ട പ്രമേയമുപയോഗിച്ച് സർവ്വസമതകളുടെ വ്യവസ്ഥകൾക്ക് നിർദ്ധാരണം കാണുക, സതതഭിന്നങ്ങൾ നിർമ്മിക്കുക, അഭിന്നകങ്ങളെ ഭിന്നസംഖ്യകളുപയോഗിച്ച് ഏകദേശനം ചെയ്യുക എന്നതിനെല്ലാം സഹായിക്കുന്നതിനു പുറമെ സംഖ്യാസിദ്ധാന്തത്തിലെ പ്രമേയങ്ങൾ തെളിയിക്കാനും ഈ അൽഗൊരിതം സഹായിക്കുന്നു. ലഗ്രാഞ്ചിന്റെ നാല് വർഗ്ഗ പ്രമേയം, അഭാജ്യ ഘടകക്രിയയുടെ അനന്യത എന്നിവ ഇങ്ങനെ തെളിയിക്കാവുന്നവയാണ്. ആദിമ അൽഗൊരിതം സംഖ്യകൾക്കും നീളങ്ങൾക്കും വേണ്ടി മാത്രമുള്ളതായിരുന്നെങ്കിലും പത്തൊമ്പതാം നൂറ്റാണ്ടിൽ ഗോസിയൻ പൂർണ്ണസംഖ്യകൾ, ഒരു ചരത്തിലുള്ള ബഹുപദങ്ങൾ മുതലായവയ്ക്കും ഉപയോഗിക്കാവുന്ന രീതിയിൽ സാമാന്യവൽക്കരിച്ചു. അമൂർത്തബീജഗണിതത്തിലെ ആധുനിക വിഭാവനമായ യൂക്ലിഡിയൻ മണ്ഡലം ഇതിനെ അടിസ്ഥാനമാക്കിയുള്ളതാണ്.