الگوریتم اقلیدس

نمایش مراحل الگوریتم اقلیدس برای به دست آوردن ب.م.م. اعداد ۲۵۲ و ۱۰۵

الگوریتم اقلیدس یک الگوریتم برای محاسبهٔ بزرگ‌ترین مقسوم علیه مشترک (ب.م.م.) است که اولین بار توسط اقلیدس در کتاب اصول اقلیدس شرح داده شده است. در این روش، برای محاسبهٔ ب.م.م. دو عدد x و y که به صورت $gcd(x,y)$ نمایش داده می‌شود، چنین عمل می‌شود (فرض بر این است که x از y بزرگتر است، اگر چه در حالت برعکس نیز، صرفاً با تغییر نام x و y این روش قابل استفاده خواهد بود):

1. از x به اندازهٔ y کم کن، و مقدار جدید را به جای x جایگذاری کن
2. قدم بالا را آن قدر تکرار کن تا x از y کوچک‌تر شود
3. جای x و y را عوض کن و قدم‌ها بالا را تکرار کن، تا وقتی که مقدار x صفر شود؛ در این حالت، مقدار y برابر با ب.م.م. دو عدد x و y خواهد بود.

به عنوان نمونه، اگر x برابر ۷۰ و y برابر ۲۵ باشد، مراحل کار چنین خواهد بود:

ب.م.م.(۲۵و۷۰) ← ب.م.م.(۲۵و۴۵) ← ب.م.م.(۲۵و۲۰) ← ب.م.م.(۲۰و۲۵)
← ب.م.م.(۲۰و۵) ← ب.م.م.(۵و۲۰) ← ب.م.م.(۵و۱۵) ← ب.م.م.(۵و۱۰)
← ب.م.م.(۵و۵) ← ب.م.م.(۵و۰) ← ب.م.م. = ۵