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

بزرگترین مقسوم علیه مشترک میان دو عدد صحیح a و b بصورت (a, b) یا (gcd (a, b نوشته می‌شود.

مثال: gcd (16, 24) = 8 و gcd (8, 9) = 1

برای محاسبه ب.م.م می‌توان هر دو عدد را به عوامل اول تجزیه کرد. ب.م.م برابر حاصل ضرب عوامل مشترک با توان کوچکتر می‌شود.

برای مثال: $18=2.3^2$ و $84=2^2.3.7$ پس $(84, 18)=2.3$gcd

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

• ب.م.م دو عدد a و ۰ برابر |a| است. |gcd(a, ۰)=|a.
• اگر m یک عدد صحیح باشد آنگاه داریم: (gcd(a + m.b, b) = gcd(a, b.

با توجه به این خاصیت‌ها هر بار باقیمانده‌ی تقسیم عدد بزرگ تر بر عدد کوچکتر را محاسبه می‌کنیم. اگر برابر صفر بود ب.م.م عدد کوچکتر است در غیر این صورت ب.م.م برابر ب.م.م عدد کوچکتر و باقیمانده‌ی تقسیم است.

مثال: یافتن (۸۴٬۱۸)gcd

ابتدا ۸۴ را به ۱۸ تقسیم می کنیم؛ خارج قسمت تقسیم ۴ و باقی‌مانده ۱۲ بدست می‌آید. سپس ۱۸ را بر ۱۲ تقسیم می کنیم؛ خارج قسمت ۱ و باقی‌مانده ۶ بدست می‌آید؛ مجدداً ۱۲ را بر ۶ تقسیم می‌کنیم؛ خارج قسمت ۲ و باقی‌مانده ۰ می‌شود. پس عدد ۶ ب.م.م دو عدد ۸۴ و ۱۸ است.

gcd.py

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

• به ازای دو عدد طبیعی a و b اگر a بزرگتر مساوی b باشد آنگاه a % b حداکثر نصف a خواهد بود.

بنابراین هر بار که یک عدد را با باقیمانده تقسیم آن بر عدد کوچکتر جایگزین می‌کنیم این عدد حداکثر نصف مقدار قبلی اش را می‌گیرد پس این الگوریتم دارای مرتبه زمانی $O(\log a + \log b)$ است.