"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 ആയതിനാൽ അവ സഹ-അഭാജ്യമാണ്.
"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" മാത്രം ജനകമായുള്ള ഗുണജത്തിന് തുല്യമാണ്. ഒറ്റ അംഗം ജനകമായുള്ള ഗുണജത്തെ പ്രിൻസിപൽ ഗുണജം എന്ന് വിളിക്കുന്നു. പൂർണ്ണസംഖ്യകളുടെ ഗുണജങ്ങളെല്ലാം തന്നെ പ്രിൻസിപൽ ആണ്. ഉസാഘയുടെ ചില ഗുണധർമ്മങ്ങൾ തെളിയിക്കാൻ ഈ നിർവചനമാണ് കൂടുതൽ സഹായകമാവുക. ഉദാഹരണമായി, രണ്ട് സംഖ്യകളുടെ പൊതുഭാജകങ്ങളെല്ലാം അവയുടെ ഉസാഘയുടെ ഭാജകമായിരിക്കണമെന്നത് നിർവചനത്തിൽ നിന്ന് നേരിട്ട് നിരീക്ഷിക്കാം. ഈ നിർവചനങ്ങളുടെയെല്ലാം തുല്യത താഴെ തെളിയിക്കുന്നുണ്ട്.

മൂന്നോ അധികമോ സംഖ്യകളുടെ ഉസാഘ അവയുടെ പൊതുവായ അഭാജ്യഘടകങ്ങളുടെ ഗുണനഫലമാണ്. സംഖ്യകളെ ഈരണ്ടെണ്ണമായെടുത്ത് ഉസാഘ കണ്ടാലും മതി.. ഉദാഹരണമായി,
അതിനാൽ രണ്ട് സംഖ്യകളുടെ ഉസാഘ കണ്ടുപിടിക്കാനുതകുന്ന യൂക്ലിഡിന്റെ അൽഗൊരിതം രണ്ടിൽ കൂടുതൽ സംഖ്യകൾക്കു വേണ്ടിയും ഉപയോഗിക്കാം.

വിവരണം
വികസിത യൂക്ലിഡിയൻ അൽഗൊരിതം
പശ്ചാത്തലം: ഉത്തമ സാധാരണ ഘടകം
ഗണനപരമായ സങ്കീർണ്ണത