الگوریتم اقلیدس؛
مقسوم‌علیه قبلی را با باقیمانده عوض کن

ب.م.م را پیش از الگوریتم معنا کن

بزرگ‌ترین مقسوم‌علیه مشترک، بزرگ‌ترین عدد مثبت است که هر دو عدد را تقسیم می‌کند. برای دو عدد غیرصفر نتیجه مثبت است. قرارداد حالت‌های شامل صفر را مطابق تعریف درس نگه دار.

عدد بزرگ‌تر را در سطر نخست قرار بده

تقسیم اقلیدسی را با بزرگ‌تر بر کوچک‌تر آغاز کن. اگر ترتیب داده‌ها برعکس است، آن‌ها را جابه‌جا کن؛ ب.م.م نسبت به ترتیب دو عدد تغییر نمی‌کند.

هر باقیمانده مقسوم‌علیه مرحلهٔ بعد است

در مرحلهٔ بعد، مقسوم‌علیه قبلی را بر باقیماندهٔ قبلی تقسیم کن. این روند تا باقیماندهٔ صفر ادامه می‌یابد. حذف یک سطر ممکن است بازگشت الگوریتم گسترده را دشوار کند.

آخرین باقیماندهٔ ناصفر را بردار

وقتی تقسیم بدون باقیمانده شد، مقسوم‌علیه همان سطر برابر آخرین باقیماندهٔ ناصفر و ب.م.م است. صفر پایانی خود پاسخ نیست.

نمونهٔ زنجیره

برای 252 و 105 داریم 252=2×105+42، سپس 105=2×42+21 و 42=2×21+0؛ پس ب.م.م برابر ۲۱ است.

برای الگوریتم گسترده، معادله‌ها را حل‌شده بنویس

هر باقیمانده را به شکل مقسوم منهای خارج‌قسمت در مقسوم‌علیه بازنویسی کن. از معادلهٔ آخرین باقیماندهٔ ناصفر شروع و با جایگذاری عقب‌گرد کن.

ترکیب خطی را مرحله‌به‌مرحله جمع کن

پس از هر جایگذاری، ضرایب دو عدد اصلی را مرتب کن تا در پایان d=ax+by به دست آید. علامت‌های منفی را حفظ کن؛ ضرایب ترکیب خطی الزاماً مثبت نیستند.

نمونهٔ بازگشت کوتاه

از مثال قبل، 21=105−2×42 و 42=252−2×105؛ پس 21=105−2(252−2×105)=5×105−2×252. جایگذاری مستقیم، درستی ترکیب را تأیید می‌کند.

نسبت به هم اول را از ب.م.م تشخیص بده

اگر ب.م.م دو عدد ۱ باشد، آن‌ها نسبت به هم اول‌اند؛ لازم نیست هر دو خودشان عدد اول باشند. این ویژگی در حذف پیمانه‌ای و یافتن وارون اهمیت دارد.

کنترل نهایی با دو تقسیم

ب.م.م باید هر دو عدد را بدون باقیمانده تقسیم کند و هیچ مقسوم‌علیه مشترک بزرگ‌تری نباشد. ترکیب خطی را نیز با ضرب ضرایب بازسازی کن. برای کاربرد پیمانه‌ای از هم‌نهشتی استفاده کن.