ইউক্লিডীয় এলগরিদম দুটি স্বাভাবিক সংখ্যা "a" এবং "b" এর গরিষ্ঠ সাধারণ গুণনীয়ক (গসাগু) নির্ণয় করে। গরিষ্ঠ সাধারণ গুণনীয়ক "g" হল সেই বৃহত্তম সংখ্যা যা "a" এবং "b" উভয়কেই নিঃশেষে ভাগ করে (কোন অবশিষ্ট থাকে না)। গসাগুর কিছু প্রতিশব্দের মধ্যে আছে "গরিষ্ঠ সাধারণ উৎপাদক" (গসাউ), "গরিষ্ঠ সাধারণ ভাজক" (গসাভা) ইত্যাদি। গরিষ্ঠ সাধারণ ভাজককে অনেক সময় গসাগু("a", "b") অথবা, আরও সহজভাবে ("a", "b") - এভাবে লেখা হয়, যদিও আরও কিছু গাণিতিক প্রকাশে এ প্রতীকটি ব্যবহৃত হয়। 
যদি গসাগু("a", "b") = 1, তাহলে "a" এবং "b" কে সহমৌলিক সংখ্যা বলা হয়। যেমন, ৬ কিংবা ৩৫ কোনোটিই সহমৌলিক সংখ্যা নয়, কারণ তাদের উভয়েরই মৌলিক উৎপাদক রয়েছে: : ৬ = ২ × ৩ and ৩৫ = ৫ × ৭। তা সত্ত্বেও ৬ এবং ৩৫ সহমৌলিক। ১ ব্যতীত আর কোন স্বাভাবিক সংখ্যা ৬ ও ৩৫ কে বিভাজ্য করে না, কারণ তাদের কোণ সাধারণ উৎপাদক নেই।
ধরি, "g" = গসাগু("a", "b"). যেহেতু "a" এবং "b" উভয়েই "g" এর গুণিতক, তাদের এভাবে লেখা যেতে পারে "a" = "mg" এবং "b" = "ng", এবং এমন কোন বৃহত্তর সংখ্যা "G" > "g" নেই যার জন্যে এটি সত্য হতে পারে। তাই স্বাভাবিক সংখ্যা "m" এবং "n" অবশ্যই সহমৌলিক সংখ্যা, কারণ কোন সাধারণ উৎপাদক "m" এবং "n" কে ভাগ করলে তা "g" এর মান বৃহত্তর করবে. তাই, অন্য যেকোন সংখ্যা "c" যা "a" এবং "b" উভয়কেই ভাগ করে তা অবশ্যই "g"কেও বিভাজ্য করবে। তাই "a" এবং "b" এর গরিষ্ঠ সাধারণ উৎপাদক "g" হল তাদের এমন একটি সাধারণ উৎপাদক যা তাদের অন্য যে কোন সাধারণ উৎপাদক দ্বারা বিভাজ্য। 
ধরি, g = গসাগু(a, b). যেহেতু a এবং b উভয়েই g এর গুণিতক, তাদের এভাবে লেখা যেতে পারে a = mg এবং b = ng, এবং এমন কোন বৃহত্তর সংখ্যা G > g নেই যার জন্যে এটি সত্য হতে পারে। তাই স্বাভাবিক সংখ্যা m এবং n অবশ্যই সহমৌলিক সংখ্যা, কারণ কোন সাধারণ উৎপাদক m এবং n কে ভাগ করলে তা g এর মান বৃহত্তর করবে. তাই, অন্য যেকোন সংখ্যা c যা a এবং b উভয়কেই ভাগ করে তা অবশ্যই gকেও বিভাজ্য করবে। তাই a এবং b এর গরিষ্ঠ সাধারণ উৎপাদক g হল তাদের এমন একটি সাধারণ উৎপাদক যা তাদের অন্য যে কোন সাধারণ উৎপাদক দ্বারা বিভাজ্য।[৪]

গসাগু এভাবে দৃশ্যায়িত করা যেতে পারে। 
ধরা যাক একটি আয়তাকার ক্ষেত্র "a" বাই "b", এবং যেকোন সাধারণ উৎপাদক "c" যা "a" এবং "b" উভয়কেই নিঃশেষে ভাগ করে। ফলে আয়তটির বাহুগুলোকে "c" দৈর্ঘের বিভিন্ন অংশে ভাগ করা যেতে পারে, যা আয়তটিকে "c" দৈর্ঘ্যবিশিষ্ট বর্গাকার ছকে ভাগ করে। সর্বোচ্চ সাধারণ উৎপাদক "g" হল "c" এর সর্বোচ্চ মান যার জন্যে এরূপ বিভাজন সম্ভব। উদাহরণ হিসাবে বলা যায়, একটি ২৪-বাই-৬০ আয়তক্ষেত্রকে এ সব ভাগে ভাগ করা যেতে পারে: ১-bবাই-১ বর্গ, ২-বাই-২ বর্গ, ৩-বাই-৩ বর্গ, ৬-বাই-৬ বর্গ অথবা ১২-বাই-১২ বর্গ. তাই, ১২ হল ২৪ এবং ৬০ এর গসাগু। একটি ২৪-বাই-৬০ আয়তক্ষেত্রকে ১২-বাই-১২ বর্গাকার ক্ষেত্রে ভাগ করা চলে, যেখানে একটি ধারে দুটি বর্গ (২৪/১২ = ২) এবং অপর ধারে ৫ টি (৬০/১২ = ৫) বর্গ থাকে।

দুটি সংখ্যা "a" ও "b" এর গসাগুকে তাদের সাধারণ মৌলিক উৎপাদক দ্বারা সংজ্ঞায়িত করা যেতে পারে। উদাহরণস্বরূপ, ৪৬২ কে এভাবে উৎপাদকে বিশ্লেষিত করা যায়: ২ × ৩ × ৭ × ১১ এবং ১০৭১ কে ৩ × ৩ × ৭ × ১৭, ৪৬২ এবং ১০৭১ এর গসাগু হল ২১ = ৩ × ৭, যা তাদের সাধারণ উৎপাদকের গুণফল। যদি দুটি সংখ্যার কোন সাধারণ মৌলিক উৎপাদক না থাকে তখন তাদের গসাগু হয় ১—তারা সহমৌলিক হয়। ইউক্লিডীয় এলগরিদমের সুবিধাহল এখানে গসাগু নির্ণয় করার জন্যে উৎপাদক হিসেব করার প্রয়োজন পড়ে না। বড় বড় পূর্ণ সংখ্যার উৎপাদকে বিশ্লেষণ এতটাই কঠিন সমস্যা হিসেবে বিবেচিত যে অনেক আধুনিক ক্রিপ্টোগ্রাফি সিস্টেম এর ওপর ভিত্তি করে তৈরি করা।

গসাগুর আরও একটু সূক্ষ্ম সংজ্ঞা উচ্চতর গণিতে সহায়ক হয়, বিশেষ করে বলয় তত্ত্বে। দুটি সংখ্যা "a" ও "b" এর গরিষ্ঠ সাধারণ গুণনীয়ক "g" একই সাথে তাদের ক্ষুদ্রতম পূর্ণসাংখ্যিক গুণিতক, অর্থাৎ, "ua" + "vb" আকারের ক্ষুদ্রতম সংখ্যা যেখানে "u" এবং "v" হল পূর্ণসংখ্যা। এ থেকে বলা যায়, "a" এবং "b" এর সকল পূর্ণ সাংখ্যিক গুণিতকের সেট ("ua" + "vb" জাতীয় সকল সংখ্যা) "g" এর পূর্ণ সাংখ্যিক গুণিতকের সেটের সমান। আধুনিক গাণিতিক পরিভাষায়, "a" এবং "b" দ্বারা তৈরিকৃত আদর্শ হল "g" হতে উৎপন্ন প্রধান ধারণা। গসাগুর এই সংজ্ঞার সাথে অন্যান্য সংজ্ঞার সমতুল্যতার বর্ণনা নিম্নে প্রদত্ত হল।

তিন বা ততোধিক সংখ্যার গসাগু হল তাদের মধ্যে থাকা সাধারণ মৌলিক উৎপাদকের গুণফল, যা সংখ্যা গুলো জোড়ায় জোড়ায় নিয়ে প্রাপ্ত গসাগুর সমান।

গরিষ্ঠ সাধারণ গুণনীয়ক
বর্ণনা
পটভূমি
কার্যপদ্ধতি