smcproject/ml-wiki-sentences huggingface dataset:
യൂക്ലിഡിയൻ ഹരണത്തിന് അടിസ്ഥാനമായ പ്രമേയം ഈ നിഷ്കർഷയോടെ ഹരണഫലവും ശിഷ്ടവും കണ്ടുപിടിക്കുന്നത് സാധ്യമാണെന്നും ഫലം അനന്യമാണെന്നും പറയുന്നു.
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന്റെ മൂലരൂപത്തിൽ ആവർത്തിച്ച് വ്യവകലനം ചെയ്തുകൊണ്ടാണ് ഹരണഫലവും ശിഷ്ടവും കണ്ടിരുന്നത്.
അതായത്, ഫലം 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 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 എന്ന സംഖ്യകളുടെ ഉസാഘ കാണാനാവശ്യമായ പടികളുടെ എണ്ണം ഏറ്റവും കുറവാകുന്നത് | r k + 1 r k | 1 φ ∼ 0.618 , {\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right| {\frac {1}{\varphi }}\sim 0.618,} ആവുന്ന തരത്തിൽ q k തിരഞ്ഞെടുക്കുമ്പോഴാണ് (ഇവിടെ φ {\displaystyle \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 0 , q 1 മുതലായവ ഉപയോഗിച്ച് 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 2 = r 0 − q 2 r 1 r 1 = b − q 1 r 0 r 0 = a − q 0 b .
ശിഷ്ടങ്ങളായ r 0 , r 1 മുതലായവയ്ക്കുള്ള സമവാക്യങ്ങളെല്ലാം ഒന്നിനുപുറകെ ഒന്നായി ഉപയോഗിച്ചാൽ കിട്ടുന്ന സമവാക്യം 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 k s k −1 t k = t k −2 − q k t k −1
സമാവർത്തനത്തിന്റെ തുടക്കത്തിലെ വിലകൾ ഇവയാണ് s −2 = 1, t −2 = 0 s −1 = 0, t −1 = 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 k r 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 k s k −1 ) a + ( t k −2 − q k t k −1 ) b .
അൽഗൊരിതത്തിന്റെ തുടക്കത്തിലെ r −2 , r −1 എന്നീ ശിഷ്ടങ്ങൾക്കും സമാവർത്തനസമവാക്യം ശരിയായതിനാൽ ഒടുവിൽ N ആമത്തെ പടിയിൽ g = r N = s N a + t N b
ബെസു അനന്യതയിലെ ഗുണോത്തരങ്ങൾ വലതുഭാഗത്തു കാണാം.
മാട്രിക്സ് രീതി
s , t എന്ന സംഖ്യകളെ തത്തുല്യമായ മാട്രിക്സ് രീതി ഉപയോഗിച്ചും കണ്ടുപിടിക്കാം.
യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിലെ പടികളിലെ സമവാക്യങ്ങളായ a = q 0 b + r 0 b = q 1 r 0 + r 1 ⋮ r N − 2 = q N r N − 1 + 0 {\displaystyle {\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) ഗുണിക്കുന്ന രീതിയിൽ എഴുതാം ( a b ) = ( q 0 1 1 0 ) ( b r 0 ) = ( q 0 1 1 0 ) ( q 1 1 1 0 ) ( r 0 r 1 ) = ⋯ = ∏ i = 0 N ( q i 1 1 0 ) ( r N − 1 0 ) .
{\displaystyle {\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 കൊണ്ട് സൂചിപ്പിച്ചാൽ M = ( m 11 m 12 m 21 m 22 ) = ∏ i = 0 N ( q i 1 1 0 ) = ( q 0 1 1 0 ) ( q 1 1 1 0 ) ⋯ ( q N 1 1 0 ) .
{\displaystyle \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}}\,.
യൂക്ലിഡിയൻ അൽഗൊരിതത്തെ ഇങ്ങനെ ലഘൂകരിച്ച് എഴുതാം ( a b ) = M ( r N − 1 0 ) = M ( g 0 ) .
{\displaystyle {\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 ന്റെ മാട്രിക്സ് വിപരീതം കണ്ടുപിടിക്കുന്നതും സമവാക്യം നിർദ്ധരിക്കുന്നതും എപ്പോഴും സാധ്യമാണ്.
( g 0 ) = M − 1 ( a b ) = ( − 1 ) N + 1 ( m 22 − m 12 − m 21 m 11 ) ( a b ) .
{\displaystyle {\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 22 a − m 12 b )
എന്നായതിനാൽ ബെസു അനന്യതയിലെ പൂർണ്ണസംഖ്യാ ഗുണോത്തരങ്ങൾ s = (−1) N +1 m 22 , t = (−1) N m 12 എന്നിവയാണെന്നു കാണാം.
ഓരോ പടിയിലും രണ്ട് ഗുണനങ്ങളും രണ്ട് സങ്കലനങ്ങളും ആവശ്യം വരുന്നതിനാൽ മാട്രിക്സ് രീതി തത്തുല്യമായ സമാവർത്തനത്തിന്റെ അത്ര തന്നെ കാര്യക്ഷമമാണെന്നു വരുന്നു.
യൂക്ലിഡിന്റെ പ്രമേയികയും അനന്യമായ ഘടകക്രിയയും
യൂക്ലിഡിന്റെ അൽഗൊരിതം പ്രയോഗിക്കുന്ന മിക്ക അവസരങ്ങളിലും ബെസു അനന്യത അത്യന്താപേക്ഷിതമാണ്.
പൂർണ്ണസംഖ്യകളെ അഭാജ്യസംഖ്യകളുടെ ഗുണനഫലമായി എഴുതുന്ന രീതി അനന്യമാണെന്ന അങ്കഗണിതത്തിലെ അടിസ്ഥാന സിദ്ധാന്തം ഇതിന്നുദാഹരണമാണ്.
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 1 , a 2 , …, a n എന്നിവയോടെല്ലാം സഹ-അഭാജ്യമാണെങ്കിൽ w അവയുടെ ഗുണനഫലമായ a 1 × a 2 × … × a n നോടും സഹ-അഭാജ്യമാണെന്നു വരുന്നു.
യൂക്ലിഡിന്റെ പ്രമേയിക ഉപയോഗിച്ച് ഏതൊരു പൂർണ്ണസംഖ്യയുടെയും ഘടകക്രിയ അനന്യമാണെന്ന് തെളിയിക്കാം.
ഇങ്ങനെയല്ല, L നെ m , n വീതം ഘടകങ്ങളുള്ള രണ്ട് രീതികളിൽ ഘടകക്രിയ ചെയ്യാം എന്ന് കരുതുക L = p 1 p 2 … p m = q 1 q 2 … q n .
p എന്ന ഓരോ അഭാജ്യസംഖ്യയും L ന്റെ ഘടകമായതിനാൽ അത് q ഘടകങ്ങളിലൊന്നിന്റെയും ഘടകമായിരിക്കണം.
എന്നാൽ q യും ഒരു അഭാജ്യസംഖ്യയായതുകൊണ്ട് p = q എന്ന് വരുന്നു.
ഇങ്ങനെ അഭാജ്യ ഘടകങ്ങളെയെല്ലാം ഓരോന്നോരോന്നായി ജോടികളാക്കിയ ശേഷം L ൽ നിന്ന് ഹരിച്ചെടുത്ത് ഈ പ്രക്രിയ തുടരുകയാണെങ്കിൽ ഘടകങ്ങളൊന്നും ബാക്കിയാവില്ലെന്നു കാണാം.
അതായത്, അഭാജ്യഘടകങ്ങളുടെ ക്രമത്തിൽ വ്യതാസമുണ്ടാകാമെന്നതൊഴിച്ചാൽ ഏതു സംഖ്യയെയും അഭാജ്യസംഖ്യകളായി ഘടകക്രിയ ചെയ്യുന്ന രീതി അനന്യമാണ്.
ഈ ഫലം ഗണിതത്തിലെ ഒട്ടേറെ തെളിവുകളിൽ പ്രധാന പങ്കു വഹിക്കുന്നു.
രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ 9 x + 12 y = 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 1 = s ( c / g ), y 1 = t ( c / g ).
സാധാരണ ഗതിയിൽ ഒരു രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യത്തിന്റെ പരിഹാരങ്ങളുടെ എണ്ണം പൂജ്യമോ അനന്തമോ ആണ്.
പരിഹാരങ്ങൾ അനന്തമാണെങ്കിൽ കണ്ടുപിടിക്കുന്നതെങ്ങനെയെന്നു നോക്കാം.
ഒരേ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യത്തിന്റെ നിർദ്ധാരണങ്ങളാണ് ( x 1 , y 1 ), ( x 2 , y 2 ) എന്നു കരുതുക.
അതായത്, ax 1 + by 1 = c = ax 2 + by 2
അഥവാ a ( x 1 − x 2 ) = b ( y 2 − y 1 ).
അതായത്, രണ്ട് പരിഹാരങ്ങളുടെ x വിലകൾക്കിടയിലുള്ള കുറഞ്ഞ വ്യത്യാസം b / g യും y വിലകൾക്കിടയിലുള്ള കുറഞ്ഞ വ്യത്യാസം a / g യുമാണ്.
അതായത്, സമവാക്യത്തിന്റെ നിർദ്ധാരണങ്ങളെ സാമാന്യരൂപത്തിൽ ഇങ്ങനെയെഴുതാം: x = x 1 − bu / g y = y 1 + au / g .
u വിന്റെ വില എല്ലാ പൂർണ്ണസംഖ്യകളുമെടുത്താൽ ( x 1 , y 1 ) എന്ന ഒറ്റ നിർദ്ധാരണത്തിൽ നിന്ന് അനന്തം എണ്ണം പരിഹാരങ്ങളെല്ലാം കണ്ടുപിടിക്കാം.
പരിഹാരത്തിലെ സംഖ്യകളെല്ലാം എണ്ണൽസംഖ്യകളാകണമെന്ന് നിഷ്കർഷിച്ചാൽ ( 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 −1 = a −1 a ≡ 1 mod m .
എന്ന സമവാക്യം അനുസരിക്കുന്ന a −1 എന്ന സംഖ്യയാണ്.
ax ≡ 1 mod m , എന്ന സർവ്വസമതയ്ക്ക് നിർദ്ധാരണം കാണുന്നതു വഴി ഈ സംഖ്യ കണ്ടുപിടിക്കാം.
ഇത് താഴെക്കൊടുത്തിരിക്കുന്ന രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യം നിർദ്ധരിക്കുന്നതിന് തുല്യമാണ് ax + my = 1.
ഈ സമവാക്യം മേൽ വിവരിച്ചതുപോലെ യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് നിർദ്ധരിക്കാം.
മൊഡ്യുലാർ ഗുണനവിപരീതങ്ങൾ കാണുന്നത് ഇകൊമേഴ്സിൽ വ്യാപകമായി ഉപയോഗിക്കുന്ന ആർ.എസ്.എ. അൽഗൊരിതത്തിന്റെ അവശ്യഭാഗമാണ്.
ക്ഷേത്രങ്ങൾക്കു പകരം വലയങ്ങളാണ് ആർ.എസ്.എ. അൽഗൊരിതത്തിൽ ഉപയോഗിക്കുന്നതെങ്കിലും വലയങ്ങളിലും (ഗുണനവിപരീതമുള്ള) അംഗങ്ങളുടെ ഗുണനവിപരീതം യൂക്ലിഡിന്റെ അൽഗൊരിതമുപയോഗിച്ച് കണ്ടുപിടിക്കാം.
വാർത്താവിനിമയത്തിൽ തെറ്റുകൾ തിരുത്താനുപയോഗിക്കുന്ന എറർ കറക്റ്റിങ് കോഡുകളിലും യൂക്ലിഡിന്റെ അൽഗൊരിതത്തിന് ഉപയോഗമുണ്ട്.
ഉദാഹരണമായി, ഗാൽവ ക്ഷേത്രങ്ങൾ ഉപയോഗിക്കുന്ന ബി.സി.എച്. കോഡ് , റീഡ്-സോളമൻ കോഡ് എന്നിവ ഡീകോഡ് ചെയ്യാൻ ബെർൽകാംപ്-മാസ്സേ അൽഗൊരിതത്തിനു പകരമായി ഇത് ഉപയോഗിക്കാം.
ചൈനീസ് ശിഷ്ട പ്രമേയം
ഒന്നിലേറെ രേഖീയ ഡയൊഫന്റൈൻ സമവാക്യങ്ങൾ നിർദ്ധരിക്കാനും യൂക്ലിഡിന്റെ അൽഗൊരിതം ഉപയോഗിക്കാം..
ഇത്തരം സമവാക്യങ്ങൾ ചൈനീസ് ശിഷ്ട പ്രമേയത്തിൽ (Chinese remainder theorem) കാണാം.
പൂർണ്ണസംഖ്യകളെ വിവരിക്കാനുള്ള ഒരു വ്യത്യസ്തമായ രീതിയാണിത്.