المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:بزرگترین مقسوم علیه مشترک

بزرگ‌ترین مقسوم‌علیه مشترک

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

بزرگترین مقسوم علیه مشترک میان دو عدد صحیح 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

روش اقلیدسی (تقسیم متوالی)

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

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

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

خاصیت‌های ب.م.م

هر مقسوم علیه دو عدد a و b، مقسوم علیه (gcd(a, b نیز هست.
ب.م.م دو عدد a و ۰ برابر |a| است. |gcd(a, ۰)=|a.
اگر a مقسوم علیه b.c باشد و داشته باشیم gcd(a, b) = d آنگاه a/d مقسوم علیه c است.
اگر m یک عدد نامنفی باشد آنگاه داریم: (gcd(m.a, m.b) = m.gcd(a, b.
اگر m یک عدد صحیح باشد آنگاه داریم: (gcd(a + m.b, b) = gcd(a, b.
اگر m مقسوم علیه مشترک غیر صفر a و b باشد آنگاه داریم:$gcd(a/m, b/m) = gcd(a, b)/m
ب.م.م دارای خاصیت جابجایی است؛ (gcd(a, b) = gcd(b, a
ب.م.م دارای خاصیت شرکت‌پذیری است؛ (gcd(a, gcd(b, c)) = gcd(gcd(a, b), c
ب.م.م دو عدد a و b وقتی که هیچ کدام ۰ نباشند، تعریف می‌شود: کوچکترین عدد مثبت d بشکلی که بتوان به فرم d = a.p + b.q نوشت که در آن p و q اعداد صحیح هستند.

ابزار صفحه