യൂക്ലിഡിന്റെ അൽഗൊരിതം

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

BA, DC എന്ന നീളങ്ങളുടെ ഉസാഘ കണ്ടുപിടിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കുന്നു. രണ്ട് നീളങ്ങളും ഒരു അടിസ്ഥാന നീളത്തിന്റെ പൂർണ്ണസംഖ്യാഗുണിതമായാണ് എടുക്കുന്നത്. BA യിൽ നിന്ന് DC ഒരു തവണ കുറച്ചാൽ EA ലഭിക്കുന്നു. ഇതിനുശേഷം DCയിൽ നിന്ന് EA രണ്ടു തവണ കുറയ്ക്കാം. ബാക്കി വരുന്ന CFന്റെ മൂന്നിരട്ടിയാണ് EA. ഇതിനു ശേഷം ശിഷ്ടമില്ലാത്തതിനാൽ CF ആണ് ഉസാഘ എന്ന് ലഭിക്കുന്നു. വലതുഭാഗത്ത് നിക്കോമാക്കസിന്റെ ഉദാഹരണമായ 49ന്റെയും 21ന്റെയും ഉസാഘ ഈ വിധത്തിൽ കണ്ടുപിടിക്കുന്നത് കാണിക്കുന്നു (7 ആണ് ഉത്തരം).

രണ്ടു സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കുമ്പോൾ വലിയ സംഖ്യയ്ക്കു പകരം സംഖ്യകളുടെ വ്യത്യാസം ഉപയോഗിച്ചാൽ ഉസാഘയിൽ വ്യത്യാസം വരുന്നില്ല എന്ന തത്ത്വമാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് അടിസ്ഥാനം. ഉദാഹരണമായി, 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) സൂചിപ്പിക്കാനും ഈ പ്രതീകമുപയോഗിക്കുന്നതിനാൽ ആശയക്കുഴപ്പമുണ്ടാകാം.

രണ്ട് സംഖ്യകളുടെ ഉസാഘ 1 ആണെങ്കിൽ അവയെ സഹ-അഭാജ്യം (coprime) എന്ന് പറയുന്നു. എന്നാൽ ഇതുകൊണ്ടുമാത്രം സംഖ്യകൾ അഭാജ്യമാണെന്നു വരുന്നില്ല. ഉദാഹരണമായി 6, 35 എന്നീ രണ്ട് സംഖ്യകളും അഭാജ്യമല്ല: 6 = 2 × 3, 35 = 5 × 7. എങ്കിലും അവ രണ്ടിനെയും ശിഷ്ടം വരാതെ ഹരിക്കാനാകുന്ന ഒരേയൊരു എണ്ണൽ സംഖ്യ 1 ആയതിനാൽ അവ സഹ-അഭാജ്യമാണ്.

24×60 ചതുരത്തെ 12×12 വലിപ്പമുള്ള പത്ത് സമചതുരങ്ങളായി വിഭജിക്കാം. ഇവിടെ 24, 60 എന്നിവയുടെ ഉസാഘയാണ് 12. സാമാന്യവൽക്കരിക്കുകയാണെങ്കിൽ, a×b വലിപ്പമുള്ള ചതുരത്തെ c×c സമചതുരങ്ങളാക്കി മുറിക്കാൻ സാധിക്കുക c രണ്ട് സംഖ്യകളുടെയും ഭാജകമാവുമ്പോഴാണ്.

g = gcd(a, b) എന്ന് കരുതുക. a, b എന്നിവ gയുടെ ഗുണിതങ്ങളായതിനാൽ a = mg എന്നും b = ng എന്നും എഴുതാം. ഉസാഘയായതിനാൽ G > g ആയ ഒരു സംഖ്യയെയും ഇപ്രകാരം എഴുതാൻ സാധിക്കുകയുമില്ല. m, n എന്ന സംഖ്യകൾ സഹ-അഭാജ്യമായിരിക്കണം, അല്ലെങ്കിൽ അവയെ അവയുടെ ഉസാഘ കൊണ്ട് ഗരിച്ച് gയെ ഗുണിക്കുക വഴി gയുടെ വില വർദ്ധിപ്പിക്കാമെന്നു വരും. അതിനാൽ a, b എന്നിവയുടെ രണ്ടിന്റെയും ഭാജകമായ മറ്റേതെങ്കിലും സംഖ്യ c ഉണ്ടെങ്കിൽ അത് gയുടെ കൂടി ഭാജകമായിരിക്കണം എന്ന് കാണാം. അതായത്, a, b എന്നിവയുടെ എല്ലാ ഭാജകങ്ങളുടെയും ഗുണിതമായ ഒരേയൊരു ധനപൂർണ്ണസംഖ്യ എന്ന രീതിയിലും ഉസാഘയെ നിർവചിക്കാം.

ഉസാഘയെ ഈ വിധത്തിൽ ചിത്രീകരിക്കാം. 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) സമചതുരങ്ങളാണുണ്ടാവുക.

രണ്ട് സംഘ്യകളുടെയും അഭാജ്യഘടകങ്ങളുടെ ഗുണനഫലമാണ് അവയുടെ ഉസാഘ. ഇതിൽ ഒരേ അഭാജ്യഘടകം ഒന്നിലേറെ തവണ ഉപയോഗിക്കാം, എന്നാൽ അവയുടെ ഗുണനഫലം രണ്ട് സംഖ്യകളുടെയും ഭാജകമായി തുടരുന്നതുവരെ മാത്രമേ ഇങ്ങനെ ചെയ്യാവൂ. ഉദാഹണമായി, 1836 നെ 2 × 3 × 3 × 7 × 11 എന്നും 3213 നെ 3 × 3 × 3 × 7 × 17 എന്നും അഭാജ്യഘടകങ്ങളായി ഘടകക്രിയ ചെയ്യാം. അവയുടെ ഉസാഘ പൊതുവായ അഭാജ്യഘടകങ്ങളുടെ ഗുണനഫലമായ 63 = 3 × 3 × 7 ആണ്. രണ്ട് സംഖ്യകൾക്ക് പൊതുവായി അഭാജ്യഘടകങ്ങളൊന്നുമില്ലെങ്കിൽ അവയുടെ ഉസാഘ 1 ആയിരിക്കും (ശൂന്യഗണത്തിന്റെ ഗുണനഫലം), ആയതിനാൽ അവ സഹ-അഭാജ്യമായിരിക്കും. ഘടകക്രിയ ചെയ്യാതെ തന്നെ ഉസാഘ കണ്ടുപിടിക്കാമെന്നതാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ ഒരു പ്രധാനമായ മെച്ചം. വലിയ സംഖ്യകളെ ഘടകക്രിയ ചെയ്യുന്നത് ഗണനപരമായ സങ്കീർണ്ണതയേറിയ പ്രശ്നമാണെന്ന് വിശ്വസിക്കപ്പെടുന്നു, വ്യാപകമായി ഉപയോഗിക്കപ്പെടുന്ന ചില ഗൂഢാലേഖനവിദ്യകളുടെ സ്ഥൈര്യത്തിന് അടിസ്ഥാനം തന്നെ ഈ സങ്കീർണ്ണതയാണ്.

വലയസിദ്ധാന്തം പോലുള്ള ഉയർന്ന ഗണിതശാസ്ത്രശാഖകളിൽ ഉപയോഗം വരുന്ന മറ്റൊരു വിധത്തിലും ഉസാഘയെ നിർവചിക്കാം: രണ്ട് സംഖ്യകളുടെ പൂർണ്ണസംഖ്യകൾകൊണ്ടുള്ള രേഖീയസഞ്ചയങ്ങളിൽ (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 അങ്ങനെ വർദ്ധിച്ചുവരുന്നു.

ഓരോ ക്രിയയുടെയും ഇൻപുട്ട് r_k−1, r_k−2 എന്ന രണ്ട് ശിഷ്ടങ്ങളാണ്, ഇവ രണ്ടും ധനപൂർണ്ണസംഖ്യകളോ പൂജ്യമോ ആയിരിക്കും. അൽഗൊരിതത്തിന്റെ ഓരോ പടിയിലും ശിഷ്ടങ്ങൾ കുറഞ്ഞുവരുന്നതിനാൾ r_k−1 അതിന്റെ മുൻഗാമിയായ r_k−2 നെക്കാൾ ചെറുതായിരിക്കും. താഴെ കൊടുത്തിരിക്കുന്ന സമവാക്യത്തിന് നിർദ്ധാരണമായി q_k എന്ന ഹരണഫലവും r_k എന്ന ശിഷ്ടവും കണ്ടുപിടിക്കുകയാണ് kആമത്തെ പടിയുടെ ലക്ഷ്യം.

$r_{k-2}=q_{k}r_{k-1}+r_{k}$

ഈ നിർദ്ധാരണത്തിൽ r_k < r_k−1 ആയിരിക്കുകയും വേണം. മറ്റൊരു രീതിയിൽ പറഞ്ഞാൽ, ഫലം r_k−1ൽ കുറവാകുന്നതു വരെ r_k−2ൽ നിന്ന് r_k−1 കുറയ്ക്കുന്നു. ഇതിന്റെ അവസാനം കിട്ടുന്ന സംഖ്യയാണ് r_k. അൽഗൊരിതത്തിന്റെ തുടക്കത്തിൽ (k = 0) ശിഷ്ടങ്ങളായ r₋₂, r₋₁ എന്നിവ ഉസാഘ കാണേണ്ട സംഖ്യകളായ a, b എന്നിവയായിരിക്കും. അടുത്ത പടിയിൽ (k = 1) bയും മുൻപത്തെ പടിയിലെ ഫലമായ r₀ യുമാണ് ശിഷ്ടങ്ങളായി ഉപയോഗിക്കുക. ഇങ്ങനെ നമുക്ക് അൽഗൊരിതത്തെ സമവാക്യങ്ങളുടെ ഒരു ശ്രേണിയായി എഴുതാം

${\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\r_{0}&=q_{2}r_{1}+r_{2}\\r_{1}&=q_{3}r_{2}+r_{3}\\&\,\,\,\vdots \end{aligned}}$

a തുടക്കത്തിൽ b യെക്കാൾ ചെറുതാണെങ്കിൽ ആദ്യത്തെ പടി അവയെ പരസ്പരം വച്ചുമാറ്റുക മാത്രമേ ചെയ്യൂ. ഈ ക്രിയയുടെ ഫലങ്ങളായ ഹരണഫലം q₀ പൂജ്യവും ശിഷ്ടം r₀ aയും ആയതിനാലാണിത്. അതിനാൽ k ≥ 0 ആകുമ്പോഴൊക്കെ ശിഷ്ടം r_k അതിന്റെ മുൻഗാമിയായ r_k−1 നെക്കാൾ ചെറുതാണെന്നു വരുന്നു. ശിഷ്ടങ്ങൾ ഓരോ പടിയിലും ചെറുതാവും, എന്നാൽ ഒരിക്കലും പൂജ്യത്തിൽ കുറവാവുകയുമില്ല എന്നതിനാൽ ഒടുവിൽ ശിഷ്ടം r_N പൂജ്യമാവുന്ന അവസ്ഥയുണ്ടാവണം. അതോടെ അൽഗൊരിതം അവസാനിപ്പിക്കുന്നു. പൂജ്യത്തിനു തൊട്ടുമുമ്പ് ലഭിച്ച ശിഷ്ടമായ r_N−1 ആണ് a, b എന്ന സംഖ്യകളുടെ ഉസാഘ. തുടക്കത്തിലെ ശിഷ്ടമായ r₀നും r_Nനും ഇടയിലെ പൂർണ്ണസംഖ്യകളുടെ എണ്ണം പരിമിതമായതിനാൽ N ഒരിക്കലും അനന്തമാവുകയില്ല.

തെളിവ്

യൂക്ലിഡിന്റെ അൽഗൊരിതം ശരിയായി ഉസാഘ കണ്ടുപിടിക്കുന്നു എന്ന് തെളിയിക്കുന്നത് രണ്ടു പടിയായാണ്. പൂജ്യത്തിനു മുമ്പായി കിട്ടുന്ന ശിഷ്ടമായ r_N−1 ഉസാഘ കാണേണ്ട a, b എന്ന സംഖ്യകളുടെ ഭാജകമാണ് എന്ന് തെളിയിക്കുകയാണ് ആദ്യത്തെ പടി. പൊതു ഭാജകമായതിനാൽ അത് ഉസാഘയായ gയെക്കാൾ വലുതായിരിക്കില്ല എന്ന് വരുന്നു. രണ്ടാമത്തെ പടിയിൽ a, b എന്ന സംഖ്യകൾക്കും പൊതുവായുള്ള ഉസാഘയുൾപ്പെടെയുള്ള ഏത് ഭാജകവും r_N−1ന്റെയും ഭാജകമാണെന്ന് തെളിയിക്കുന്നു. അതിനാൽ ഉസാഘ ഈ സംഖ്യയെക്കാൾ ചെറുതോ അതിന് തുല്യമോ ആയിരിക്കണം. ഈ രണ്ട് പ്രസ്താവനകളും പരസ്പരവിരുദ്ധമാവാതിരിക്കാനുള്ള ഒരേയൊരു വഴി r_N−1 = g ആവുകയാണ്.

ആദ്യ പടിയായി a, b എന്നിവയുടെ ഭാജകമാണ് r_N−1 എന്ന് ഇപ്രകാരം തെളിയിക്കാം. ആദ്യമായി, r_N−1 അതിന്റെ മുൻഗാമിയായ r_N−2ന്റെ ഭാജകമാണെന്ന് നിരീക്ഷിക്കുക

r_N−2 = q_N r_N−1

അവസാനത്തെ ശിഷ്ടമായ r_N പൂജ്യമായതിനാലാണിത്. ഇതിനു മുമ്പത്തെ പടിയിലെ സമവാക്യമെടുത്താൽ

r_N−3 = q_N−1 r_N−2 + r_N−1

വലതുഭാഗത്തെ രണ്ട് പദങ്ങളും r_N−1 ന്റെ ഗുണിതങ്ങളായതിനാൽ r_N−1 അതിന്റെ അടുത്ത മുൻഗാമിയായ r_N−3ന്റെയും ഭാജകമാണെന്നു കാണാം. ഈ വിധത്തിൽ തുടരുകയാണെങ്കിൽ r_N−1 അതിനു മുമ്പുള്ള എല്ലാ ശിഷ്ടങ്ങളുടെയും ഭാജകമാണെന്നു വരുന്നു, ഈ ശിഷ്ടങ്ങളിൽ a, b എന്നിവയും പെടുന്നു എന്നത് പ്രധാനമാണ്. r_N−1നു മുമ്പ് ലഭിച്ച ശിഷ്ടങ്ങളായ r_N−2, r_N−3 മുതലായവയൊന്നും തന്നെ ശിഷ്ടം വരുന്നതിനാൽ a യുടെയോ b യുടെയോ ഭാജകങ്ങളാവില്ല. r_N−1 എന്നത് a, b എന്നിവയുടെ പൊതു ഭാജകമായതിനാൽ r_N−1 ≤ g.

a, b എന്നീ സംഖ്യകളുടെ ഭാജകമായ ഏത് cയും അൽഗൊരിതത്തിലെ എല്ലാ ശിഷ്ടങ്ങളുടെയും ഭാജകമായിരിക്കും എന്ന് തെളിയിക്കുകയാണ് അടുത്ത പടി. നിർവചനമനുസരിച്ച് aയെയും bയെയും cയുടെ ഗുണിതങ്ങളായി എഴുതാം: a = mc, b = nc. ഇവിടെ m, n എന്നിവ എണ്ണൽ സംഖ്യകളാണ്. അൽഗൊരിതത്തിന്റെ ആദ്യത്തെ പടിയെടുത്താൽ

r₀ = a − q₀b = mc − q₀nc = (m − q₀n)c

അതായത്, c ആദ്യത്തെ പടിയിലെ ശിഷ്ടമായ r₀യുടെ ഭാജകമാണ്. ഇതേ വാദമുപയോഗിച്ചാൽ c ഇതെത്തുടർന്നു വരുന്ന പടികളിലെ ശിഷ്ടങ്ങളായ r₁, r₂ മുതലായവയുടെയും ഭാജകമാണെന്ന് കാണാം. അതായത്, r_N−1ന്റെ ഭാജകമാണ് ഉസാഘയായ g എന്നും, അതിനാൽത്തന്നെ g ≤ r_N−1 എന്നും വരുന്നു. ഇതിന്റെ വിപരീതം (r_N−1 ≤ g) നേരത്തെ തെളിയിച്ചിട്ടുള്ളതിനാൽ g = r_N−1 എന്ന് ലഭിക്കുന്നു. അതായത്, ഇതിനു മുമ്പുള്ള എല്ലാ ജോടികളുടെയും ഉസാഘ g തന്നെയാണ്:

g = gcd(a, b) = gcd(b, r₀) = gcd(r₀, r₁) = … = gcd(r_N−2, r_N−1) = r_N−1.

ഉദാഹരണം

വ്യവകലനം ഉപയോഗിക്കുന്ന യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ ആനിമേഷൻ. തുടക്കത്തിൽ ചതുരത്തിന്റെ നീളം a = 1071 ഉം വീതി b = 462 ഉം ആണ്. 462×462 സമചതുരങ്ങൾ കൊണ്ട് ചതുരം നിറയ്ക്കാൻ ശ്രമിച്ചാൽ 462×147 വിസ്തീർണ്ണമുള്ള ചതുരം ബാക്കിയാകും. ഈ ചതുരത്തെ അടുത്ത പടിയിൽ 147×147 സമചതുരങ്ങൾ കൊണ്ട് നിറയ്ക്കാൻ ശ്രമിക്കാം, 21×147 വിസ്തീർണ്ണമുള്ള ചതുരങ്ങളാണ് ബാക്കിയാവുക. തുടർന്ന് ഇതിനെ 21×21 സമചതുരങ്ങൾ കൊണ്ട് നിറച്ചാൽ ശിഷ്ടമുണ്ടാവില്ലെന്ന് കാണാം. ഏറ്റവും ചെറിയ സമചതുരത്തിന്റെ വശമായ 21 ആണ് തുടക്കത്തിലെ സംഖ്യകളായ 1071, 462 എന്നിവയുടെ ഉസാഘ.

യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് a = 1071, b = 462 എന്നിവയുടെ ഉസാഘ കാണേണ്ടതുണ്ടെന്ന് കരുതുക. ശിഷ്ടം 462-ൽ കുറവാകുന്നതുവരെ 462-ന്റെ ഗുണിതങ്ങൾ 1071-ൽ നിന്ന് കുറയ്ക്കുകയാണ് ആദ്യ പടി. രണ്ടുതവണയേ (q₀ = 2) ഇങ്ങനെ കുറയ്ക്കാൻ പറ്റുകയുള്ളൂ, അതോടെ 147 ശിഷ്ടമായി ലഭിക്കും:

1071 = 2 × 462 + 147.

ഇതിനു ശേഷം ശിഷ്ടമായ 147-ന്റെ ഗുണിതങ്ങളെ 462-ൽ നിന്ന് ആവുന്നത്ര തവണ കുറയ്ക്കും. മൂന്നു തവണ കുറച്ചാൽ (q₁ = 3) ശിഷ്ടം 147ലും കുറവായി 21 ആവും:

462 = 3 × 147 + 21.

അടുത്ത പടിയിൽ 21-ന്റെ ഗുണിതങ്ങളെ 147ൽ നിന്ന് കുറയ്ക്കുന്നു. ഏഴ് തവണ (q₂ = 7) കുറച്ചാൽ ഒന്നും ബാക്കി വരാതെ സംഖ്യ പൂജ്യമാവും:

147 = 7 × 21 + 0.

അവസാനത്തെ ശിഷ്ടം പൂജ്യമായതിനാൽ 1071,462 എന്ന സംഖ്യകളുടെ ഉസാഘയായി 21 (മുമ്പത്തെ പടിയിലെ ശിഷ്ടം) കണ്ടുപിടിച്ച് അൽഗൊരിതം അവസാനിക്കുന്നു. 1071 = 3^2 × 7 × 17, 462 = 2 × 3 × 7 × 11 എന്നിങ്ങനെ സംഖ്യകളുടെ ഘടകക്രിയ ചെയ്താൽ ഈ ഉത്തരം ശരിയാണെന്നു കാണാം. അൽഗഗൊരിതത്തിലെ പടികൾ ഇവിടെ പട്ടികപ്പെടുത്തിയിരിക്കുന്നു

പടി k	സമവാക്യം	ഹരണഫലവും ശിഷ്ടവും
0	1071 = q0 462 + r0	q0 = 2, r0 = 147
1	462 = q1 147 + r1	q1 = 3, r1 = 21
2	147 = q2 21 + r2	q2 = 7, r2 = 0; അൽഗൊരിതം അവസാനിച്ചു

ചിത്രീകരണം

മേലെ ഉസാഘയെ ജ്യാമിതീയമായ വ്യാഖ്യാനിച്ച രീതിയിൽ അൽഗൊരിതത്തിലെ ക്രിയകളെയും ചിത്രീകരിക്കാം. a×b വിസ്തീർണ്ണമുള്ള (ഇവിടെ a, bയെക്കാൾ വലുതാണ്) ഒരു ചതുരത്തെ സമചതുരങ്ങൾ കൊണ്ട് നിറയ്ക്കണമെന്ന് കരുതുക. ആദ്യം നമുക്ക് ചതുരത്തെ b×b സമചതുരങ്ങൾ കൊണ്ട് മൂടാൻ ശ്രമിക്കാം. പക്ഷെ ആവുന്നത്ര സമചതുരങ്ങൾ ചേർത്തുകഴിഞ്ഞാൽ ഒരു r₀×b ചതുരം ബാക്കിയാവും. ഇതിനെ പിന്നീട് r₀×r₀ സമചതുരങ്ങൾ കൊണ്ട് മൂടാൻ ശ്രമിക്കാം. ഇതിന്റെ അവസാനം ഒരു r₁×r₀ ചതുരം ബാക്കിയാവുകയും അതിനെ അടുത്ത പടിയിൽ r₁×r₁ സമചതുരങ്ങൾ കൊണ്ട് മൂടാൻ ശ്രമിക്കുകയും ചെയ്യാം. ഒരു പടിയിൽ ചതുരത്തെ സമചതുരങ്ങൾ കൊണ്ട് പൂർണ്ണമായി മൂടാൻ സാധിക്കുകമ്പോഴാണ് ഈ ക്രിയാശ്രേണി അവസാനിക്കുന്നത്. ഒടുവിൽ ചേർത്ത ഏറ്റവും ചെറിയ സമചതുരത്തിന്റെ വശത്തിന്റെ നീളമാണ് ആദ്യത്തെ ചതുരത്തിന്റെ വശങ്ങളുടെ ഉസാഘ. ഉദാഹരണമായി, ആനിമേഷനിലെ തുടക്കത്തിലെ പച്ച ചതുരത്തിന്റെ വശങ്ങളുടെ നീളം 1071, 462 ആണ്, ഇവയുടെ ഉസാഘയായ 21 ആണ് ഏറ്റവും ചെറിയ ചുവന്ന സമചതുരമത്തിന്റെ വശം.

യൂക്ലിഡിയൻ ഹരണം

kആമത്തെ പടിയിൽ r_k−1, r_k−2 എന്നീ സംഖ്യകളുപയോഗിച്ച് ഹരണഫലമായ q_kയും ശിഷ്ടമായ r_kയും കണ്ടുപിടിക്കുകയാണ് ചെയ്യേണ്ടത്.

r_k−2 = q_k r_k−1 + r_k

ഇവിടെ r_kയുടെ കേവലവില r_k−1ന്റേതിനെക്കാൾ കുറവായിരിക്കണം. യൂക്ലിഡിയൻ ഹരണത്തിന് അടിസ്ഥാനമായ പ്രമേയം ഈ നിഷ്കർഷയോടെ ഹരണഫലവും ശിഷ്ടവും കണ്ടുപിടിക്കുന്നത് സാധ്യമാണെന്നും ഫലം അനന്യമാണെന്നും പറയുന്നു.

യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മൂലരൂപത്തിൽ ആവർത്തിച്ച് വ്യവകലനം ചെയ്തുകൊണ്ടാണ് ഹരണഫലവും ശിഷ്ടവും കണ്ടിരുന്നത്. അതായത്, ഫലം r_k−1ൽ കുറവാവുന്നതു വരെ r_k−2ൽ നിന്ന് r_k−1 ആവർത്തിച്ച് കുറയ്ക്കുന്നു. ഇതിനുശേഷം r_k, r_k−1 എന്നിവയെ പരസ്പരം വച്ചുമാറിയ ശേഷം പ്രക്രിയ തുടരുന്നു. ഇങ്ങനെ ആവർത്തിച്ച് വ്യവകലനം ചെയ്യുന്നതിനു പകരം ഒറ്റ ക്രിയകൊണ്ടുതന്നെ ഹരണഫലവും ശിഷ്ടവും കാണാൻ യൂക്ലിഡിയൻ ഹരണം വഴി സാധിക്കുന്നു. കാര്യക്ഷമത വർദ്ധിപ്പിക്കുന്നതിനു പുറമെ, ഹരണഫലങ്ങൾ ആവശ്യമില്ലാത്തതിനാൽ ശിഷ്ടം മാത്രം നൽകുന്ന മോഡ്യുലോ സംക്രിയ ഉപയോഗിക്കാനും സാധിക്കുന്നു. അതിനാൽ യൂക്ലിഡിയൻ ഹരണം ഉപയോഗിച്ചുള്ള അൽഗൊരിതത്തിന്റെ ക്രിയകളെ ഇപ്രകാരം എഴുതാം

r_k = r_k−2 mod r_k−1.

പ്രയോഗത്തിൽ

അൽഗൊരിതത്തിന്റെ പ്രയോഗം സ്യൂഡോകോഡ് ഉപയോഗിച്ച് വ്യക്തമാക്കാം. ഉദാഹരണത്തിന് ഹരണം ഉപയോഗിക്കുന്ന അൽഗൊരിതം ഇപ്രകാരം എഴുതാം

function gcd(a, b)
    while b ≠ 0
       t := b; 
       b := a mod b; 
       a := t; 
    return a;

k ആമത്തെ പടിയുടെ ആരംഭത്തിൽ b മുമ്പത്തെ ശിഷ്ടമായ r_k−1 ഉം a മുൻഗാമിയായ r_k−2 ഉം ആയിരിക്കും. b := a mod b എന്ന ക്രിയ മേൽ വിവരിച്ച r_k ≡ r_k−2 mod r_k−1 എന്ന ആവർത്തനബന്ധത്തിന്റെ പ്രയോഗമാണ്. താൽക്കാലികമായ ചരമായ t ശിഷ്ടങ്ങളെ പരസ്പരം വച്ചുമാറാനാണ് ഉപയോഗിക്കുന്നത്. പടിയുടെ അവസാനം ശിഷ്ടമായ r_k യുടെ വില b യിലും, മുമ്പത്തെ പടിയിലെ ശിഷ്ടമായ r_k−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;

മുമ്പത്തെ ശിഷ്ടങ്ങളായ r_k−1, r_k−2 എന്നിവയുടെ വിലകൾ a, b എന്ന ചരങ്ങൾ മാറിമാറി സ്വീകരിക്കുന്നു. ഒരു പടിയുടെ തുടക്കത്തിൽ a യുടെ വില b യെക്കാൾ വലുതാണെന്ന് കരുതുക; എങ്കിൽ r_k−2 > r_k−1 ആയതിനാൽ a എന്ന ചരത്തിലുള്ളത് r_k−2 ന്റെ വിലയാണെന്ന് വരുന്നു. a യുടെ വില b യെക്കാൾ ചെറുതാവുന്നത് വരെ b യെ a യിൽ നിന്ന് കുറയ്ക്കുന്നു. പുതിയ ശിഷ്ടമായ r_k യുടെ വില അപ്പോൾ a യിലെത്തുന്നു. തുടർന്ന് b യുടെ വില a യിൽ കുറവാവുന്നത് വരെ a കുറച്ച് അടുത്ത ശിഷ്ടമായ r_k+1 കണ്ടുപിടിക്കുന്നു, ഇങ്ങനെയാണ് അൽഗൊരിതം പുരോഗമിക്കുന്നത്.

ഓരോ പടിയിലെയും സംഖ്യാജോടിയുടെ ഉസാഘ തുല്യമാണ് എന്നതും അൽഗൊരിതം അവസാനിപ്പിക്കാൻ gcd(r_N−1, 0) = r_N−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 കൂട്ടാതെ ലഭിക്കുന്ന ധനശിഷ്ടത്തെക്കാൾ കുറവാണെങ്കിൽ പരിഷ്കരിച്ച ഹരണഫലവും ശിഷ്ടവും ഉപയോഗിച്ചുകൊണ്ടാണ് ഈ അൽഗൊരിതം പുരോഗമിക്കുന്നത്. ഇതുവരെ

r_k−2 = q_k r_k−1 + r_k

എന്ന സമവാക്യത്തിൽ |r_k−1| > r_k > 0 ആണെന്നായിരുന്നു നാം കല്പിച്ചിരുന്നത്. എന്നാൽ ഇതിൽ നിന്ന് വ്യത്യസ്തമായി ഒരു ഋണശിഷ്ടം e_k ഇപ്രകാരം കണ്ടുപിടിക്കാം:

r_k−1 > 0 ആണെങ്കിൽ

r_k−2 = (q_k + 1) r_k−1 + e_k

അഥവാ r_k−1 < 0 ആണെങ്കിൽ

r_k−2 = (q_k − 1) r_k−1 + e_k

|e_k| < |r_k| ആവുന്ന അവസരത്തിൽ r_k യ്ക്കു പകരം e_k. ഉപയോഗിക്കുകയാണെങ്കിൽ ഓരോ പടിയിലും താഴെ കൊടുത്തിരിക്കുന്ന നിഷ്കർഷ അനുസരിക്കുന്ന അൽഗൊരിതം ലഭിക്കുന്നു:

|r_k| ≤ |r_k−1| / 2

അൽഗൊരിതത്തിന്റെ എല്ലാ ഭാഷ്യങ്ങളിലും വച്ച് ഇതിനാണ് ഏറ്റവും കുറവ് പടികൾ ആവശ്യമായി വരിക എന്ന് ലിയോപോൾഡ് ക്രോണെക്കർ തെളിയിച്ചിട്ടുണ്ട്. സാമാന്യവൽക്കരിക്കുകയാണെങ്കിൽ, a, b എന്ന സംഖ്യകളുടെ ഉസാഘ കാണാനാവശ്യമായ പടികളുടെ എണ്ണം ഏറ്റവും കുറവാകുന്നത് $\left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,$ ആവുന്ന തരത്തിൽ q_k തിരഞ്ഞെടുക്കുമ്പോഴാണ് (ഇവിടെ $\varphi$ സുവർണ്ണാനുപാതമാണ്).

ചരിത്രം

യൂക്ലിഡിനും (ചിത്രത്തിൽ) നൂറ്റാണ്ടുകൾ മുമ്പു തന്നെ യൂക്ലിഡിയൻ അൽഗൊരിതം കണ്ടുപിടിക്കപ്പെട്ടിട്ടുണ്ടാവാം.

സാധാരണയായി ഉപയോഗിക്കപ്പെടുന്ന അൽഗൊരിതങ്ങളിൽ ഏറ്റവും പഴക്കമേറിയവയിലാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സ്ഥാനം. ക്രിസ്തുവിനും മുന്നൂറുവർഷത്തോളം മുമ്പ് യൂക്ലിഡ് എഴുതിയ എലിമെന്റ്സ് എന്ന ഗ്രന്ഥത്തിൽ ഈ അൽഗൊരിതം പ്രത്യക്ഷപ്പെടുന്നു (ഏഴാം പുസ്തകം വാദം 1-2, പത്താം പുസ്തകം വാദം 2-3). ഏഴാം പുസ്തകത്തിൽ പൂർണ്ണസംഖ്യകൾക്കുവേണ്ടിയും പത്താം പുസ്തകത്തിൽ രേഖാഖണ്ഡങ്ങളുടെ നീളങ്ങൾക്കു വേണ്ടിയുമാണ് അൽഗൊരിതം ആസൂത്രണം ചെയ്തിരിക്കുന്നത്. ആധുനിക ഗണിതശാസ്ത്രത്തിൽ വാസ്തവികസംഖ്യകളുടെ ഉസാഘ കാണുന്നതിന് സമാനമാണ് ഇങ്ങനെ നീളങ്ങളുടെ ഉസാഘ കണ്ടുപിടിക്കുന്നത്. എന്നാൽ യൂക്ലിഡിന്റെ കാലത്ത് വാസ്തവികസംഖ്യകൾ എന്ന ആശയം ഉരുത്തിരിഞ്ഞിട്ടില്ലായിരുന്നു. a, b എന്നീ നീളങ്ങളുടെ ഉസാഘ g അവയെ രണ്ടിനെയും പൂൂർണ്ണസംഖ്യ എണ്ണം ഭാഗങ്ങളായി അളക്കാൻ സാധിക്കുന്ന ഏറ്റവും വലിയ നീളമാണ്. അതായത്, a, b എന്നിവ രണ്ടും gയുടെ പൂർണ്ണസംഖ്യാഗുണിതങ്ങളായി വരുന്ന തരത്തിലുള്ള ഏറ്റവും വലിയ നീളമാണ് g.

ഈ അൽഗൊരിതം കണ്ടുപിടിച്ചത് യൂക്ലിഡ് ആയിരിക്കാൻ സാധ്യതയില്ല, മുൻകാലത്തെ ഗണിതശാസ്ത്രജ്ഞരുടെ കണ്ടെത്തലുകൾ എലിമെന്റ്സിൽ സമാഹരിച്ച കൂട്ടത്തിലുള്ളതാവാം. പൈതഗോറിയൻ സ്കൂളിലെ ഗണിതശാസ്ത്രജ്ഞർ സംഖ്യാസിദ്ധാന്തത്തെക്കുറിച്ചെഴുതിയ ഒരു ഗ്രന്ഥത്തിൽ നിന്നാണ് എലിമെന്റ്സിലെ ഏഴാം പുസ്തകം ഉരുത്തിരിഞ്ഞതെന്ന് ഗണിതശാസ്ത്രജ്ഞനും ചരിത്രകാരനുമായ ബി. എൽ. ഫാൻ ഡെർ വേർഡൻ നിർദ്ദേശിക്കുന്നു. ക്രിസ്തുവിന് 375 വർഷം മുമ്പ് നിഡസിലെ യുഡോക്സസിന് ഈ അൽഗൊരിതത്തെക്കുറിച്ച് അറിയുമായിരുന്നിരിക്കാം. യൂക്ലിഡും അരിസ്റ്റോട്ടിലും ἀνθυφαίρεσις (ആന്റിഫൈറസിസ് അഥവാ വ്യുൽക്രമ വ്യവകലനം) എന്ന സാങ്കേതികപദം ഉപയോഗിച്ചിരുന്നതിനാൽ യൂഡോക്സസിനും മുമ്പുതന്നെ അൽഗൊരിതം കണ്ടുപിടിക്കപ്പെട്ടിരിക്കാനും സാധ്യതയുണ്ട്.

നൂറ്റാണ്ടുകൾക്കു ശേഷം ഇന്ത്യയിലും ചൈനയിലും യൂക്ലിഡിന്റെ അൽഗൊരിതം വീണ്ടും സ്വതന്ത്രമായി കണ്ടുപിടിക്കപ്പെട്ടു. ജ്യോതിഃശാസ്ത്രത്തിൽ കണക്കുകൂട്ടലുകൾ നടത്താനും കൃത്യതയാർന്ന കലണ്ടറുകൾ ഉണ്ടാക്കാനും വേണ്ടി ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കുന്നതിനായായിരുന്നു ഇത്. ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കുന്നതിൽ വളരെ ഫലപ്രദമായതിനാൽ അഞ്ചാം നൂറ്റാണ്ടിലെ ഗണിതശാസ്ത്രജ്ഞനും ജ്യോതിഃശാസ്ത്രജ്ഞനുമായ ആര്യഭടൻ അൽഗൊരിതത്തെ വിശേഷിപ്പിച്ചത് തവിടുപൊടിയാക്കുന്നത് (pulverizer) എന്നായിരുന്നു. ചൈനീസ് ശിഷ്ടപ്രമേയത്തിന്റെ ഒരു വിശിഷ്ടഭാഷ്യം (special case) സുൻസി സുവാൻജിങ് (Sunzi Suanjing) എന്ന ചൈനീസ് ഗ്രന്ഥത്തിൽ മുമ്പേ വിവരിച്ചിരുന്നുവെങ്കിലും 1247-ൽ ക്വിൻ ജിയുഷാവോ ആണ് ഷുഷു ജിയുസാങ് (Shushu Jiuzhang 數書九章) എന്ന ഗ്രന്ഥത്തിൽ പ്രമേയത്തിന്റെ സാമാന്യഭാഷ്യത്തിന്റെ നിർദ്ധാരണം പ്രസിദ്ധീകരിച്ചത്. യൂറോപ്പിൽ യൂക്ലിഡിന്റെ അൽഗൊരിതം ആദ്യമായി വിവരിക്കപ്പെടുന്നത് ക്ലോദ് ഗസ്പാർദ് ബാഷെ ദെ മെസിറിയാക് എഴുതിയ പ്രോബ്ലെം പ്ലെയ്സാന്ത് എ ദെലെക്താബ്ല് (Problèmes plaisants et délectables, ഹൃദ്യവും ആസ്വാദ്യവുമായ പ്രശ്നങ്ങൾ) എന്ന ഗ്രന്ഥത്തിന്റെ രണ്ടാം പതിപ്പിലാണ്. ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കാനും സതതഭിന്നങ്ങൾ കണ്ടുപിടിക്കാനുമാണ് യൂറോപ്പിൽ അൽഗൊരിതം ഉപയോഗിച്ചിരുന്നത്. അൽഗൊരിതത്തിന്റെ വികസിതരൂപം (വികസിത യൂക്ലിഡിയൻ അൽഗൊരിതം) പ്രസിദ്ധീകരിച്ചത് ഇംഗ്ലീഷ് ഗണിതശാസ്ത്രജ്ഞനായ നിക്കോളാസ് സോണ്ടേർസണായിരുന്നു. സതതഭിന്നങ്ങൾ കാര്യക്ഷമമായി കണക്കുകൂട്ടാൻ വേണ്ടി റോജർ കോട്സ് ആണ് ഈ രീതി കണ്ടുപിടിച്ചത് എന്നാണ് സോണ്ടേഴ്സൺ പറഞ്ഞത്.

പത്തൊമ്പതാം നൂറ്റാണ്ടിൽ ഗോസ്സിയൻ പൂർണ്ണസംഖ്യകൾ, ഐസൻസ്റ്റൈൻ പൂർണ്ണസംഖ്യകൾ മുതലായ പുതിയ സംഖ്യാവ്യവസ്ഥകൾ വികസിപ്പിച്ചെടുത്തത് യൂക്ലിഡിന്റെ അൽഗൊരിതം അടിസ്ഥാനമാക്കിയാണ്. 1815-ൽ ഗോസ്സിയൻ പൂർണ്ണസംഖ്യകളെ അനന്യമായി ഘടകക്രിയ ചെയ്യാമെന്ന് തെളിയിക്കാൻ കാൾ ഫ്രെഡറിക് ഗോസ്സ് ഈ അൽഗൊരിതം ഉപയോഗിച്ചു (1832-ലാണ് ഈ ഫലം പ്രസിദ്ധീകരിച്ചത്). 1801-ൽ പ്രസിദ്ധീകരിച്ച തന്റെ ഡിസ്ക്വിസിഷൻസ് അരിത്മെറ്റികേ (Disquisitiones Arithmeticae) എന്ന ഗ്രന്ഥത്തിൽ ഗോസ്സ് അൽഗൊരിതത്തെ മുമ്പേ പരാമർശിച്ചിരുന്നുവെങ്കിലും അത് സതതഭിന്നങ്ങൾ കണ്ടുപിടിക്കാനുള്ള ഒരു രീതി എന്ന നിലയിലായിരുന്നു. പീറ്റർ ഗുസ്താവ് ലെജോൻ ദിരിക്ലേ ആണ് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെ സംഖ്യാസിദ്ധാന്തത്തിന്റെ അടിസ്ഥാനശിലയായി വിവരിച്ചത്. പൂർണ്ണസംഖ്യകൾക്കു മാത്രമല്ല, യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാൻ സാധിക്കുന്ന മറ്റേത് സംഖ്യാവ്യവസ്ഥയും അനന്യമായ ഘടകക്രിയ ഉൾപ്പെടെയുള്ള സംഖ്യസിദ്ധാന്തപ്രമേയങ്ങൾ അനുസരിക്കും എന്ന് ദിരിക്ലേ നിരീക്ഷിച്ചു. സംഖ്യാസിദ്ധാന്തത്തെക്കുറിച്ചുള്ള ദിരിക്ലേയുടെ പ്രഭാഷണങ്ങൾ സംശോധനം ചെയ്യുകയും വ്യാപിപ്പിക്കുകയും ചെയ്ത റിച്ചാർഡ് ഡെഡിക്കിന്റ് ബീജീയ പൂർണ്ണസംഖ്യകൾ എന്ന പൂർണ്ണസംഖ്യകളുടെ പുതിയ സാമാന്യവൽക്കരണത്തെക്കുറിച്ച് പഠിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിച്ചു. ഗോസ്സിയൻ പൂർണ്ണസംഖ്യകളുടെ അനന്യമായ ഘടകക്രിയ ഉപയോഗിച്ച് ഡെഡിക്കിന്റ് ഫെർമയുടെ രണ്ട് വർഗ്ഗ പ്രമേയം ആദ്യമായി തെളിയിച്ചു. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സാമാന്യവൽക്കരണങ്ങൾ അനുസരിക്കുന്ന സംഖ്യാവ്യവസ്ഥകളായ യൂക്ലിഡിയൻ മണ്ഡലങ്ങളെ നിർവചിച്ചതും ഡെഡിക്കിന്റ് തന്നെ. പത്തൊമ്പതാം നൂറ്റാണ്ടിന്റെ അവസാനത്തോടെ ഡെഡിക്കിന്റിന്റെ ഗുണജങ്ങളുടെ സാമാന്യസിദ്ധാന്തം യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെക്കാൾ പ്രചാരം നേടി.

"ഇന്നും അതിജീവിക്കുന്ന ഏറ്റവും പഴക്കമേറിയതും നിസ്സാരമല്ലാത്തതുമായ അൽഗൊരിതമായതിനാൽ [യൂക്ലിഡിന്റെ അൽഗൊരിതം] എല്ലാ അൽഗൊരിതങ്ങളുടെയും പിതാമഹനാണ് ([Euclid's algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day)."

ഡൊണാൾഡ് കനൂത്ത്, ദി ആർട്ട് ഓഫ് കമ്പ്യൂട്ടർ പ്രോഗ്രാമിംഗ്, വാള്യം 2: സെമിന്യൂമെറിക്കൽ അൽഗൊരിതംസ്, രണ്ടാം പതിപ്പ് (1981), പേജ് 318.

പത്തൊമ്പതാം നൂറ്റാണ്ടിൽ യൂക്ലിഡിന്റെ അൽഗൊരിതം വേറെയും ആവശ്യങ്ങൾക്ക് ഉപയോഗിക്കാൻ തുടങ്ങി. ഒരു ബഹുപദത്തിന് ഏതെങ്കിലും ഇടവേളയിൽ എത്ര വാസ്തവിക നിർദ്ധാരണങ്ങളുണ്ടെന്ന് കണ്ടുപിടിക്കാനുപയോഗിക്കുന്ന സ്റ്റുർമ് ശൃംഖലകൾ സൃഷ്ടിക്കുന്നതിന് ഈ അൽഗൊരിതം സഹായകമാണെന്ന് 1829-ൽ ചാൾസ് സ്റ്റുർമ് തെളിയിച്ചു. ഒരു വാസ്തവികസംഖ്യാഗണത്തിലെ സംഖ്യകളെ ഏത് പൂർണ്ണസംഖ്യാ ഗുണോത്തരങ്ങൾ കൊണ്ട് ഗുണിച്ച് തുക കണ്ടാലാണ് (അത് സാധ്യമെങ്കിൽ) പൂജ്യം ഫലമായി ലഭിക്കുക എന്ന് കണ്ടുപിടിക്കാനുപയോഗിക്കുന്ന Integer relation അൽഗൊരിതങ്ങളിൽ ആദ്യത്തേതാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതം. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ പിൻഗാമികളായി ഈ ആവശ്യത്തിനായി മറ്റനേകം അൽഗൊരിതങ്ങൾ അടൂത്തകാലത്തായി കണ്ടുപിടിച്ചിട്ടുണ്ട്.

1969-ൽ കോളും ഡേവിയും യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെ അടിസ്ഥാനമാക്കി രണ്ടുപേർക്കു കളിക്കാവുന്ന ഒരു കളി വികസിപ്പിച്ചു. യൂക്ലിഡിന്റെ കളി (The game of Euclid) എന്നാണ് ഇതിന്റെ പേര്. a, b വീതം എണ്ണം കല്ലുകളുള്ള രണ്ട് കൂമ്പാരങ്ങളാണ് കളിയുടെ തുടക്കത്തിലുണ്ടാവുക. ഓരോ കളിക്കാരിയും അവരുടെ അവസരമെത്തുമ്പോൾ ചെറിയ കൂമ്പാരത്തിന്റെ ഒരു ഗുണിതം എണ്ണം കല്ലുകൾ വലിയ കൂമ്പാരത്തിൽ നിന്ന് കുറയ്ക്കുന്നു. അതായത്, ഒരു അവസരത്തിന്റെ തുടക്കത്തിൽ കൂമ്പാരങ്ങളിൽ x, y വീതം കല്ലുകളാണുള്ളതെന്നും x നെക്കാളും ചെറുതാണ് y എന്നും ഇരിക്കട്ടെ. അടുത്ത അവസരത്തിൽ കളിക്കാരി x കല്ലുകളുള്ള വലിയ കൂമ്പാരത്തിൽ നിന്നും ചെറിയ കൂമ്പാരത്തിലെ കല്ലുകളുടെ എണ്ണമായ y യുടെ m ഇരട്ടി കുറച്ച് x − my കല്ലുകൾ ബാക്കിയാക്കുന്നു (ഈ സംഖ്യ പൂജ്യത്തിൽ കുറവാകുന്നത് അനുവദിനീയമല്ല). ഒരു കൂമ്പാരത്തിലെ കല്ലുകളെല്ലാം നീക്കുന്ന കളിക്കാരിയാണ് കളിയിലെ വിജയി. ഈ കളിയിൽ രണ്ടുപേരും നന്നായി കളിച്ചാൽ ആരാണ് ജയിക്കുകയെന്നും എങ്ങനെയാണ് ജയം കരസ്ഥമാക്കാൻ കഴിയുക എന്നും തുടക്കത്തിലെ കല്ലുകളിലെ എണ്ണത്തിൽ നിന്നു തന്നെ കണ്ടുപിടിക്കാം.

ഗണിതത്തിലെ ഉപയോഗങ്ങൾ

ബെസു അനന്യത

a, b എന്ന പൂർണ്ണസംഖ്യകളുടെ ഉസാഘ g ആണെങ്കിൽ gയെ a യുടെയും b യുടെയും പൂർണ്ണസംഖ്യകൾ ഗുണോത്തരങ്ങളായുള്ള രേഖീയസഞ്ചയമായി എഴുതാൻ സാധിക്കും എന്ന് ബെസു അനന്യത (Bézout's identity) പറയുന്നു. അതായത്, g = sa + tb എന്ന സമവാക്യത്തിന് നിർദ്ധാരണമായി s, t എന്ന പൂർണ്ണസംഖ്യകളെ കണ്ടുപിടിക്കുന്നത് എല്ലായ്പ്പോഴും സാധ്യമാണ്.

യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിലെ സമവാക്യങ്ങൾ വിപരീതക്രമത്തിലെടുക്കുകയാണെങ്കിൽ ഹരണഫലങ്ങളായ q₀, q₁ മുതലായവ ഉപയോഗിച്ച് s, t എന്നിവയുടെ വിലകൾ കണക്കുകൂട്ടാം. അവസാനത്തെ സമവാക്യത്തിനു തൊട്ടു മുമ്പത്തേത് അനുസരിച്ച് g യുടെ വില ഹരണഫലമായ q_N−1, മുമ്പത്തെ രണ്ട് പടികളിലെ ശിഷ്ടങ്ങളായ r_N−2 , r_N−3 എന്നിവയുടെ വിലകളുമായി ബന്ധിപ്പിക്കാം

g = r_N−1 = r_N−3 − q_N−1 r_N−2 .

ഇതേ രീതിയിൽ വലതുഭാഗത്തെ ശിഷ്ടങ്ങളെ മുൻ പടികളിലെ ഹരണഫലങ്ങളുടെയും ശിഷ്ടങ്ങളുടെയും അടിസ്ഥാനത്തിൽ എഴുതാം

r_N−2 = r_N−4 − q_N−2 r_N−3 ,

r_N−3 = r_N−5 − q_N−3 r_N−4 .

ആദ്യത്തെ സമവാക്യത്തിൽ r_N−2, r_N−3 എന്നിവയ്ക്കു പകരം ഈ രണ്ട് സമവാക്യങ്ങളുടെ വലതുഭാഗങ്ങൾ കൊടുത്താൽ g യെ ശിഷ്ടങ്ങളായ r_N−4, r_N−5 എന്നിവയുടെ രേഖീയസഞ്ചയമായി എഴുതാം. തുടക്കത്തിലെ സംഖ്യകളായ a, b എന്നിവ എത്തുന്നതു വരെ ഈ പ്രക്രിയ തുടരുന്നു:

r₂ = r₀ − q₂ r₁

r₁ = b − q₁ r₀

r₀ = a − q₀ b.

ശിഷ്ടങ്ങളായ r₀, r₁ മുതലായവയ്ക്കുള്ള സമവാക്യങ്ങളെല്ലാം ഒന്നിനുപുറകെ ഒന്നായി ഉപയോഗിച്ചാൽ കിട്ടുന്ന സമവാക്യം 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 കൊണ്ട് ഗുണിച്ചാൽ ഇത് തെളിയിക്കാം

mg = msa + mtb.

ua + vb എന്ന രീതിയിൽ എഴുതാൻ സാധിക്കുന്ന സംഖ്യകളുടെ ഗണം ഉസാഘയുടെ ഗുണിതങ്ങളുടെ ഗണം തന്നെയാണെന്ന് ഇതുവഴി കാണാം. അതായത്, a, b എന്ന സംഖ്യകളെ പൂർണ്ണസംഖ്യകളെക്കൊണ്ട് ഗുണിച്ച് തുക കണ്ടാൽ ലഭിക്കുന്ന സംഖ്യകളുടെ ഗണം gcd(a, b) യുടെ ഗുണിതങ്ങളുടെ ഗണമാണ്. അതിനാൽ a, b എന്നിവയുടെ ഗുണജത്തിന്റെ (ideal) ജനകമാണ് (generator) അവയുടെ ഉസാഘയായ g. ഉസാഘയുടെ ഈ നിർവചനമാണ് ആധുനിക അമൂർത്തബീജഗണിതത്തിലെ സങ്കല്പങ്ങളായ പ്രിൻസിപൽ ഗുണജങ്ങൾ (ഒറ്റ അംഗം ജനകമായുള്ള ഗുണജം), പ്രിൻസിപൽ ഗുണജ മണ്ഡലം (ഓരോ ഗുണജവും പ്രിൻസിപൽ ആയുള്ള മണ്ഡലം) എന്നിവയുടെ അടിസ്ഥാനം.

ഈ ഫലമുപയോഗിച്ച് ചില ഗണിതപ്രശ്നങ്ങൾ നിർവചിക്കാനാകും. ഉദാഹരണമായി a, b വ്യാപ്തമുള്ള രണ്ട് ഗ്ലാസുകളെടൂക്കുക. ആദ്യത്തെ ഗ്ലാസ്സിന്റെ u ഗുണിതങ്ങളും രണ്ടാമത്തെ ഗ്ലാസ്സിന്റെ v ഗുണിതങ്ങളും കൂട്ടുകയോ കുറയ്ക്കുകയോ ചെയ്താൽ ua + vb എന്ന തരത്തിലെഴുതാവുന്ന ഏത് വ്യാപ്തവും കൃത്യമായി അളക്കാൻ സാധിക്കും. ഈ അളവുകളെല്ലാം തന്നെ g = gcd(a, b) യുടെ ഗുണിതങ്ങളാണെന്ന് കാണാം.

വികസിത യൂക്ലിഡിയൻ അൽഗൊരിതം

ബെസു അനന്യതയിലെ s, t എന്ന ഗുണോത്തരങ്ങളെ വികസിത യൂക്ലിഡിയൻ അൽഗൊരിതം ഉപയോഗിച്ച് കണ്ടുപിടിക്കാം. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തോട് രണ്ട് സമാവർത്തന സമവാക്യങ്ങൾ ചേർത്താണ് ഇത് സാധിക്കുന്നത്

s_k = s_k−2 − q_ks_k−1

t_k = t_k−2 − q_kt_k−1

സമാവർത്തനത്തിന്റെ തുടക്കത്തിലെ വിലകൾ ഇവയാണ്

s₋₂ = 1, t₋₂ = 0

s₋₁ = 0, t₋₁ = 1.

N+1 പടികൾക്കൊടുവിൽ ശിഷ്ടം r_N+1 = 0 ആകുമ്പോൾ അൽഗൊരിതം അവസാനിക്കുകയും s = s_N, t = t_N എന്നിങ്ങനെ ബെസു അനന്യതയിലെ ഗുണോത്തരങ്ങൾ ലഭിക്കുകയും ചെയ്യുന്നു.

ഇങ്ങനെ ലഭിക്കുന്ന സംഖ്യകൾ ബെസു അനന്യതയിലെ ഗുണോത്തരങ്ങളാണെന്ന് ഗണിതീയാഗമനം വഴി തെളിയിക്കാം. k − 1 പടികൾ വരെ സമാവർത്തനബന്ധം ശരിയാണെന്ന് കരുതുക. അതായത്, j യുടെ വില k യിൽ കുറവാകുമ്പോഴൊക്കെ താഴെ കൊടുത്തിരിക്കുന്ന സമവാക്യം ശരിയാണെന്നിരിക്കട്ടെ

r_j = s_j a + t_j b

അൽഗൊരിതത്തിന്റെ k ആമത്തെ പടിയിൽ

r_k = r_k−2 − q_kr_k−1.

എന്ന സമവാക്യം ലഭിക്കുന്നു. സമാവർത്തനബന്ധം r_k−2, r_k−1 എന്നിവയ്ക്ക് ശരിയാണെന്നാണ് ഗണിതീയാഗമനത്തിൽ സങ്കല്പിച്ചിരിക്കുന്നത് എന്നതിനാൽ അവയെ യോജിച്ച s, t വിലകളുടെ അടിസ്ഥാനത്തിൽ എഴുതാം

r_k = (s_k−2 a + t_k−2 b) − q_k(s_k−1 a + t_k−1 b).

ഈ സമവാക്യത്തെ പുനഃക്രമീകരിച്ചാൽ k ആമത്തെ പടിയിലെ സമാവർത്തനബന്ധം ലഭിക്കുന്നു.

r_k = s_k a + t_k b = (s_k−2 − q_ks_k−1) a + (t_k−2 − q_kt_k−1) b.

അൽഗൊരിതത്തിന്റെ തുടക്കത്തിലെ r₋₂, r₋₁ എന്നീ ശിഷ്ടങ്ങൾക്കും സമാവർത്തനസമവാക്യം ശരിയായതിനാൽ ഒടുവിൽ N ആമത്തെ പടിയിൽ

g = r_N = s_N a + t_N b

എന്ന സമവാക്യം ലഭിക്കുന്നു. ബെസു അനന്യതയിലെ ഗുണോത്തരങ്ങൾ വലതുഭാഗത്തു കാണാം.

മാട്രിക്സ് രീതി

s, t എന്ന സംഖ്യകളെ തത്തുല്യമായ മാട്രിക്സ് രീതി ഉപയോഗിച്ചും കണ്ടുപിടിക്കാം. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിലെ പടികളിലെ സമവാക്യങ്ങളായ

${\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{N-2}&=q_{N}r_{N-1}+0\end{aligned}}$

എന്നിവയെ ഹരണഫലങ്ങളുടെ 2×2 മാട്രിക്സുകളെക്കൊണ്ട് ശിഷ്ടങ്ങളുടെ ദ്വിമാന സദിശങ്ങളെ (vector) ഗുണിക്കുന്ന രീതിയിൽ എഴുതാം

${\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}\,.$

എല്ലാ ഹരണഫല മാട്രിക്സുകളുടെയും ഗുണനഫലത്തെ M കൊണ്ട് സൂചിപ്പിച്ചാൽ

$\mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}\,.$

യൂക്ലിഡിയൻ അൽഗൊരിതത്തെ ഇങ്ങനെ ലഘൂകരിച്ച് എഴുതാം

${\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}\,.$

g യെ a യുടെയും b യുടെയും രേഖീയസഞ്ചയമായി എഴുതാൻ ഈ സമവാക്യത്തിന്റെ രണ്ടു ഭാഗങ്ങളെയും M ന്റെ മാട്രിക്സ് വിപരീതത്തെക്കൊണ്ട് ഗുണിച്ചാൽ മതിയാകും. ഓരോ ഹരണഫല മാട്രിക്സിന്റെയും സാരണികം (determinant) -1 ആയതിനാൽ അവയുടെ ഗുണനഫലമായ M ന്റെ സാരണികം (−1)^N+1 ആണ്. ഇത് ഒരിക്കലും പൂജ്യമാവുകയില്ല എന്നതിനാൽ M ന്റെ മാട്രിക്സ് വിപരീതം കണ്ടുപിടിക്കുന്നതും സമവാക്യം നിർദ്ധരിക്കുന്നതും എപ്പോഴും സാധ്യമാണ്.

${\begin{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}\,.$

ഈ മാട്രിക്സ് സമവാക്യത്തിന്റെ ആദ്യത്തെ വരി

g = (−1)^N+1 ( m₂₂ a − m₁₂ b)

എന്നായതിനാൽ ബെസു അനന്യതയിലെ പൂർണ്ണസംഖ്യാ ഗുണോത്തരങ്ങൾ s = (−1)^N+1m₂₂, t = (−1)^Nm₁₂ എന്നിവയാണെന്നു കാണാം. ഓരോ പടിയിലും രണ്ട് ഗുണനങ്ങളും രണ്ട് സങ്കലനങ്ങളും ആവശ്യം വരുന്നതിനാൽ മാട്രിക്സ് രീതി തത്തുല്യമായ സമാവർത്തനത്തിന്റെ അത്ര തന്നെ കാര്യക്ഷമമാണെന്നു വരുന്നു.

യൂക്ലിഡിന്റെ പ്രമേയികയും അനന്യമായ ഘടകക്രിയയും

യൂക്ലിഡിന്റെ അൽഗൊരിതം പ്രയോഗിക്കുന്ന മിക്ക അവസരങ്ങളിലും ബെസു അനന്യത അത്യന്താപേക്ഷിതമാണ്. പൂർണ്ണസംഖ്യകളെ അഭാജ്യസംഖ്യകളുടെ ഗുണനഫലമായി എഴുതുന്ന രീതി അനന്യമാണെന്ന അങ്കഗണിതത്തിലെ അടിസ്ഥാന സിദ്ധാന്തം ഇതിന്നുദാഹരണമാണ്.

L എന്ന സംഖ്യ u, v എന്നീ സംഖ്യകളുടെ ഗുണനഫലമാണെന്നു കരുതുക. അതായത്, L = uv. ഇനി w എന്ന മറ്റൊരു സംഖ്യ L ന്റെ ഘടകമാണെന്നു കരുതുക. u വിനോട് സഹ അഭാജ്യമാണ് w എങ്കിൽ അത് v യുടെ ഘടകമായിരിക്കണം എന്ന് ഇപ്രകാരം തെളിയിക്കാം: u, w എന്ന സംഖ്യകളുടെ ഉസാഘ 1 ആയതിനാൽ ബെസു അനന്യത ഉപയോഗിച്ച്

1 = su + tw

എന്ന സമവാക്യത്തിന് നിർദ്ധാരണമായി s, t എന്ന പൂർണ്ണസംഖ്യകൾ കണ്ടുപിടിക്കാനാകും. സമവാക്യത്തിന്റെ രണ്ടു ഭാഗവും v കൊണ്ടു ഗുണിച്ചാൽ

v = suv + twv = sL + twv

എന്ന് ലഭിക്കുന്നു. വലതുഭാഗത്തെ രണ്ട് പദങ്ങളും w ന്റെ ഗുണിതങ്ങളായതിനാൽ ഇടതുഭാഗമായ v യും w ന്റെ ഗുണിതമാണെന്നു വരുന്നു. ഈ ഫലം യൂക്ലിഡിന്റെ പ്രമേയിക എന്നറിയപ്പെടുന്നു. ഇതിൽ നിന്നും, ഒരു അഭാജ്യസംഖ്യ L ന്റെ ഘടകമാണെങ്കിൽ L ന്റെ ഒരു ഘടകമെങ്കിലും ആ അഭാജ്യസംഖ്യയുടെ ഗുണിതമായിരിക്കണം എന്നു കാണാം. നേരെമറിച്ച്, w എന്ന സംഖ്യ a₁, a₂, …, a_n എന്നിവയോടെല്ലാം സഹ-അഭാജ്യമാണെങ്കിൽ w അവയുടെ ഗുണനഫലമായ a₁ × a₂ × … × a_n നോടും സഹ-അഭാജ്യമാണെന്നു വരുന്നു.

യൂക്ലിഡിന്റെ പ്രമേയിക ഉപയോഗിച്ച് ഏതൊരു പൂർണ്ണസംഖ്യയുടെയും ഘടകക്രിയ അനന്യമാണെന്ന് തെളിയിക്കാം. ഇങ്ങനെയല്ല, L നെ m, n വീതം ഘടകങ്ങളുള്ള രണ്ട് രീതികളിൽ ഘടകക്രിയ ചെയ്യാം എന്ന് കരുതുക

L = p₁p₂…p_m = q₁q₂…q_n .

p എന്ന ഓരോ അഭാജ്യസംഖ്യയും L ന്റെ ഘടകമായതിനാൽ അത് q ഘടകങ്ങളിലൊന്നിന്റെയും ഘടകമായിരിക്കണം. എന്നാൽ q യും ഒരു അഭാജ്യസംഖ്യയായതുകൊണ്ട് p = q എന്ന് വരുന്നു. ഇങ്ങനെ അഭാജ്യ ഘടകങ്ങളെയെല്ലാം ഓരോന്നോരോന്നായി ജോടികളാക്കിയ ശേഷം L ൽ നിന്ന് ഹരിച്ചെടുത്ത് ഈ പ്രക്രിയ തുടരുകയാണെങ്കിൽ ഘടകങ്ങളൊന്നും ബാക്കിയാവില്ലെന്നു കാണാം. അതായത്, അഭാജ്യഘടകങ്ങളുടെ ക്രമത്തിൽ വ്യതാസമുണ്ടാകാമെന്നതൊഴിച്ചാൽ ഏതു സംഖ്യയെയും അഭാജ്യസംഖ്യകളായി ഘടകക്രിയ ചെയ്യുന്ന രീതി അനന്യമാണ്. ഈ ഫലം ഗണിതത്തിലെ ഒട്ടേറെ തെളിവുകളിൽ പ്രധാന പങ്കു വഹിക്കുന്നു.

രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ

9x + 12y = 483 എന്ന രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യത്തിന്റെ ആരേഖം. നിർദ്ധാരണങ്ങൾ നീല വൃത്തങ്ങളായി കാണിച്ചിരിക്കുന്നു

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

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 യുടെയും വില വികസിത യൂക്ലിഡിയൻ അൽഗൊരിതം ഉപയോഗിച്ച് കണ്ടുപിടിക്കാം. ഡയൊഫന്റൈൻ സമവാക്യത്തിന്റെ ഒരു നിർദ്ധാരണം ഇങ്ങനെ കണ്ടുപിടിക്കാം: x₁ = s (c/g), y₁ = t (c/g).

സാധാരണ ഗതിയിൽ ഒരു രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യത്തിന്റെ പരിഹാരങ്ങളുടെ എണ്ണം പൂജ്യമോ അനന്തമോ ആണ്. പരിഹാരങ്ങൾ അനന്തമാണെങ്കിൽ കണ്ടുപിടിക്കുന്നതെങ്ങനെയെന്നു നോക്കാം. ഒരേ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യത്തിന്റെ നിർദ്ധാരണങ്ങളാണ് (x₁, y₁), (x₂, y₂) എന്നു കരുതുക. അതായത്,

ax₁ + by₁ = c = ax₂ + by₂

അഥവാ

a(x₁ − x₂) = b(y₂ − y₁).

അതായത്, രണ്ട് പരിഹാരങ്ങളുടെ x വിലകൾക്കിടയിലുള്ള കുറഞ്ഞ വ്യത്യാസം b/g യും y വിലകൾക്കിടയിലുള്ള കുറഞ്ഞ വ്യത്യാസം a/g യുമാണ്. അതായത്, സമവാക്യത്തിന്റെ നിർദ്ധാരണങ്ങളെ സാമാന്യരൂപത്തിൽ ഇങ്ങനെയെഴുതാം:

x = x₁ − bu/g

y = y₁ + au/g.

u വിന്റെ വില എല്ലാ പൂർണ്ണസംഖ്യകളുമെടുത്താൽ (x₁, y₁) എന്ന ഒറ്റ നിർദ്ധാരണത്തിൽ നിന്ന് അനന്തം എണ്ണം പരിഹാരങ്ങളെല്ലാം കണ്ടുപിടിക്കാം. പരിഹാരത്തിലെ സംഖ്യകളെല്ലാം എണ്ണൽസംഖ്യകളാകണമെന്ന് നിഷ്കർഷിച്ചാൽ (x > 0, y > 0) പരിഹാരങ്ങളുടെ എണ്ണം പരിമിതമാണെന്നു വരാം. ചരങ്ങളെക്കാൾ എണ്ണം സമവാക്യങ്ങളുള്ള ചില ഡയൊഫന്റൈൻ വ്യവസ്ഥകൾക്ക് പരിമിതമായ പരിഹാരങ്ങൾ മാത്രമുണ്ടാകാൻ ഈ നിഷ്കർഷ കാരണമാകാം; പൂർണ്ണസംഖ്യകൾക്ക് പകരം വാസ്തവികസംഖ്യകൾ ഉപയോഗിച്ച് നിർദ്ധരിക്കുന്ന രേഖീയ സമവാക്യ വ്യവസ്ഥകളിൽ ഇത് ഒരിക്കലും സംഭവിക്കില്ല.

ഗുണനവിപരീതവും ആർ.എസ്.എ. അൽഗൊരിതവും

പരിമിത എണ്ണം സംഖ്യകളുള്ള ഒരു ഗണവും ഗണത്തിലെ സംഖ്യകളുടെ മേൽ പ്രവർത്തിക്കുന്ന നാല് സംക്രിയകളും ചേർന്ന ബീജീയഘടനയാണ് പരിമിതക്ഷേത്രം. സങ്കലനം, വ്യവകലനം, ഗുണനം, ഹരണം എന്നിവയുടെ സാമാന്യവത്കരണങ്ങളാണ് ഈ സംക്രിയകൾ, ഇവ സാധാരണ സംഖ്യകളെപ്പോലെ ക്രമനിയമം, സാഹചര്യനിയമം, വിതരണനിയമം എന്നിവ പാലിക്കുകയും ചെയ്യുന്നു. ഉദാഹരണമായി, {0, 1, 2, …, 12} എന്ന പതിമൂന്ന് സംഖ്യകളുടെ ഗണം മോഡ്യുലർ അങ്കഗണിത സംക്രിയകൾക്കു കീഴിൽ ഒരു പരിമിതക്ഷേത്രമാണ്. ഈ ക്ഷേത്രത്തിൽ നാല് സംക്രിയകളും (സങ്കലനം, വ്യവകലനം, ഗുണനം, ഹരണം) മോഡ്യുലോ 13 ആയാണ് ചെയ്യുക. അതായത്, സംക്രിയയുടെ ഫലം 0 നും 12 നും ഇടയിലല്ലെങ്കിൽ അത്തരമൊരു സംഖ്യ ലഭിക്കുന്നതു വരെ 13 കൂട്ടുകയോ കുറയ്ക്കുകയോ ചെയ്യുന്നു. ഉദാഹരണമായി, 5 × 7 = 35 mod 13 = 9. ഇത്തരം പരിമിതക്ഷേത്രങ്ങൾ p എന്ന ഏത് അഭാജ്യസംഖ്യയുപയോഗിച്ചും നിർമ്മിക്കാം. കൂടുതൽ സങ്കീർണ്ണമായ നിർവ്വചനങ്ങളുപയോഗിച്ചാൽ അഭാജ്യസംഖ്യകളുടെ ഘാതങ്ങൾക്കും (p ^m) പരിമിതക്ഷേത്രങ്ങൾ സൃഷ്ടിക്കുക സാധ്യമാണ്. പരിമിതക്ഷേത്രങ്ങൾ ഗാൽവ ക്ഷേത്രങ്ങൾ എന്ന പേരിലും അറിയപ്പെടുന്നു, ഇവയെ GF(p) എന്നോ GF(p ^m) എന്നോ ആണ് സൂചിപ്പിക്കുക.

a ഇത്തരമൊരു ക്ഷേത്രത്തിലെ പൂജ്യമല്ലാത്ത അംഗമാണെങ്കിൽ അതിന് അനന്യമായ മോഡ്യുലർ ഗുണനവിപരീതം ഉണ്ടായിരിക്കും. a യുടെ മോഡ്യുലർ ഗുണനവിപരീതം എന്നത് aa⁻¹ = a⁻¹a ≡ 1 mod m. എന്ന സമവാക്യം അനുസരിക്കുന്ന a⁻¹ എന്ന സംഖ്യയാണ്. ax ≡ 1 mod m, എന്ന സർവ്വസമതയ്ക്ക് നിർദ്ധാരണം കാണുന്നതു വഴി ഈ സംഖ്യ കണ്ടുപിടിക്കാം. ഇത് താഴെക്കൊടുത്തിരിക്കുന്ന രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യം നിർദ്ധരിക്കുന്നതിന് തുല്യമാണ്

ax + my = 1.

ഈ സമവാക്യം മേൽ വിവരിച്ചതുപോലെ യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് നിർദ്ധരിക്കാം. മൊഡ്യുലാർ ഗുണനവിപരീതങ്ങൾ കാണുന്നത് ഇകൊമേഴ്സിൽ വ്യാപകമായി ഉപയോഗിക്കുന്ന ആർ.എസ്.എ. അൽഗൊരിതത്തിന്റെ അവശ്യഭാഗമാണ്. ക്ഷേത്രങ്ങൾക്കു പകരം വലയങ്ങളാണ് ആർ.എസ്.എ. അൽഗൊരിതത്തിൽ ഉപയോഗിക്കുന്നതെങ്കിലും വലയങ്ങളിലും (ഗുണനവിപരീതമുള്ള) അംഗങ്ങളുടെ ഗുണനവിപരീതം യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് കണ്ടുപിടിക്കാം. വാർത്താവിനിമയത്തിൽ തെറ്റുകൾ തിരുത്താനുപയോഗിക്കുന്ന എറർ കറക്റ്റിങ് കോഡുകളിലും യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് ഉപയോഗമുണ്ട്. ഉദാഹരണമായി, ഗാൽവ ക്ഷേത്രങ്ങൾ ഉപയോഗിക്കുന്ന ബി.സി.എച്. കോഡ്, റീഡ്-സോളമൻ കോഡ് എന്നിവ ഡീകോഡ് ചെയ്യാൻ ബെർൽകാംപ്-മാസ്സേ അൽഗൊരിതത്തിനു പകരമായി ഇത് ഉപയോഗിക്കാം.

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

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

${\begin{aligned}x_{1}&\equiv x{\pmod {m_{1}}}\\x_{2}&\equiv x{\pmod {m_{2}}}\\&\,\,\,\vdots \\x_{N}&\equiv x{\pmod {m_{N}}}\,.\end{aligned}}$

x_i എന്ന ശിഷ്ടങ്ങളുപയോഗിച്ച് x കണ്ടുപിടിക്കുകയാണ് ലക്ഷ്യം. ഈ സമവാക്യങ്ങളെയെല്ലാം കൂട്ടിച്ചേർത്ത് m_i എന്ന മാപാങ്കങ്ങളുടെ (moduli) ഗുണനഫലമായ M മാപാങ്കമായുള്ള ഒറ്റ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യമായി മാറ്റുക വഴി ഇത് സാധിക്കാം. m_i ഒഴികെയുള്ള മാപാങ്കങ്ങളുടെ ഗുണനഫലത്തെ M_i എന്ന് വിളിക്കുക:

$M_{i}={\frac {M}{m_{i}}}.$

താഴെ കൊടുത്തിരിക്കുന്ന സമവാക്യമനുസരിക്കുന്ന (യഥാർത്ഥത്തിൽ N സമവാക്യങ്ങൾ) സംഖ്യകൾ കണ്ടുപിടിക്കുകയാണ് നിർദ്ധാരണത്തിലെ പ്രധാന പടി

$M_{i}h_{i}\equiv 1{\pmod {m_{i}}}\,.$

h_i എന്ന സംഖ്യകളിൽ നിന്നും x കണ്ടുപിടിക്കാൻ ഈ സൂത്രവാക്യമുപയോഗിക്കാം

$x\equiv (x_{1}M_{1}h_{1}+x_{2}M_{2}h_{2}+\cdots +x_{N}M_{N}h_{N}){\pmod {M}}\,.$

h_i എന്ന സംഖ്യകൾ M_i എന്നിവയുടെ ഗുണനവിപരീതങ്ങളായതിനാൽ മുൻപത്തെ ഭാഗത്ത് വിവരിച്ചതുപോലെ അവയെ യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് കണ്ടുപിടിക്കാം.

സ്റ്റേൺ-ബ്രോക്കോട്ട് ട്രീ

എല്ലാ ധന ഭിന്നകസംഖ്യകളെയും ഒരു അനന്ത ബൈനറി സർച്ച് ട്രീയുടെ രൂപത്തിൽ ക്രമീകരിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം. ഈ ട്രീ സ്റ്റേൺ-ബ്രോക്കോട്ട് ട്രീ എന്നറിയപ്പെടുന്നു. 1 എന്ന സംഖ്യയെ 1/1 എന്ന ഭിന്നസംഖ്യയുടെ രൂപത്തിൽ ട്രീയുടെ മൂലത്തിൽ (root) നിക്ഷേപിക്കാം. a/b എന്ന മറ്റേത് സംഖ്യയുടെയും ട്രീയിലെ സ്ഥാനം നിർണ്ണയിക്കുന്നത് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മൂലരൂപമുപയോഗിച്ച് ഉസാഘയായ gcd(a,b) കണ്ടാണ്. അൽഗൊരിതത്തിന്റെ മൂലരൂപത്തിൽ ശിഷ്ടം കാണുന്നതിനു പകരം വലിയ സംഖ്യയിൽ നിന്ന് ചെറുത് കുറയ്ക്കുകയും സംഖ്യകൾ തുല്യമാകുമ്പോൾ നിർത്തുകയുമാണല്ലോ ചെയ്യുന്നത്. ആദ്യത്തെ സംഖ്യയിൽ നിന്ന് രണ്ടാമത്തേത് കുറയ്ക്കുകയാണെങ്കിൽ ട്രീയിലെ ഒരു ശീഷത്തിൽ നിന്ന് അതിന്റെ വലത്തെ പിൻഗാമിയിലേക്ക് (right child) നീങ്ങുന്നു, പകരം രണ്ടാമത്തെ സംഖ്യയിൽ നിന്ന് ആദ്യത്തേതാണ് കുറയ്ക്കുന്നതെങ്കിൽ ഇടത്തെ പിൻഗാമിയിലേക്കാണ് (left child) നീങ്ങുക. മൂലത്തിൽ നിന്ന് തുടങ്ങി ഈ നിയമമനുസരിച്ച് നീങ്ങിയാൽ അൽഗൊരിതം അവസാനിക്കുമ്പോൾ എത്തുന്ന ശീർഷമാണ് ട്രീയിൽ a/b യുടെ സ്ഥാനം. ഈ പഥത്തിന്റെ നീളവും ക്രമവും a/b അതിന്റെ ലഘൂകരിച്ച രൂപത്തിലാണോ സൂചിപ്പിച്ചിരിക്കുന്നത് എന്നതിനെ ആശ്രയിക്കുന്നില്ല. അതിനാൽ ഓരോ ധനഭിന്നകസംഖ്യയുടെയും ട്രീയിലെ സ്ഥാനം അനന്യമാണെന്നു വരുന്നു.

സ്റ്റേൺ-ബ്രോക്കോട്ട് ട്രീയുടെ ആദ്യത്തെ നാല് തലങ്ങൾ

ഉദാഹരണമായി, 3/4 ന്റെ ശീർഷത്തിലെത്താൻ ട്രീയുടെ മൂലത്തിൽ തുടങ്ങി ഇടത്തേക്ക് ഒരു തവണയും തുടർന്ന് വലത്തേക്ക് രണ്ടു തവണയും നീങ്ങുന്നു:

${\begin{aligned}&\gcd(3,4)&\leftarrow \\={}&\gcd(3,1)&\rightarrow \\={}&\gcd(2,1)&\rightarrow \\={}&\gcd(1,1).\end{aligned}}$

ഭിന്നകസംഖ്യകളുടെ മറ്റൊരു ബൈനറി ട്രീ ആയ കാൽകിൻ-വിൽഫ് ട്രീയുമായും യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് ബന്ധമുണ്ട്. പഥം വിപരീതക്രമത്തിലാണ് നിർമ്മിക്കുന്നത് എന്നതാണ് വ്യത്യാസം: അതായത്, ട്രീയുടെ മൂലത്തിൽ നിന്ന് സംഖ്യയുടെ ശീർഷത്തിലേക്കുള്ള പഥത്തിനു പകരം സംഖ്യയുടെ ശീർഷത്തിൽ നിന്ന് ട്രീയുടെ മൂലത്തിലേക്ക് പോകുന്നു.

സതതഭിന്നം

സതതഭിന്നങ്ങളുമായും (continued fraction) യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് അടുത്ത ബന്ധമുണ്ട്. അൽഗൊരിതത്തിലെ പടികളുടെ സമവാക്യങ്ങളെ ഇപ്രകാരവും എഴുതാം:

${\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&\,\,\,\vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&\,\,\,\vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\,.\end{aligned}}$

ഓരോ സമവാക്യത്തിന്റെയും വലതുഭാഗത്തെ രണ്ടാമത്തെ പദം അടുത്ത സമവാക്യത്തിന്റെ ഇടതുഭാഗത്തിന്റെ വ്യുൽക്രമമാണ്. അതിനാൽ ആദ്യത്തെ രണ്ട് സമവാക്യങ്ങളെയും ഈ വിധത്തിൽ കൂട്ടിച്ചേർക്കാം

${\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}\,.$

മൂന്നാമത്തെ സമവാക്യമുപയോഗിച്ച് ഛേദത്തിലെ r₁/r₀ എന്ന പദത്തെ വികസിപ്പിക്കാം

${\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}\,.$

ഓരോ പടിയിലെയും r_k/r_k−1 എന്ന ശിഷ്ടങ്ങളുടെ അനുപാതത്തെ ഇങ്ങനെ അടുത്ത സമവാക്യമുപയോഗിച്ച് വികസിപ്പിക്കാം. അവസാനത്തെ സമവാക്യവും ഇങ്ങനെ ഉപയോഗിച്ചു കഴിയുമ്പോൾ ഒരു സതതഭിന്നം ലഭിക്കുന്നു

${\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]\,.$

മുകളിൽ gcd(1071, 462) കണ്ടുപിടിച്ചപ്പോൾ q_k എന്ന ഹരണഫലങ്ങളായി ലഭിച്ചത് 2, 3, 7 എന്ന സംഖ്യകളായിരുന്നു. അതിനാൽ 1071/462 എന്ന ഭിന്നസംഖ്യയെ സതതഭിന്നരൂപത്തിൽ ഇപ്രകാരം എഴുതാം

${\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3,7]$

ഇത് ശരിയാണെന്ന് നേരിട്ട് കണക്കുകൂട്ടിയാൽ കാണാൻ വിഷമമില്ല. ഇപ്രകാരം ഏത് ഭിന്നകസംഖ്യയുടെയും സതതഭിന്നരൂപം യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് കണ്ടുപിടിക്കാം.

ഫാക്റ്ററൈസേഷൻ അൽഗൊരിതങ്ങൾ

വലിയ സംഖ്യകളുടെ ഘടകക്രിയ ചെയ്യാനുപയോഗിക്കുന്ന ഫാക്റ്ററൈസേഷൻ അൽഗൊരിതങ്ങളിലെ ഒരു പ്രധാന പടിയാണ് ഉസാഘ കാണുന്നത്. പൊളാർഡ്സ് റോ അൽഗൊരിതം, ഷോർ അൽഗൊരിതം, ഡിക്സൺ രീതി ലെൻസ്ട്ര എലിപ്റ്റിക് കർവ് ഫാക്റ്ററൈസേഷൻ എന്നിവയെല്ലാം ഇങ്ങനെ ഉസാഘ ആവശ്യമുള്ള അൽഗൊരിതങ്ങളാണ്. ഇതിനായ ഉസാഘ കാണാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം. സതതഭിന്ന ഫാക്റ്ററൈസേഷൻ രീതിയിൽ സതതഭിന്നങ്ങൾ കണ്ടുപിടിക്കാനും അൽഗൊരിതം സഹായിക്കുന്നു.

ഗണനപരമായ സങ്കീർണ്ണത

gcd(x,y) കണ്ടുപിടിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിൽ എടുക്കുന്ന പടികളുടെ എണ്ണം. ചുവപ്പും മഞ്ഞയും ബിന്ദുക്കൾ താരതമ്യേന കുറഞ്ഞ എണ്ണം പടികളിൽ ഉസാഘ കണ്ടുപിടിക്കാനാവുന്നത് സൂചിപ്പിക്കുന്നു, വയലറ്റും നീലയും ബിന്ദുക്കൾ സൂചിപ്പിക്കുന്ന സംഖ്യാജോടികൾക്ക് കൂടുതൽ പടികൾ ആവശ്യമാണ്. ഏറ്റവും ഇരുണ്ട ഭാഗം y = Φx എന്ന രേഖയോടടുത്താണ് (ഇവിടെ Φ സുവർണ്ണാനുപാാതമാണ്).

യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ ഗണനപരമായ സങ്കീർണ്ണത സമഗ്രമായി പഠിക്കപ്പെട്ടിട്ടുണ്ട്. അൽഗൊരിതത്തിന്റെ കാര്യക്ഷമത കണ്ടുപിടിക്കാൻ അൽഗൊരിതത്തിലെ പടികളുടെ എണ്ണത്തെ ഒരു പടിയുടെ ഗണനപരമായ ചിലവ്വുകൊണ്ട് ഗുണിച്ചാൽ മതി. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെക്കുറിച്ച് ഇത്തരത്തിലുള്ള ആദ്യത്തെ പഠനം നടത്തിയത് 1811-ൽ എ.എ.എൽ. റെയ്നോഡ് ആണ്, u, v എന്ന സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കാൻ v പടികൾ മതിയെന്ന് കണ്ടുപിടിക്കുകയും പിന്നീട് ഈ സീമ v/2  + 2 ആയി മെച്ചപ്പെടുത്തുകയും ചെയ്തു. എമിൽ ലെഷെർ 1837-ൽ അൽഗൊരിതം ഏറ്റവുമധികം പടികളെടൂക്കുന്ന അവസ്ഥയെക്കുറിച്ച് പഠിച്ചു. അനുക്രമമായ ഫിബനാച്ചി ശ്രേണികളുടെ ഉസാഘ കണ്ടുപിടിക്കുമ്പോഴാണ് ഇത് സംഭവിക്കുന്നത്. ഇതിനു ശേഷം 1841-ൽ പിയേർ ജോസെഫ് എറ്റിയെൻ ഫിങ്ക് പടികളുടെ എണ്ണം 2 log₂ v + 1 മതിയെന്നും അതിനാൽ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത ഇൻപുട്ട് വലിപ്പത്തിന്റെ ബഹുപദമാണെന്നും (polynomial time) കണ്ടെത്തി. ഫിങ്കിന്റെ അപഗ്രഥനം പരിഷ്കരിച്ച ഗബ്രിയേൽ ലാമേ ചെറിയ സംഖ്യയായ b യെ ദശാംശസമ്പ്രദായത്തിൽ എഴുതാനെടുക്കുന്ന അക്കങ്ങളുടെ എണ്ണമായ h ന്റെ അഞ്ചിരട്ടി പടികളേ അൽഗൊരിതത്തിൽ ആവശ്യം വരൂ എന്ന് തെളിയിച്ചു.

ഒരു സംഖ്യ എത്ര വലുതാണെങ്കിലും അതിനെ കമ്പ്യൂട്ടറിന്റെ മെമ്മറിയിൽ ഒറ്റ മഷീൻ വാക്കിൽ സൂക്ഷിക്കാം എന്ന് കരുതുകയാണെങ്കിൽ സംഖ്യകൾക്കു മേൽ ഹരണം, ശിഷ്ടം മുതലായ സംക്രിയകൾ നടത്താൻ എടുക്കുന്ന സമയം സ്ഥിരമാണ് (സംഖ്യയുടെ വലിപ്പത്തെ ആശ്രയിക്കുന്നില്ല). ഈ കല്പനയെ uniform cost model എന്നാണ് അൽഗൊരിതങ്ങളുടെ ഗണനപരമായ സങ്കീർണ്ണതാസിദ്ധാന്തത്തിൽ വിളിക്കുന്നത്. ഈ അനുമാനത്തിനു കീഴിൽ അൽഗൊരിതത്തിന്റെ ഓരോ പടിയും ചെയ്യാനെടുക്കുന്ന സമയം ഒരു സ്ഥിരാങ്കമാണെന്നും അതിനാൽ അൽഗൊരിതത്തിന്റെ ആകെ സങ്കീർണ്ണത O(h) ആണെന്നും വരുന്നു. എന്നാൽ ഒരു മഷീൻ വാക്കിലൊതുങ്ങാത്ത വലിയ സംഖ്യകളുടെ കാര്യത്തിൽ ഈ കല്പന ശരിയാവില്ല. വലിയ സംഖ്യകളുടെ ശിഷ്ടം കാണാനെടൂക്കുന്ന അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത O(h²) വരെ ആകാം എന്നതിനാൽ ടെലിസ്കോപിങ് സീരീസ് ഉപയോഗിച്ച് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മൊത്തം സങ്കീർണ്ണതയും O(h²) ആണെന്നു കാണാം. വലിയ സംഖ്യകളെ കാര്യക്ഷമമായി ഗുണിക്കാനുപയോഗിക്കുന്ന ഷോൺഹാഗെ-സ്ട്രാസെൻ അൽഗൊരിതം മുതലായവ ഉപയോഗിച്ച് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സങ്കീർണ്ണത ഇനിയും കുറച്ച് ക്വാസിലീനിയർ (quasilinear) വരെയാക്കാം.

പടികളുടെ എണ്ണം

a, b എന്ന സംഖ്യകളുടെ ഉസാഘ കാണാനെടുക്കുന്ന പടികളുടെ എണ്ണത്തെ T(a, b) കൊണ്ടു സൂചിപ്പിക്കാം. ഇവയുടെ ഉസാഘ g ആണെങ്കിൽ a = mg എന്നും b = ng എന്നും വരുന്ന തരത്തിൽ m, n എന്ന സഹ-അഭാജ്യസംഖ്യകൾ കണ്ടുപിടിക്കാം. ഇതുപയോഗിച്ച്

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, r₀) = 2 + T(r₀, r₁) = … = N + T(r_N−2, r_N−1) = N + 1 .

ഇവിടെ T(x, 0) = 0 എന്ന് കല്പിച്ചിരിക്കുന്നു.

കൂടിയ വില

ഉസാഘ കണ്ടുപിടിക്കാൻ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിൽ N പടികൾ ആവശ്യമായ ഏറ്റവും ചെറിയ സംഖ്യാജോടി ഫിബനാച്ചി സംഖ്യകളായ F_N+2, F_N+1 എന്നിവയാണ്. കൂടുതൽ കൃത്യമായി പറയുകയാണെങ്കിൽ, യൂക്ലിഡിന്റെ അൽഗൊരിതം a > b ആയ രണ്ടു സംഖ്യകളുടെ ഉസാഘ കാണാൻ N പടികളെടുക്കുന്നുവെങ്കിൽ a ≥ F_N+2, b ≥ F_N+1 ആയിരിക്കും. ഗണിതീയാഗമനം വഴി ഇത് തെളിയിക്കാം. N = 1 ആണെങ്കിൽ a യുടെ ഭാജകമായിരിക്കണം b. ഇങ്ങനെ വരുന്ന ഏറ്റവും ചെറിയ സംഖ്യകൾ b = 1, a = 2 ആണ്. ഇവ യഥാക്രമം ഫിബനാച്ചി സംഖ്യകളായ F₂, F₃ എന്നിവയാണെന്നു കാണാം. N ന്റെ M − 1 വരെയുള്ള എല്ലാ വിലകൾക്കും ഈ പ്രസ്താവന ശരിയാണെന്നു കരുതുക. M പടികളുള്ള അൽഗൊരിതത്തിന്റെ ആദ്യത്തെ ക്രിയ a = q₀b + r₀ കാണുകയാണ്, ഇതിനു ശേഷം b > r₀ എന്നിവയുടെ ഉസാഘ M − 1 പടികളുപയോഗിച്ച് കാണുന്നു. ഗണിതീയാഗമനത്തിലെ പരികല്പനയനുസരിച്ച് b ≥ F_M+1, r₀ ≥ F_M ആണല്ലോ. അതിനാൽ

a = q₀b + r₀ ≥ b + r₀ ≥ F_M+1 + F_M = F_M+2

ഇതാണ് M ആമത്തെ പടിയിൽ തെളിയിക്കേണ്ടിയിരുന്ന അസമത. 1944-ൽ ഗബ്രിയേൽ ലാമേ ആണിത് തെളിയിച്ചത്. ഗണനപരമായ സങ്കീർണ്ണതാസിദ്ധാന്തത്തിന് തുടക്കം കുറിച്ചത് ഈ ഫലമാണ്, ഫിബനാച്ചി സംഖ്യകളുടെ ആദ്യത്തെ പ്രായോഗികമായ ഉപയോഗവും ഈ തെളിവിലായിരുന്നു.

യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിലെ പടികളുടെ എണ്ണം സംഖ്യകളെ ദശാംശസമ്പ്രദായത്തിലെഴുതുമ്പോളുള്ള അക്കങ്ങളുടെ എണ്ണത്തിന്റെ അഞ്ചിരട്ടിയിൽ കൂടുകയില്ല എന്നും ഈ ഫലമുപയോഗിച്ച് തെളിയിക്കാം. അൽഗൊരിതം N പടികളുപയോഗിക്കുന്നുവെങ്കിൽ b യുടെ വില ചുരുങ്ങിയത് F_N+1 ആയിരിക്കും എന്ന് മേലെ കണ്ടല്ലോ. സുവർണ്ണാനുപാതത്തെ φ കൊണ്ട് സൂചിപ്പിച്ചാൽ ഇതിന്റെ വില φ^N−1 എങ്കിലും വരും. b ≥ φ^N−1 ആയതിനാൽ N − 1 ≤ log_φb എന്നു വരുന്നു. സുവർണ്ണാനുപാതത്തിന്റെ സ്വാഭാവിക ലോഗരിതത്തിന്റെ വില 1/5 ൽ കുറവായതിനാൽ

(N − 1)/5 < log₁₀φ log_φb = log₁₀b.

എന്നു കാണാം. അതായത്, N ≤ 5 log₁₀b. ചെറിയ സംഖ്യയായ b യുടെ അക്കങ്ങളുടെ എണ്ണം h ആണെങ്കിൽ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിൽ O(h) ഹരണങ്ങളേ ആവശ്യമായി വരൂ.

ശരാശരി

യൂക്ലിഡിന്റെ അൽഗൊരിതം പൂർത്തീകരിക്കാനെടുക്കുന്ന ശരാശരി പടികളുടെ എണ്ണത്തെ മൂന്ന് രീതിയിൽ നിർവചിക്കാം. വലിയ സംഖ്യയായ a നിർണ്ണയിച്ച ശേഷം ചെറിയ സംഖ്യയായ b യെ 0 മുതൽ a − 1 വരെയുള്ള പൂർണ്ണസംഖ്യകളിൽ നിന്ന് തുല്യ സംഭാവ്യതയോടെ തിരഞ്ഞെടുത്താൽ അൽഗൊരിതത്തിനാവശ്യമായ ശരാശരി പടികളുടെ എണ്ണമെടുക്കുകയാണ് ഒരു വഴി. ഇതിനെ T(a) എന്ന് സൂചിപ്പിക്കാം

$T(a)={\frac {1}{a}}\sum _{0\leq b<a}T(a,b).$

T(a, b) യുടെ വില സംഖ്യകളുടെ ഉസാഘയ്ക്കനുസരിച്ച് കാര്യമായി മാറുന്നതിനാൽ T(a) യും ഇവ്വിധം അവിച്ഛിന്നമായിരിക്കാൻ സാധ്യതയുണ്ട്. ഇത്തരം ഏറ്റക്കുറച്ചിലുകളൊഴിവാക്കാൻ b യെ 0 മുതൽ a − 1 വരെയുള്ള പൂർണ്ണസംഖ്യകളിൽ വച്ച് a യോട് സഹ-അഭാജ്യമായുള്ളവ മാത്രമെടുത്ത് ശരാശരി പടികളുടെ എണ്ണം കാണാം, ഇതിനെ τ(a) കൊണ്ട് സൂചിപ്പിക്കുന്നു

$\tau (a)={\frac {1}{\varphi (a)}}\sum _{\begin{smallmatrix}0\leq b<a\\\gcd(a,b)=1\end{smallmatrix}}T(a,b).$

ഇവിടെ φ(a) എന്നത് a യെക്കാൾ ചെറുതും a യോട് സഹ-അഭാജ്യവുമായ സംഖ്യകളുടെ എണ്ണമാണ്, ഇതിനെ ഓയ്‌ലറുടെ ടോഷ്യന്റ് ഫലനം എന്ന് വിളിക്കുന്നു. ഈ τ ശരാശരി a യുടെ വില വർദ്ധിക്കുന്നതിനനുസരിച്ച് ഏതാണ്ട് ക്രമമായാണ് വർദ്ധിക്കുന്നത്

$\tau (a)={\frac {12}{\pi ^{2}}}\ln 2\ln a+C+O(a^{-1/6-\varepsilon }).$

ക്രമമായ വർദ്ധനവിൽ നിന്നുള്ള വ്യതിയാനം ഏതാണ്ട് a^{−(1/6) + ε} മാത്രമാണ് (ഇവിടെ ε അനന്തസൂക്ഷ്മത്തെ സൂചിപ്പിക്കുന്നു). സമവാക്യത്തിലെ C പോർട്ടറുടെ സ്ഥിരാങ്കം എന്നറിയപ്പെടുന്നു. ഇതിന്റെ വില

$C=-{\frac {1}{2}}+{\frac {6\ln 2}{\pi ^{2}}}\left(4\gamma -{\frac {24}{\pi ^{2}}}\zeta '(2)+3\ln 2-2\right)\approx 1.467$

ആണ്. ഇവിടെ γ ഓയ്‌ലർ-മസ്കരോണി സ്ഥിരാങ്കവും ζ' റീമാൻ സീറ്റ ഫലനത്തിന്റെ അവകലജവുമാണ്. (12/π²) എന്ന ആദ്യത്തെ ഗുണോത്തരം രണ്ട് സ്വതന്ത്രമായ രീതികളുപയോഗിച്ചാണ് കണ്ടുപിടിച്ചത്.

a യുടെ ഭാജകങ്ങളായ d കളെയെല്ലാം പരിഗണിച്ച് τ ശരാശരിയിൽ നിന്നും T ശരാശരി കണ്ടുപിടിക്കാം

$T(a)={\frac {1}{a}}\sum _{d\mid a}\varphi (d)\tau (d)$

താഴെ കൊടുത്തിരിക്കുന്ന സൂത്രവാക്യമുപയോഗിച്ച് ഇതിന്റെ വില ഏകദേശനം ചെയ്യാം

$T(a)\approx C+{\frac {12}{\pi ^{2}}}\ln 2\left(\ln a-\sum _{d\mid a}{\frac {\Lambda (d)}{d}}\right).$

ഇവിടെ Λ(d) മാൻഗോൾട്ട് ഫലനമാണ്.

a, b എന്ന രണ്ട് സംഖ്യകളും 1 മുതൽ n വരെയുള്ള പൂർണ്ണസംഖ്യകളിൽ നിന്ന് തുല്യ സംഭാവ്യതയോടെ തിരഞ്ഞെടുത്ത് മൂന്നാമതൊരു രീതിയിലും ശരാശരി നിർവ്വചിക്കാം, ഇതിനെ Y(n) എന്ന് സൂചിപ്പിക്കുന്നു

$Y(n)={\frac {1}{n^{2}}}\sum _{a=1}^{n}\sum _{b=1}^{n}T(a,b)={\frac {1}{n}}\sum _{a=1}^{n}T(a).$

T(a) യ്ക്ക് മേലെക്കൊടുത്ത ഏകദേശസൂത്രവാക്യമുപയോഗിച്ച് Y(n) നെയും ഏകദേശനം ചെയ്യാം

$Y(n)\approx {\frac {12}{\pi ^{2}}}\ln 2\ln n+0.06.$

ഒരു പടിയുടെ സങ്കീർണ്ണത

യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ k ആമത്തെ പടിയിൽ r_k−2, r_k−1 എന്ന സംഖ്യകളുപയോഗിച്ച് q_k എന്ന ഹരണഫലവും r_k എന്ന ശിഷ്ടവും കണക്കാക്കുകയാണ് ചെയ്യുന്നത്

r_k−2 = q_k r_k−1 + r_k.

ഹരണഫലമായ q_k കണ്ടുപിടിക്കുന്നതാണ് കൂടുതൽ പ്രയാസമേറിയത്, ഇതിന്റെ വില കിട്ടിയാൽ അതുപയോഗിച്ച് ശിഷ്ടമായ r_k എളുപ്പത്തിൽ കണ്ടുപിടിക്കാം

r_k = r_k−2 − q_k r_k−1.

h ബിറ്റുകളുള്ള സംഖ്യകളെ ഹരിക്കാനെടുക്കുന്ന സമയസങ്കീർണ്ണത O(h(ℓ+1)) ആണ് (ഇവിടെ ഹരണഫലത്തിലെ ബിറ്റുകളുടെ എണ്ണമാണ് ℓ).

വ്യവകലനമുപയോഗിക്കുന്ന യൂക്ലിഡിന്റെ മൂല അൽഗൊരിതം ഇതിലും വളരെ മന്ദഗതിയിലുള്ളതാണ്. ഒരു തവണ ഹരിക്കുന്നത് q തവണ വ്യവകലനം ചെയ്യുന്നതിന് തുല്യമാണല്ലോ. a യുടെയും b യുടെയും ഹരണഫലം വളരെ വലുതാണെങ്കിൽ ഒരുപാടു തവണ വ്യവകലനം ചെയ്യേണ്ടി വരും. എന്നിരുന്നാലും, സാധാരണഗതിയിൽ ഹരണഫലങ്ങൾ ചെറിയ സംഖ്യകളായിരിക്കും എന്ന് തെളിയിക്കാൻ സാധിക്കും. u = (q + 1)² എന്നെടുത്താൽ q ഹരണഫലമായി വരാനുള്ള സംഭാവ്യത ഏകദേശം ln|u/(u − 1)| എന്നതിനാലാണിത്. ഹരണഫലമായി 1, 2, 3, 4 എന്ന സംഖ്യകൾ ലഭിക്കാനുള്ള സംഭാവ്യത യഥാക്രമം ഏകദേശം 41.5%, 17.0%, 9.3%, 5.9% ഇങ്ങനെയാണെന്നു കാണാം. വ്യവകലനം ഹരണത്തെക്കാൽ സങ്കീർണ്ണത കുറഞ്ഞ സംക്രിയയായതിനാൽ (പ്രത്യേകിച്ച് വലിയ സംഖ്യകൾക്ക്) വ്യവകലനമുപയോഗിക്കുന്ന മൂല അൽഗൊരിതത്തിന് ഹരണമുപയോഗിക്കുന്ന അൽഗൊരിതത്തോട് കിടനിൽക്കാനാകും. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ ബൈനറി രൂപം ഇതിനെ അടിസ്ഥാനമാക്കിയതാണ്.

പടികളുടെ എണ്ണവും ഒരു പടി ചെയ്യാനെടുക്കുന്ന സമയവുമുപയോഗിച്ച് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ സമയസങ്കീർണ്ണത തുടക്കത്തിലെ സംഖ്യകളിലെ ശരാശരി അക്കങ്ങളുടെ എണ്ണമായ h ന്റെ രണ്ടാംകൃതിയാണെന്ന് (h²) കാണാം. r₀, r₁, …, r_N−1 എന്നീ ശിഷ്ടങ്ങളുടെ അക്കങ്ങളുടെ എണ്ണം h₀, h₁, …, h_N−1 ആണെന്നെടുക്കുക. പടികളുടെ എണ്ണം h നോടൊപ്പം രേഖീയമായാണ് വർദ്ധിക്കുന്നത് എന്നതിനാൽ അൽഗൊരിതം എടുക്കുന്ന ആകെ സമയം

$O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2})$

ആണെന്ന് വരുന്നു.

മറ്റു രീതികൾ

യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ ലാളിത്യം കാരണം അതിന് വളരെ പ്രചാരം ലഭിച്ചിട്ടുണ്ട്. പ്രത്യേകിച്ച് ചെറിയ സംഖ്യകളുടെ ഉസാഘ കാണാൻ അൽഗൊരിതം വ്യാപകമായി ഉപയോഗിക്കപ്പെടുന്നു. ഉസാഘ കാണാനുപയോഗിക്കുന്ന മറ്റ് രീതികളുടെ കാര്യക്ഷമത യൂക്ലിഡിന്റെ അൽഗൊരിതവുമായി താരതമ്യം ചെയ്യാം.

a, b എന്ന സംഖ്യകളുടെ ഉസാഘ കാണാനുള്ള ഒരു വഴി അവയുടെ പൊതു ഘടകങ്ങളെല്ലാം കണ്ടുപിടിക്കുകയാണ്, ഈ ഘടകങ്ങളിൽ ഏറ്റവും വലുതാണ് ഉസാഘ. 2 മുതൽ ചെറിയ സംഖ്യയായ b വരെയുള്ള എല്ലാ സംഖ്യകളെക്കൊണ്ടും ഹരിച്ചു നോക്കി പൊതു ഘടകങ്ങൾ കണ്ടുപിടിക്കാം. ഇതിനെടുക്കുന്ന ക്രിയകളുടെ എണ്ണം b വലുതാകുന്നതിനനുസരിച്ച് രേഖീയമായും b യിലെ അക്കങ്ങളുടെ എണ്ണമനുസരിച്ച് ഘാതാങ്കമായും (exponential) വളരുന്നു. മുകളിൽ വിവരിച്ചതുപോലെ a യുടെയും b യുടെയും പൊതുവായ അഭാജ്യ ഘടകങ്ങളുടെ ഗുണനഫലമായതിനാൽ ആ വിധത്തിലും ഉസാഘ ക്കണ്ടുപിടിക്കാം. എന്നാൽ പൂർണ്ണസംഖ്യകളെ ഘടകക്രിയ ചെയ്യാനുള്ള അൽഗൊരിതങ്ങളും ഉയർന്ന സമയസങ്കീർണ്ണതയുള്ളവയായതിനാൽ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തോളം കാര്യക്ഷമമല്ല. ഇങ്ങനെ പൂർണ്ണസംഖ്യകളെ ഘടകക്രിയ ചെയ്യൽ പ്രയാസമാണ് എന്നതാണ് പല ആധുനിക ഗൂഢാലേഖനവിദ്യകളുടെയും അടിസ്ഥാനം.

കമ്പ്യൂട്ടറിൽ ഉപയോഗിക്കുന്ന ദ്വയാങ്കസംഖ്യാവ്യവസ്ഥ അടിസ്ഥാനമാക്കി ഹരണത്തിനു പകരം കൂടുതൽ വേഗത്തിൽ ചെയ്യാവുന്ന സംക്രിയകളുപയോഗിച്ച് ഉസാഘ കാണുന്ന രീതിയാണ് ദ്വയാങ്ക ഉസാഘ അൽഗൊരിതം. ഈ അൽഗൊരിതത്തിന്റെയും സമയസങ്കീർണ്ണത O(h²) ആണെങ്കിലും സാധാരണ കമ്പ്യൂട്ടറുകളിൽ അത് യൂക്ലിഡിന്റെ അൽഗൊരിതത്തെക്കാൾ വേഗത്തിൽ ഉസാഘ കാണുന്നു. a യുടെയും b യുടെയും ആദ്യ അക്കങ്ങൾ മാത്രം പരിശോധിച്ച് കാര്യക്ഷമത വർദ്ധിപ്പിക്കാൻ സാധിക്കും. ഇതുപോലെ മറ്റ് സംഖ്യാവ്യവസ്ഥകളെ അടിസ്ഥാനമാക്കിയും (k-ary അൽഗൊരിതങ്ങൾ) ഉസാഘ കണ്ടുപിടിക്കാനുള്ള അൽഗൊരിതങ്ങൾ വികസിപ്പിക്കാം, ഇവ അഞ്ചിരട്ടി വരെ വേഗത്തിൽ ഉസാഘ കണ്ടുപിടിക്കാൻ സഹായിക്കുന്നു. ദ്വയാങ്ക അൽഗൊരിതത്തിന്റെ പൊതു തത്ത്വങ്ങളെ അടിസ്ഥാനമാക്കി ഏത് സംഖ്യാവ്യവസ്ഥയിലും ഉസാഘ കാണാനുള്ള വേഗം കൂട്ടുന്ന അൽഗൊരിതമാണ് ലെഹ്മറുടെ ഉസാഘ അൽഗൊരിതം.

വളരെ വലിയ സംഖ്യകളുടെ (25,000 ലേറെ അക്കങ്ങൾ) ഉസാഘ കാണാനുള്ള ക്വാസിലീനിയർ അൽഗൊരിതങ്ങളുമുണ്ട്. ഷോൺഹാഗെ, സ്റ്റെഹ്ലെ-സിമ്മെർമാൻ മുതലായവരുടെ അൽഗൊരിതങ്ങൾ ഉദാഹരണമാണ്. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മാട്രിക്സ് രീതി ആണ് ഇവയ്ക്കടിസ്ഥാനം. ഇവയുടെ സമയസങ്കീർണ്ണത പൊതുവെ O(h (log h)² (log log h)) ആണ്.

സാമാന്യവത്കരണങ്ങൾ

സാധാരണ ഗതിയിൽ എണ്ണൽ സംഖ്യകളുടെ ഉസാഘ കാണാനാണ് യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കുന്നതെങ്കിലും വാസ്തവികസംഖ്യകൾക്കായും ബഹുപദങ്ങൾ, ദ്വിമാന പൂർണ്ണസംഖ്യകൾ, ഹുർവിറ്റ്സ് ക്വാട്ടേർണിയനുകൾ മുതലായ ഗണിതഘടനകൾക്കായും അൽഗൊരിതത്തെ സാമാന്യവത്കരിക്കാം. ഇത്തരം ഗണിതഘടനകളിൽ അനന്യമായ ഘടകക്രിയ സാധ്യമാണ് എന്ന് തെളിയിക്കാൻ അൽഗൊരിതം ഉപയോഗിക്കുന്നു. അതായത്, ഘടനയിലെ അംഗങ്ങളെ അച്ഛേദ്യമായ അംഗങ്ങളാക്കി (ഘടനയിൽ അഭാജ്യസംഖ്യകൾക്ക് സമാനമായ അംഗങ്ങളാണിവ) ഘടകക്രിയ നടത്താൻ ഒരു വഴിയേ ഉള്ളൂ എന്ന് തെളിയിക്കാം. സംഖ്യാസിദ്ധാന്തത്തിലെ പല തെളിവുകളുടെയും അടിസ്ഥാനം അനന്യമായ ഘടകക്രിയയാണ്.

ഭിന്നകസംഖ്യകളും വാസ്തവികസംഖ്യകളും

യൂക്ലിഡ് എലിമെന്റ്സിലെ പത്താം പുസ്തകത്തിൽ വിവരിച്ചതുപോലെ വാസ്തവികസംഖ്യകൾക്കും യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം. a, b എന്ന വാസ്തവികസംഖ്യകളിൽ നിന്നും ഇവ പൂർണ്ണസംഖ്യാഗുണിതങ്ങളായി വരുന്ന g എന്ന വാസ്തവികസംഖ്യ കാണുകയാണ് അൽഗൊരിതത്തിന്റെ ലക്ഷ്യം. അതായത്, a = mg, b = ng എന്ന സമവാക്യങ്ങൾ ശരിയായി വരുകയും m, n എന്നിവ പൂർണ്ണസംഖ്യകളാവുകയും വേണം. a യുടെയും b യുടെയുമിടയിൽ ഒരു പൂർണ്ണസംഖ്യാബന്ധം (integer relation) കണ്ടുപിടിക്കുന്നതിനു തുല്യമാണിത്; അതായത്, sa + tb = 0 എന്ന സമവാക്യമനുസരിക്കുന്ന s, t എന്ന പൂർണ്ണസംഖ്യകൾ കണ്ടുപിടിക്കുക. രണ്ട് നീളങ്ങൾ സാനുപാതമാണോ എന്ന ചോദ്യത്തിനുത്തരമായാണ് യൂക്ലിഡ് ഈ രീതി വികസിപ്പിച്ചത്.

വാസ്തവികസംഖ്യകൾക്കു മേൽ യൂക്ലിഡിന്റെ അൽഗൊരിതം പ്രയോഗിക്കുന്നതിൽ പൂർണ്ണസംഖ്യകളുടെ അൽഗൊരിതവുമായി രണ്ടു വ്യത്യാസങ്ങൾ കാണാം. ഹരണഫലങ്ങളായ q_k മുമ്പത്തെപ്പോലെ പൂർണ്ണസംഖ്യകളാണെങ്കിലും ശിഷ്ടങ്ങളായ r_k വാസ്തവികസംഖ്യകളാണ് എന്നതാണ് ആദ്യത്തെ വ്യത്യാസം. അൽഗൊരിതത്തിലെ പടികളുടെ എണ്ണം പരിമിതമല്ല എന്നതാണ് രണ്ടാമത്തേത്. N പടികളോടെ അൽഗൊരിതം അവസാനിക്കുക a/b ഭിന്നകസംഖ്യയാകുമ്പോൾ (അതായത്, രണ്ടു പൂർണ്ണസംഖ്യകളുടെ അനുപാതം‌) മാത്രമാണ്,

${\frac {a}{b}}={\frac {mg}{ng}}={\frac {m}{n}}.$

ഇങ്ങനെ വരുമ്പോൾ ഈ ഭിന്നത്തെ [q₀; q₁, q₂, ..., q_N] എന്നിങ്ങനെ ഒരു പരിമിത സതതഭിന്നമായി എഴുതാനാകും. അൽഗൊരിതം അവസാനിക്കുന്നില്ലെങ്കിൽ a/b ഒരു അഭിന്നകസംഖ്യയായിരിക്കും, അതിന്റെ സതതഭിന്നമായ [q₀; q₁, q₂, …] അനന്തവും. ഇങ്ങനെ അനന്തമായ സതതഭിന്നങ്ങൾക്ക് ഉദാഹരണമാണ് സുവർണ്ണാനുപാതവും (φ = [1; 1, 1, ...]) രണ്ടിന്റെ വർഗ്ഗമൂലവും (√2 = [1; 2, 2, ...]‌). a/b എന്ന വാസ്തവികസംഖ്യകളുടെ അനുപാതങ്ങൾ ഏതാണ്ടെല്ലാം തന്നെ അഭിന്നകങ്ങളായതിനാൽ അൽഗൊരിതം അവസാനിക്കാതിരിക്കാനാണ് കൂടുതൽ സാധ്യത.

അനന്തമായ സതതഭിന്നത്തെ k പടികൾക്കു ശേഷം മുറിക്കാം. ഇങ്ങനെ ലഭിക്കുന്ന [q₀; q₁, q₂, ..., q_k] എന്ന പരിമിത സതതഭിന്നം a/b യുടെ ഏകദേശവില നൽകുന്നു. k യുടെ വില വർദ്ധിക്കുന്നതിനനുസരിച്ച് ഈ ഏകദേശനം കൂടുതൽ കൃത്യമായി വരുന്നു. kആമത്തെ പടിയിലെ ഏകദേശവില m_k/n_k ആണ്, ഈ അനുക്രമത്തെ അഭിസാരി (convergent) എന്നു വിളിക്കുന്നു. ഈ ഭിന്നത്തിലെ അംശവും ഛേദവും സഹ-അഭാജ്യമായ പൂർണ്ണസംഖ്യകളാണ്, ഇവ താഴെക്കൊടുത്തിരിക്കുന്ന ആവർത്തനബന്ധം അനുസരിക്കുന്നു,

${\begin{aligned}m_{k}&=q_{k}m_{k-1}+m_{k-2}\\n_{k}&=q_{k}n_{k-1}+n_{k-2}.\end{aligned}}$

m₋₁ = n₋₂ = 1, m₋₂ = n₋₁ = 0 എന്ന അടിസ്ഥാനവിലകളോടെയാണ് ആവർത്തനബന്ധം ആരംഭിക്കുന്നത്. m_k/n_k എന്ന അഭിസാരി a/b യെ ഏകദേശനം ചെയ്യുന്ന ഭിന്നകങ്ങളിൽ ഛേദം n_k ആയുള്ളവയിൽ വച്ച് ഏറ്റവും കൃത്യമായിരിക്കും:

$\left|{\frac {a}{b}}-{\frac {m_{k}}{n_{k}}}\right|<{\frac {1}{n_{k}^{2}}}.$

ബഹുപദങ്ങൾ

ഒരു ചരത്തിനുമേലുള്ള (x എന്നെടുക്കുക) ബഹുപദങ്ങളെ കൂട്ടുകയും ഗുണിക്കുകയും ചെയ്യുന്നതിനു പുറമെ അവയെ അച്ഛേദ്യ ബഹുപദങ്ങളുടെ (അഭാജ്യസംഖ്യകൾക്ക് സമാനമായ അംഗങ്ങളാണിവ) ഗുണനഫലമായി എഴുതാനും സാധിക്കും. a(x), b(x) എന്ന ബഹുപദങ്ങളുടെ പൊതുവായ അച്ഛേദ്യ ബഹുപദ ഘടകങ്ങളുടെ ഗുണനഫലമാണ് അവയുടെ ബഹുപദ ഉസാഘയായ g(x). യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് ബഹുപദ ഉസാഘ കണ്ടുപിടിക്കാം. പൂർണ്ണസംഖ്യകളൂടെ അൽഗൊരിതത്തിന് സമാനമായാണ് ഇവിടെയും ഉസാഘ കാണുന്നത്. k ആമത്തെ പടിയിൽ ഹരണഫലമായ q_k(x) എന്ന ബഹുപദവും r_k(x) എന്ന ശിഷ്ട ബഹുപദവും കണ്ടുപിടിക്കുന്നു. ഇവ താഴെക്കൊടുത്തിരിക്കുന്ന ആവർത്തനബന്ധം അനുസരിക്കുന്നു,

$r_{k-2}(x)=q_{k}(x)r_{k-1}(x)+r_{k}(x).$

r₋₂(x) = a(x), r₋₁(x) = b(x) എന്ന വിലകളോടെയാണ് അൽഗൊരിതം ആരംഭിക്കുന്നത്. q_k(x) r_k−1(x) ന്റെ ആദ്യത്തെ പദം r_k−2(x) ന്റെ ആദ്യത്തെ പദത്തിന് തുല്യമാവുന്ന തരത്തിലാണ് ഹരണഫലം കാണുന്നത്. ഓരോ പടിയിലും ഹരണഫല ബഹുപദത്തിന്റെ കൃതി കുറഞ്ഞുവരുമെന്ന് ഇത് ഉറപ്പുവരുത്തുന്നു.: deg[r_k(x)] < deg[r_k−1(x)]. ബഹുപദങ്ങളുടെ കൃതി ഒരിക്കലും പൂജ്യത്തിൽ കുറവാവുകയില്ല എന്നതിനാൽ അൽഗൊരിതം പരിമിത എണ്ണം പടികൾക്കു ശേഷം അവസാനിക്കും. ഏറ്റവുമൊടുവിൽ ലഭിക്കുന്ന പൂജ്യമല്ലാത്ത ശിഷ്ടമാണ് a(x) ന്റെയും b(x) ന്റെയും ഉസാഘ.

ഉദാഹരണമായി, താഴെ കൊടുത്തിരിക്കുന്ന നാലം കൃതി ബഹുപദങ്ങളുടെ (ഇവയുടെ ഘടകക്രിയ കൊടുത്തിരിക്കുന്നു) ഉസാഘ കാണുന്നതെങ്ങനെയെന്നു നോക്കാം

${\begin{aligned}a(x)&=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)\qquad {\text{and}}\\b(x)&=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2).\end{aligned}}$

a(x) നെ b(x) കൊണ്ടു ഹരിച്ചാൽ ശിഷ്ടം r₀(x) = x³ + (2/3)x² + (5/3)x − (2/3) ലഭിക്കുന്നു. അടുത്ത പടിയിൽ b(x) നെ r₀(x) കൊണ്ട് ഹരിച്ച് ശിഷ്ടം r₁(x) = x² + x + 2 ലഭിക്കുന്നു. രണ്ടാമത്തെ പടിയിൽ ശിഷ്ടത്തിന്റെ കൃതി കുറഞ്ഞതു കാണാം. ഒടുവിൽ r₀(x) നെ r₁(x) കൊണ്ടു ഹരിച്ചാൽ ശിഷ്ടം വരില്ലെന്നും അതിനാൽ a(x) ന്റെയും b(x) ന്റെയും ഉസാഘ r₁(x) ആണെന്നും കാണാം. ബഹുപദങ്ങളെ ഘടകക്രിയ ചെയ്തപ്പോൾ ലഭിച്ച പൊതു ഘടകം തന്നെയാണിത്.

പൂർണ്ണസംഖ്യകളുടെ അൽഗൊരിതത്തിന്റെ മേൽ വിവരിച്ച ഉപയോഗങ്ങളിൽ പലതും ബഹുപദങ്ങൾക്കും ഉപയോഗിക്കാം. ബഹുപദങ്ങളുടെ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കാനും ചൈനീസ് ശിഷ്ട പ്രമേയത്തിനും അൽഗൊരിതം ഉപയോഗിക്കാം, ബഹുപദങ്ങളുടെ സതതഭിന്നങ്ങൾ നിർവചിക്കുകയും ചെയ്യാം. ബഹപദങ്ങളുടെ യൂക്ലിഡിയൻ അൽഗൊരിതത്തിന് വേറെയും ഉപയോഗങ്ങളുണ്ട്. ഒരു ബഹുപദ സമവാക്യത്തിന് ഏതെങ്കിലും ഇടവേയിൽ നിർദ്ധാരണം കാണാൻ സഹായിക്കുന്ന സ്റ്റുർമ് ശൃംഖല ഇതിനെ അടിസ്ഥാനമാക്കിയതാണ്. കണ്ട്രോൾ തിയറി യിലെ റൂത്ത്-ഹുർവിറ്റ്സ് സ്ഥിരത മാനദണ്ഡത്തിൽ സ്റ്റുർമ് ശൃംഖല ഉപയോഗിക്കുന്നു.

യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാൻ ബഹുപദങ്ങളുടെ ഗുണോത്തരങ്ങൾ പൂർണ്ണസംഖ്യകളോ വാസ്തവികസംഖ്യകളോ മിശ്രസംഖ്യകൾ പോലുമോ ആകണമെന്ന് നിർബന്ധമില്ല. മേൽ വിവരിച്ച പരിമിത ക്ഷേത്രങ്ങൾ (GF(p)) പോലുള്ള ഏതെങ്കിലും ക്ഷേത്രത്തിലെ അംഗങ്ങൾ ഗുണോത്തരങ്ങളായ ബഹുപദങ്ങൾക്കുമേലും യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം. പൂർണ്ണസംഖ്യകൾക്കു മേൽ അൽഗൊരിതം പ്രയോഗിക്കുന്നതിനെക്കുറിച്ച് മേലെ പറഞ്ഞതെല്ലാം ഇത്തരം ബഹുപദങ്ങളുടെ കാര്യത്തിലും ശരിയായി വരുന്നു..

ഗോസിയൻ പൂർണ്ണസംഖ്യകൾ

u² + v² ന്റെ വില 500ൽ കുറവുള്ള ഗോസിയൻ അഭാജ്യസംഖ്യകൾ (u + vi)

α = u + vi എന്ന രൂപത്തിൽ എഴുതാവുന്ന മിശ്രസംഖ്യകളാണ് ഗോസിയൻ പൂർണ്ണസംഖ്യകൾ. ഇവിടെ u, v എന്നിവ സാധാരണ പൂർണ്ണസംഖ്യകളും i എന്നത് -1 ന്റെ വർഗ്ഗമൂലവുമാണ്. യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ പരിഷ്കരിച്ച രൂപമുപയോഗിച്ച് മുകളിൽ വിവരിച്ച രീതിയിൽ ഗോസിയൻ പൂർണ്ണസംഖ്യകളുടെ ഘടകക്രിയ അനന്യമാണെന്ന് തെളിയിക്കാനാകും.. എല്ലാ പൈതഗോറിയൻ ത്രയങ്ങളും കണ്ടുപിടിക്കാനും ഫെർമയുടെ രണ്ടു വർഗ്ഗ പ്രമേയം തെളിയിക്കാനും ഘടകക്രിയയുടെ അനന്യത ഉപയോഗിക്കാം. എന്നിരുന്നാലും, യൂക്ലിഡിയൻ അൽഗൊരിതത്തിന്റെ സഹായം കൂടാതെ തന്നെ മറ്റു വഴികളിലും ഇത്തരം പ്രമേയങ്ങൾ തെളിയിക്കാവുന്നതാണ്.

α, β എന്ന ഗോസിയൻ പൂർണ്ണസംഖ്യകളുടെ ഉസാഘ കാണാനുള്ള അൽഗൊരിതം സാധാരണ പൂർണ്ണസംഖ്യകൾക്കായുള്ള അൽഗൊരിതത്തിന് വളരെ സമാനമാണെങ്കിലും രണ്ട് വ്യത്യാസങ്ങളുണ്ട്. മുമ്പത്തെപ്പോലെത്തന്നെ അൽഗൊരിതത്തിന്റെ k ആമത്തെ പടിയിൽ താഴെ കൊടുത്തിരിക്കുന്ന ആവർത്തനബന്ധമനുസരിക്കുന്ന q_k എന്ന ഹരണഫലവും r_k എന്ന ശിഷ്ടവും കണ്ടുപിടിക്കുകയാണ് ലക്ഷ്യം,

$r_{k}=r_{k-2}-q_{k}r_{k-1}.$

ഇവിടെ അൽഗൊരിതത്തിന്റെ തുടക്കത്തിലെ ശിഷ്ടങ്ങൾ r_k−2 = α, r_k−1 = β എന്നിവയാണ്. ഓരോ പടിയിലും ശിഷ്ടം മുമ്പത്തേതിനെക്കാൾ കുറവായിരിക്കുകയും ചെയ്യും: |r_k| < |r_k−1|. ഹരണഫലങ്ങളും ശിഷ്ടങ്ങളും പൂർണ്ണസംഖ്യകൾക്കു പകരം ഗോസിയൻ പൂർണ്ണസംഖ്യകളായിരിക്കും എന്നതാണ് പൂർണ്ണസംഖ്യകൾക്കായുള്ള യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിൽ നിന്നുള്ള ആദ്യത്തെ വ്യത്യാസം.

α/β എന്ന മിശ്രസംഖ്യാഭിന്നത്തിന്റെ വാസ്തവികഭാഗത്തെയും സാങ്കല്പികഭാഗത്തെയും ഏറ്റവുമടുത്ത പൂർണ്ണസംഖ്യകളുമായി ഏകദേശനം ചെയ്താണ് ഹരണഫലങ്ങളായ q_k കണ്ടുപിടിക്കുന്നത്. മിശ്രസംഖ്യകളായ ശിഷ്ടങ്ങളിൽ വലുതും ചെറുതും ഏത് എന്ന് കണക്കാക്കുന്ന രീതിയാണ് പൂർണ്ണസംഖ്യകളുടെ അൽഗൊരിതത്തിൽ നിന്നുള്ള രണ്ടാമത്തെ വ്യത്യാസം. ഇതിനായി f(u + vi) = u² + v² എന്ന norm നിർവചിക്കുന്നു, മിശ്രസംഖ്യയുടെ മാപാങ്കത്തിന്റെ വർഗ്ഗമായ ഇത് ഗോസിയൻ പൂർണ്ണസംഖ്യയെ സാധാരണ പൂർണ്ണസംഖ്യയാക്കി മാറ്റുന്ന ഫലനമാണ്. അൽഗൊരിതത്തിന്റെ ഓരോ പടിയിലും ശിഷ്ടത്തിന്റെ norm ആയ f(r_k) മുമ്പത്തെ പടിയിലെ f(r_k−1) നെക്കാൾ കുറവായിരിക്കും. Norm പൂജ്യത്തിൽ കുറവല്ലാത്ത പൂർണ്ണസംഖ്യയായതിനാലും ഓരോ പടിയിലും കുറഞ്ഞുവരുന്നതിനാലും പരിമിത എണ്ണം പടികൾക്കുശേഷം അൽഗൊരിതം അവസാനിക്കണം. പൂജ്യത്തിനു മുമ്പ് ലഭിക്കുന്ന അവസാനത്തെ ശിഷ്ടമാണ് gcd(α, β), തുടക്കത്തിലെ α, β എന്ന പൂർണ്ണസംഖ്യകളെ ശിഷ്ടം വരാതെ ഹരിക്കാവുന്ന norm ഏറ്റവും കൂടിയ ഗോസിയൻ പൂർണ്ണസംഖ്യയാണിത്. ഏകകങ്ങളായ ±1, ±i എന്നിവ കൊണ്ട് ഗുണിക്കാൻ സ്വാതന്ത്ര്യമുണ്ട് എന്നതൊഴിച്ചാൽ ഈ ഉസാഘ അനന്യമാണ്.

പൂർണ്ണസംഖ്യകളുടെ അൽഗൊരിതത്തിന്റെ പല ഉപയോഗങ്ങളും ഗോസിയൻ പൂർണ്ണസംഖ്യകൾക്കും ഉപയോഗിക്കാം. ഗോസിയൻ പൂർണ്ണസംഖ്യകൾക്കു മേൽ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യങ്ങളും ചൈനീസ് ശിഷ്ടപ്രമേയവും നിർദ്ധരിക്കുന്നതും സതതഭിന്നങ്ങൾ നിർവചിക്കുന്നതും ഉദാഹരണമാണ്.

യൂക്ലിഡിയൻ മണ്ഡലങ്ങൾ

സങ്കലനം, ഗുണനം എന്ന് വിളിക്കാവുന്ന രണ്ട് ദ്വയാങ്കസംക്രിയകൾ നിർവചിച്ചിട്ടുള്ള R എന്ന ഗണത്തെ അതൊരു ക്രമവിനിമേയ വലയമായിരിക്കുകയും അതിനുമേൽ യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ ഒരു സാമാന്യരൂപം നിർവചിക്കാൻ സാധിക്കുകയും ചെയ്താൽ യൂക്ലിഡിയൻ മണ്ഡലം എന്നു വിളിക്കാം. സങ്കലനം, ഗുണനം എന്ന പേരുകളിൽ അറിയപ്പെടുന്നുവെങ്കിലും സംക്രിയകൾ സാധാരണ സംഖ്യകൾക്കുമേലുള്ള സംക്രിയകൾക്ക് സമാനമാകണമെന്നില്ല; ഗ്രൂപ്പുകളിലോ മോണോയ്ഡുകളിലോ ഉള്ളതുപോലെ സാമാന്യ സംക്രിയകളുമാകാം. എന്നിരുന്നാലും ഈ സംക്രിയകൾ അങ്കഗണിതത്തിലേതുപോലെ ക്രമനിയമം, സാഹചര്യനിയമം, വിതരണനിയമം എന്നിവ പാലിക്കേണ്ടതുണ്ട്.

യൂക്ലിഡിന്റെ അൽഗൊരിതം നിർവചിക്കാനായി ഇതിനു പുറമെ R ലെ അംഗങ്ങളെ ധനപൂർണ്ണസംഖ്യകളിലേക്ക് കൊണ്ടുചെല്ലുന്ന f എന്ന യൂക്ലിഡിയൻ ഫലനവും നിർവചിക്കേണ്ടതുണ്ട്. R ലെ a, b എന്ന ഏത് അംഗങ്ങളെടുത്താലും a = qb + r എന്ന സമവാക്യമനുസരിക്കുന്ന q, r എന്ന അംഗങ്ങളെ R ൽ തന്നെ കണ്ടെത്താൻ സാധിക്കുകയും f(r) < f(b) ആയിരിക്കുകയും വേണം. ഗോസിയൻ പൂർണ്ണസംഖ്യകൾക്ക് മുകളിൽ ഉപയോഗിച്ച norm യൂക്ലിഡിയൻ ഫലനത്തിന് ഉദാഹരണമാണ്. f എന്ന ഫലനം ഗണത്തിനനുസരിച്ച് സംഖ്യകളുടെ പരിമാണമോ ബഹുപദങ്ങളുടെ കൃതിയോ ഒക്കെയാവാം. അൽഗൊരിതത്തിന്റെ ഓരോ പടിയിലും f ന്റെ വില കുറഞ്ഞുവരുന്നു എന്നതാണ് പ്രധാനം; പൂജ്യത്തിൽ കുറയാത്ത പൂർണ്ണസംഖ്യയായതിനാൽ പരിമിത എണ്ണം പടികൾക്കു ശേഷം അൽഗൊരിതം അവസാനിക്കുകം. പൂജ്യത്തിൽ കുറയാത്ത പൂർണ്ണസംഖ്യകളുടെ ശൂന്യമല്ലാത്ത ഏത് ഗണത്തിലും ഏറ്റവും ചെറിയ ഒരു അംഗമുണ്ട് എന്ന well-ordering principle ആണ് ഇതിനടിസ്ഥാനം.

അങ്കഗണിതത്തിലെ അടിസ്ഥാന സിദ്ധാന്തം യൂക്ലിഡിയൻ മണ്ഡലങ്ങളിലൊക്കെയും സാധുവാണ്. അതായത്, ഒരു യൂക്ലിഡിയൻ മണ്ഡലത്തിലെ ഏത് അംഗത്തെയും വീണ്ടും ലഘൂകരിക്കാനാകാത്ത അംഗങ്ങളുടെ ഗുണനഫലമായി അനന്യമായ രീതിയിൽ ഘടകക്രിയ ചെയ്യാനാകും. എല്ലാ യൂക്ലിഡിയൻ മണ്ഡലങ്ങളും അനന്യ ഘടകക്രിയാ മണ്ഡലങ്ങളാണ് (unique factorization domain - UFD), എന്നാൽ അനന്യ ഘടകക്രിയാ മണ്ഡലങ്ങളെല്ലാം യൂക്ലിഡിയൻ ആയിരിക്കണമെന്നില്ല. ഏത് രണ്ട് അംഗങ്ങളുടെയും ഉസാഘ കാണാൻ സാധിക്കുന്ന ഉസാഘ മണ്ഡലങ്ങളുടെ (GCD domain) ഉപക്ലാസ്സുകളാണ് യൂക്ലിഡിയൻ മണ്ഡലങ്ങളും UFD കളും. അതായത്, ഉസാഘ മണ്ഡലങ്ങളിൽ അംഗജോടികൾക്കെല്ലാം ഉസാഘയുണ്ടെങ്കിലും അത് യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് കണക്കുകൂട്ടാൻ സാധിക്കണമെന്നില്ല. യൂക്ലിഡിയൻ മണ്ഡലങ്ങളെല്ലാം പ്രിൻസിപൽ ഗുണജ മണ്ഡലങ്ങളാണ് (PID) - എല്ലാ ഗുണജങ്ങളും പ്രിൻസിപൽ ഗുണജങ്ങളായുള്ള പൂർണ്ണസംഖ്യാ മണ്ഡലങ്ങളാണ് (integral domain) ഇവ. എല്ലാ പ്രിൻസിപൽ ഗുണജ മണ്ഡലങ്ങളും യൂക്ലിഡിയൻ മണ്ഡലങ്ങളാവണമെന്നില്ല.

യൂക്ലിഡിയൻ മണ്ഡലങ്ങളിലെ അനന്യമായ ഘടകക്രിയയ്ക്ക് വളരെയധികം ഉപയോഗങ്ങളുണ്ട്. ഉദാഹരണമായി, ഗോസിയൻ പൂർണ്ണസംഖ്യകളിലെ അനന്യ ഘടകക്രിയ പൈതഗോറിയൻ ത്രയങ്ങളുടെ സൂത്രവാക്യം കണ്ടുപിടിക്കാനും ഫെർമയുടെ രണ്ട് വർഗ്ഗ പ്രമേയം തെളിയിക്കാനും ഉപയോഗിക്കാം. ഫെർമയുടെ അവസാന സിദ്ധാന്തം തെളിയിക്കാൻ ഗബ്രിയേൽ ലാമേ 1847-ൽ ശ്രമിച്ചത് അനന്യ ഘടകക്രിയയുപയോഗിച്ചായിരുന്നു. x, y എന്നിവ പൂർണ്ണസംഖ്യകളായി വരുന്ന x + ωy എന്ന സംഖ്യകളുടെ (ഇവിടെ ω = e^2iπ/n എന്നത് 1 ന്റെ n ആം മൂലമാണ്. അതായത്, ωⁿ = 1) അനന്യ ഘടകക്രിയയുപയോഗിക്കാനാണ് ലാമേ ശ്രമിച്ചത്. എന്നാൽ n ന്റെ ചില വിലകൾക്ക് മാത്രമേ അനന്യ ഘടകക്രിയ സാധ്യമാവുകയും ഈ വിധത്തിൽ ഫെർമയുടെ സിദ്ധാന്തം തെളിയിക്കാനാവുകയും ചെയ്യൂ. n = 3 ആയി വരുന്ന ഐസൻസ്റ്റൈൻ പൂർണ്ണസംഖ്യകൾ ഉദാഹരണമാണ്. n ന്റെ എല്ലാ വിലകൾക്കും അനന്യ ഘടകക്രിയ സാധ്യമല്ല എന്നതിനാൽ സിദ്ധാന്തം തെളിയിക്കാനുള്ള ഈ ശ്രമം പരാജയപ്പെട്ടു. ചില സൈക്ലോടോമിക് ക്ഷേത്രങ്ങളിൽ അനന്യ ഘടകക്രിയ സാധ്യമല്ല എന്നതാണ് ഏൺസ്റ്റ് കുമ്മർ ഗുണജസംഖ്യകൾ എന്ന ആശയവും പിന്നീട് റിച്ചാർഡ് ഡെഡെകിൻഡ് ഗുണജങ്ങളും കണ്ടുപിടിക്കുന്നതിലേക്ക് നയിച്ചത്.

ദ്വിമാന പൂർണ്ണസംഖ്യകളുടെ അനന്യ ഘടകക്രിയ

u + vω എന്ന രീതിയിലെഴുതാവുന്ന ഐസൻസ്റ്റൈൻ പൂർണ്ണസംഖ്യകളിൽ അഭാജ്യമായവയെ മിശ്രസംഖ്യാപ്രതലത്തിൽ ചിത്രീകരിച്ചിരിക്കുന്നു. ഇവിടെ ω എന്നത് 1 ന്റെ ഘനമൂലമാണ്. Norm 500 ൽ കുറവായ സംഖ്യകളാണ് ചിത്രത്തിലുള്ളത്.

ദ്വിമാന പൂർണ്ണസംഖ്യകളുടെ വലയങ്ങളിൽ ചിലത് യൂക്ലിഡിയൻ മണ്ഡലത്തിന് ഉദാഹരണമാണ്. ഗോസിയൻ പൂർണ്ണസംഖ്യകളിൽ സാങ്കല്പിക ഏകകമായ i ക്കു പകരം ω എന്ന സംഖ്യ ഉപയോഗിക്കുമ്പോൾ ലഭിക്കുന്ന ബീജീയഘടനയാണ് ദ്വിമാന പൂർണ്ണസംഖ്യകൾ. അതായത്, u, v എന്നിവ പൂർണ്ണസംഖ്യകളായി വരുന്ന u + vω എന്ന രൂപത്തിലെഴുതാവുന്ന സംഖ്യകളാണിത്. ഇവിടെ ω എന്ന സംഖ്യ D എന്ന പൂർണ്ണസംഖ്യയുടെ വിലയനുസരിച്ച് രണ്ട് രൂപത്തിൽ നിർവചിക്കാം. D നാലിന്റെ ഒരു ഗുണിതത്തെക്കാൾ ഒന്ന് കൂടുതലാണെങ്കിൽ

$\omega ={\sqrt {D}}$

എന്നും അല്ലാത്ത പക്ഷം

$\omega ={\frac {1+{\sqrt {D}}}{2}}$

എന്നും നിർവചിക്കുന്നു. D യുടെ ഓരോ വിലയ്ക്കും വ്യത്യസ്തമായ ഓരോ ഗണം ലഭിക്കുന്നു.

മുകളിൽ ഗോസിയൻ പൂർണ്ണസംഖ്യകളുടെ കാര്യത്തിൽ എടുത്തതുപോലെ f ഒരു norm-ഫലനമാണെങ്കിൽ അത്തരം മണ്ഡലത്തെ norm-യൂക്ലിഡിയൻ എന്നു വിളിക്കുന്നു. D യുടെ വില −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, or 73 എന്നിവയിലൊന്ന്നാകുമ്പോഴാണ് ദ്വിമാന പൂർണ്ണസംഖ്യകൾ norm-യൂക്ലിഡിയൻ ആവുക. D = −1 ആവുമ്പോൾ ഗോസിയൻ പൂർണ്ണസംഖ്യകളും D = −3 ആവുമ്പോൾ ഐസൻസ്റ്റൈൻ പൂർണ്ണസംഖ്യകളും ലഭിക്കുന്നു.

f ഏതെങ്കിലും യൂക്ലിഡിയൻ ഫലനമായാൽ മതിയെങ്കിൽ ഏതൊക്കെ D വിലകൾക്കാണ് ദ്വിമാന പൂർണ്ണസംഖ്യകൾ യൂക്ലിഡിയൻ മണ്ഡലങ്ങളാവുക എന്നത് ഗണിതശാസ്ത്രത്തിലെ ഒരു തുറന്ന പ്രശ്നമാണ്. D = 69 നാണ് norm-യൂക്ലിഡിയൻ അല്ലാത്തതും എന്നാൽ യൂക്ലിഡിയൻ ആയതുമായ ഒരു ദ്വിമാന പൂർണ്ണസംഖ്യാമണ്ഡലം ആദ്യമായി 1994-ൽ കണ്ടുപിടിക്കുന്നത്. റീമാൻ പരികല്പനയുടെ സാമാന്യരൂപം ശരിയാണെങ്കിൽ D > 0 ആയുള്ള ദ്വിമാന പൂർണ്ണസംഖ്യാ വലയങ്ങൾ യൂക്ലിഡിയൻ മണ്ഡലങ്ങളാവുന്നത് കൃത്യം അവ പ്രിൻസിപൽ ഗുണജ മണ്ഡലങ്ങളാവുമ്പോഴാണെന്ന് 1973-ൽ വൈൻബെർഗർ തെളിയിച്ചു.

ക്രമവിനിമേയമല്ലാത്ത വലയങ്ങൾ

ഹുർവിറ്റ്സ് ക്വാട്ടേർണിയനുകൾ പോലുള്ള ക്രമവിനിമേയമല്ലാത്ത (noncommutative) വലയങ്ങളിലും യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം. α, β എന്നിവ അത്തരമൊരു വലയത്തിലെ അംഗങ്ങളാണെന്നിരിക്കട്ടെ. ξ, η എന്ന വലയത്തിലെ ഏതെങ്കിലും അംഗങ്ങൾക്ക് α = ξδ, β = ηδ എന്ന സമവാക്യങ്ങൾ സാധുവാകുന്നുവെങ്കിൽ δ യെ α യുടെയും β യുടെയും വലത് പൊതു ഘടകം എന്നുവിളിക്കുന്നു. ഇതുപോലെ α = δξ, β = δη എന്നിവ ശരിയാണെങ്കിൽ ഇടത് പൊതു ഘടകം എന്നും വിളിക്കാം. ഗുണനം ക്രമനിയമമനുസരിക്കാത്തതിനാൽ ഇടത് ഘടകങ്ങൾക്കും വലത് ഘടകങ്ങൾക്കും യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ വെവ്വേറെ രൂപങ്ങളുണ്ട്. വലത് ഘടകങ്ങളാണെടുക്കുന്നതെങ്കിൽ gcd(α, β) കാണാനുള്ള ആദ്യത്തെ പടി ഇപ്രകാരമെഴുതാം

$\rho _{0}=\alpha -\psi _{0}\beta =(\xi -\psi _{0}\eta )\delta ,$

ഇവിടെ ψ₀ ഹരണഫലവും ρ₀ ശിഷ്ടവുമാണ്. α, β എന്നിവയുടെ പൊതുവായ ഏതൊരു ഘടകവും ശിഷ്ടമായ ρ₀ ന്റെയും ഘടകമായിരിക്കുമെന്ന് ഈ സമവാക്യം പറയുന്നു. ഇതിനു സമാനമായി ഇടത് ഘടകങ്ങൾക്കും സമവാക്യമെഴുതാം

$\rho _{0}=\alpha -\beta \psi _{0}=\delta (\xi -\eta \psi _{0}).$

ഇവയിൽ ഏത് സമവാക്യമെടുത്താലും ഇടതോ വലതോ ഉസാഘ ലഭിക്കുന്നതു വരെ ഈ പ്രക്രിയ തുടരാം. യൂക്ലിഡിയൻ മണ്ഡലങ്ങളിലേതുപോലെ ഓരോ പടിയിലും ശിഷ്ടത്തിന്റെ "വലിപ്പം" കുറഞ്ഞുവരണം. അതായത്, ρ₀ യുടെ വലിപ്പം β യെക്കാൾ ചെറുതായിരിക്കണം. ρ₀ ന്റെ വലിപ്പത്തിന് പരിമിത എണ്ണം സാധ്യതകളേ ഉണ്ടാവൂ, അൽഗൊരിതം അവസാനിക്കുമെന്ന് ഉറപ്പുവരുത്താനാണിത്.

ഉസാഘയുമായി ബന്ധപ്പെട്ട് മുകളിൽ കൊടുത്ത ഫലങ്ങൾ മിക്കതും ക്രമവിനിമേയമല്ലാത്ത സംഖ്യകളുടെ കാര്യത്തിലും സാധുവാണ്. ഉദാഹരണമായി, വലത്തെ ഉസാഘ gcd(α, β) യെ α യുടെയും β യുടെയും രേഖീയസഞ്ചയമായി എഴുതാനാകുമെന്ന് ബെസു അനന്യത പറയുന്നു. അതായത്,

$\Gamma _{\text{right}}=\sigma \alpha +\tau \beta$

എന്ന ബന്ധമനുസരിക്കുന്ന σ, τ എന്ന അംഗങ്ങളെ കണ്ടുപിടിക്കാൻ സാധിക്കും. ഇതുപോലെ ഇടത്തെ ഉസാഘയെയും രേഖീയസഞ്ചയമായി എഴുതാം,

$\Gamma _{\text{left}}=\alpha \sigma +\beta \tau .$

ഇങ്ങനെ ബെസു അനന്യതയുപയോഗിച്ച് ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കാം. എല്ലാ ധനപൂർണ്ണസംഖ്യകളെയും നാല് പൂർണ്ണവർഗ്ഗങ്ങളുടെ തുകയായി എഴുതാം എന്ന് സ്ഥാപിക്കുന്ന ലഗ്രാഞ്ചിന്റെ നാല് വർഗ്ഗ പ്രമേയം ക്വാട്ടേർണിയനുകളുടെ ഉസാഘ ഈ വിധത്തിലുപയോഗിച്ച് തെളിയിക്കാവുന്നതാണ്.

ഗ്രന്ഥസൂചി

• Cohen, H. (1993). A Course in Computational Algebraic Number Theory. New York: Springer-Verlag. ISBN 0-387-55640-0. {{cite book}}: Invalid |ref=harv (help)
• Cohn, H. (1962). Advanced Number Theory. New York: Dover. ISBN 0-486-64023-X. {{cite book}}: Invalid |ref=harv (help)
• Cox, D.; Little, J.; O'Shea, D. (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (2nd ed.). Springer-Verlag. ISBN 0-387-94680-2. {{cite book}}: Invalid |ref=harv (help)
• Crandall, R.; Pomerance, C. (2001). Prime Numbers: A Computational Perspective (1st ed.). New York: Springer-Verlag. ISBN 0-387-94777-9. {{cite book}}: Invalid |ref=harv (help)
• Lejeune Dirichlet, P. G. (1894). Dedekind, Richard (ed.). Vorlesungen über Zahlentheorie (Lectures on Number Theory) (in ജർമ്മൻ). Braunschweig: Vieweg. LCCN 03005859. OCLC 490186017. {{cite book}}: Invalid |ref=harv (help). See also Vorlesungen über Zahlentheorie
• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison–Wesley. ISBN 0-201-89684-2. {{cite book}}: Invalid |ref=harv (help)
• LeVeque, W. J. (1996) [1977]. Fundamentals of Number Theory. New York: Dover. ISBN 0-486-68906-9. {{cite book}}: Invalid |ref=harv (help)
• Mollin, R. A. (2008). Fundamental Number Theory with Applications (2nd ed.). Boca Raton: Chapman & Hall/CRC. ISBN 978-1-4200-6659-3. {{cite book}}: Invalid |ref=harv (help)
• Ore, O. (1948). Number Theory and Its History. New York: McGraw–Hill. {{cite book}}: Invalid |ref=harv (help)
• Rosen, K. H. (2000). Elementary Number Theory and its Applications (4th ed.). Reading, MA: Addison–Wesley. ISBN 0-201-87073-8. {{cite book}}: Invalid |ref=harv (help)
• Schroeder, M. (2005). Number Theory in Science and Communication (4th ed.). Springer-Verlag. ISBN 0-387-15800-6. {{cite book}}: Invalid |ref=harv (help)
• Stark, H. (1978). An Introduction to Number Theory. MIT Press. ISBN 0-262-69060-8. {{cite book}}: Invalid |ref=harv (help)
• Stillwell, J. (1997). Numbers and Geometry. New York: Springer-Verlag. ISBN 0-387-98289-2. {{cite book}}: Invalid |ref=harv (help)
• Stillwell, J. (2003). Elements of Number Theory. New York: Springer-Verlag. ISBN 0-387-95587-9. {{cite book}}: Invalid |ref=harv (help)
• Tattersall, J. J. (2005). Elementary Number Theory in Nine Chapters. Cambridge: Cambridge University Press. ISBN 978-0-521-85014-8. {{cite book}}: Invalid |ref=harv (help)