গরিষ্ঠ সাধারণ গুণনীয়ক

দুই বা তার অধিক সংখ্যার গরিষ্ঠ সাধারণ গুণনীয়ক (গ.সা.গু.) হলো সেই বৃহত্তম সংখ্যা যাকে দিয়ে ওই সংখ্যাগুলোকে নিঃশেষে ভাগ করা যায়। (অর্থাৎ, ভাগ করার পর কোনো ভাগশেষ থাকে না।) কোনো ভগ্নাংশকে তার ক্ষুদ্রতম পদে প্রকাশ করার জন্য গ.সা.গু.-র প্রয়োজন হয়।
মানে এর ক্ষুদ্রতম রূপ হল । দুটি সংখ্যার গ.সা.গু. যদি ১ হয় তা হলে তাদেরকে সহমৌলিক সংখ্যা বলে, যেমন: ৯ এবং ২৮-এর গ.সা.গু. ১, তাই তারা সহমৌলিক। যেমন:
9)28(3
গ.সা.গু. মানে যেহেতু সবচেয়ে বড় সাধারণ উৎপাদক, তাই যেসব সংখ্যার গ.সা.গু. বের করতে হবে তাদের মৌলিক উৎপাদকগুলো (prime factor) জানা থাকলে, সেসব মৌলিক উৎপাদকগুলোর মধ্যে যেগুলো সবগুলো সংখ্যার জন্য সাধারণ (common) (অর্থাৎ, যেসকল মৌলিক উৎপাদক উভয় সংখ্যা বা ততোধিক সংখ্যায় বিদ্যমান) সেগুলোকে নিয়ে গুণ করলে ওই সংখ্যাগুলোর সবচেয়ে বড় সাধারণ উৎপাদক বা গ.সা.গু. পাওয়া যায়। উদাহরণ: ৪৮ এবং ১৮০ এর মৌলিক উৎপাদকগুলো হল,
এখানে ৪৮ এবং ১৮০-এর জন্য দুটি ২ এবং একটি ৩ সাধারণ (common) মৌলিক উৎপাদক (অর্থাৎ, যে মৌলিক উৎপাদক বা সংখ্যাগুলো উভয়েই বিদ্যমান), তা হলে ৪৮ এবং ১৮০-এর গ.সা.গু. হলো ।
নিচে ভেনচিত্রের মাধ্যমে উদাহরণটিকে আরও সুস্পষ্ট করে দেখানো হল:
যদি সংখ্যাগুলোর কোন মৌলিক সাধারণ উৎপাদক না থাকে, তবে তাদের গ.সা.গু. হবে ১।
গ.সা.গু. নির্ণয়ের জন্য মৌলিক উৎপাদক পদ্ধতির চেয়ে অনেক বেশি কার্যকর পদ্ধতি হলো গ্রিক গণিতবিদ ইউক্লিডের লিপিবদ্ধ করা ভাগ প্রক্রিয়ার এ পদ্ধতিটি। এটিকে ইউক্লিডের অ্যালগরিদম বলা হয়। এই অ্যালগরিদম বা প্রক্রিয়াটি এই পর্যবেক্ষণ থেকে এসেছে যে, দুটি সংখ্যা—formula_1, formula_2 (যেখানে formula_3)-এর গ.সা.গু. আর formula_4, formula_2-এর গ.সা.গু. একই হয়। যদি সংখ্যাগুলো যথাক্রমে ১৪৩ এবং ৭৭ হয় তাহলে, । অর্থাৎ দুটি সংখ্যার গ.সা.গু. সংখ্যা দুটির পরমদূরত্বকেও নিঃশেষে ভাগ করে এবং সংখ্যা দুটির পরমদূরত্ব ও তাদের ক্ষুদ্রতম সংখ্যার গ.সা.গু. মূল সংখ্যা দুটির গ.সা.গু. এর সমান। 
যদি এ পর্যবেক্ষণ সঠিক হয় তাহলে এই প্রক্রিয়াটি কিছু সংখ্যক বার পুনরাবৃত্তি করা হলে, মানে বড় সংখ্যাটি থেকে ছোট সংখ্যাটি বিয়োগ করে বিয়োগফল এবং ছোট সংখ্যাটি নিয়ে আবার একি কাজ করা হলে এক সময় বিয়োগফল এবং ছোট সংখ্যাটি সমান হয়ে যাবে, আর আমরা বুঝতে পারি দুটি সংখ্যা সমান হলে তাদের গরিষ্ঠ সাধারণ গুণনীয়ক হবে ওই সংখ্যাটিই। তাহলে অবশেষে আমরা মূল সংখ্যা দুটি এবং এই প্রক্রিয়ায় মধ্যবর্তী যতগুলো সংখ্যার জোড়া এসেছে তাদের সবার গ.সা.গু. পেয়ে যাবো। যেহেতু বারবার বিয়োগ করা মানে ভাগ করা তাই বিয়োগ না করে ছোট সংখ্যাটি দিয়ে বড় সংখ্যাটিকে ভাগ করে ভাগশেষ এবং ছোট সংখ্যাটি নিয়ে পুরো প্রক্রিয়াটিকে আরো দ্রুত শেষ করা সম্ভব। নিচে ভাগের মাধ্যমে ৩৬৩ এবং ১৪৩ এর গ.সা.গু নির্ণয়ের ধাপ গুলো দেখানো হল:
উপরের ছবিতে ভাগশেষগুলোকে ইংরেজি formula_6 এবং ভাগফলগুলোকে formula_7 দ্বারা চিহ্নিত করা হয়েছে।
বিধিসন্মত ভাবে ইউক্লিডের অ্যালগরিদমকে নিচের মতো করে বর্ণনা করা যায়:
এটাকে আবার এই ভাবেও লেখা যায়:
ইউক্লিডের অ্যালগরিদমকে দুটি পর্যায়ক্রমিক যুক্তির মাধ্যমে প্রমাণ করা সম্ভব।
formula_12 যে formula_1 এবং formula_2-এর গুণনীয়ক তা দেখানোর জন্য প্রথমে দেখানো হয় formula_12 তার আগের ভাগশেষ formula_34 এর গুণনীয়ক।
যেহেতু formula_35
সেহতু formula_12 অবশ্যই formula_34 এর গুণনীয়ক, অর্থাৎ formula_38
একই-ভাবে বলা যায় formula_12 অবশ্যই formula_40 এরও গুণনীয়ক কারণ, formula_41 এভাবে দেখানো যায় formula_12 সব গুলো formula_43 (formula_44 যেকোন ধনাত্মক সংখ্যা) এরই গুণনীয়ক। যেহেতু formula_1 এবং formula_2-কে formula_43 হিসেবে বলা করা যায় সেহেতু প্রমাণিত হলো formula_12 formula_1 এবং formula_2 দুটি সংখ্যাকেই নিঃশেষে ভাগ করে, অর্থাৎ formula_12 formula_1 এবং formula_2-এর একটি সাধারণ গুণনীয়ক, আর তাই formula_54 হতে হবে।
ধরা যাক a এবং b এর এটি সাধারণ গুননীয়ক হলো c সেক্ষেত্রে formula_56এবং formula_57(যেখানে d, e যেকোন সংখ্যা)।
তাহলে বলা যায়, c প্রথম ভাগশেষ formula_58 কে নিঃশেষে ভাগ করে কারণ, formula_59
একি ভাবে দেখানো যায় c সব formula_43 কেই নিঃশেষে ভাগ করে, যেমন formula_61
তাই প্রমাণিত হয়, c formula_12 কে নিঃশেষে ভাগ করে। যেহেতু formula_63 হতে পারে সেহেতু বলা যায় formula_17, formula_12 এর গুণনীয়ক। এর মানে formula_66 হতে হবে।
এই দুই সর্তকে যদি এক সাথে সত্যি হতে হয় তাহলে নিশ্চিত ভাবে বলা যায়, formula_67। অর্থাৎ ভাগ প্রক্রিয়ার সত্যতা প্রমাণিত হলো।