محاسبه بزرگترین مقسوم علیه مشترک (ب.م.م)

ابزار محاسبه بزرگترین مقسوم علیه مشترک (Greatest Common Factor)، ب.م.م را بین دو تا پانزده عدد مختلف محاسبه می‌کند. در ادامه مطلب، با روش‌های مختلف برای پیدا کردن بزرگترین مقسوم علیه مشترک، از جمله تجزیه به عوامل اول و الگوریتم اقلیدسی آشنا می‌شوید. کافی است اعداد خود را وارد محاسبه‌گر کیده و ببینید چگونه ابزار ما می‌تواند هنگام کار با اعداد بزرگ در وقت شما صرفه‌جویی کند.

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

بزرگ‌ترین مقسوم‌علیه مشترک (ب.م.م)، بزرگ‌ترین عدد صحیحی است که بین مجموعه‌ای از اعداد مشترک است. این مفهوم به نام‌های دیگری مانند بزرگ‌ترین مخرج مشترک (HCF) نیز شناخته می‌شود. این مفهوم در کاربردهای خاص ریاضیات مانند ساده‌سازی چندجمله‌ای‌ها که در آن نیاز به پیدا کردن عوامل مشترک است، اهمیت دارد. در ادامه، نحوه یافتن ب.م.م توضیح داده می‌شود.

چگونه بزرگ‌ترین مقسوم‌علیه مشترک را پیدا کنیم؟

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

1. استفاده از لیست ضریب‌ها
2. تجزیه به عوامل اول
3. الگوریتم اقلیدسی
4. الگوریتم دودویی (الگوریتم اشتاین)
5. استفاده از ویژگی‌های مختلف ب.م.م (مانند استفاده از کوچک‌ترین مضرب مشترک)

خبر خوب این است که می‌توانید با عملیات ساده ریاضی (بدون ریشه یا لگاریتم)، بزرگترین مقسوم علیه مشترک را محاسبه کنید! در بیشتر موارد، این عملیات شامل تفریق، ضرب یا تقسیم هستند.

یافتن ب.م.م با لیست ضریب‌ها

روش اصلی برای تخمین بزرگ‌ترین مقسوم‌علیه مشترک این است که تمام ضریب‌های اعداد داده شده را پیدا کنیم. ضریب‌ها در واقع اعدادی هستند که در هم ضرب می‌شوند تا مقدار اصلی را به دست آورند. به طور کلی، این عوامل می‌توانند مثبت یا منفی باشند، به عنوان مثال، 2 × 3 همان (-2) × (-3) است که هر دو برابر 6 هستند. از دیدگاه عملی، ما فقط عوامل مثبت را در نظر می‌گیریم. علاوه بر این، فقط اعداد صحیح مورد توجه قرار می‌گیرند؛ در غیر این صورت، می‌توان ترکیب بی‌نهایتی از کسرهای متمایز به عنوان عوامل یافت که در اینجا بی‌فایده است. با دانستن این نکته، بیایید بزرگ‌ترین مقسوم‌علیه مشترک اعداد 72 و 40 را تخمین بزنیم.

1. ضریب‌های 72 عبارتند از: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.
2. ضریب‌های 40 عبارتند از: 1, 2, 4, 5, 8, 10, 20, 40.
3. تمام عوامل مشترک را لیست می‌کنیم: 1, 2, 4, 8.
4. بزرگ‌ترین مقسوم‌علیه مشترک برابر است با 8، که بزرگ‌ترین مقدار از لیست بالا است.

یک مسدله  چاللشی‌تر را امتحان کنیم. می‌خواهیم پاسخ این سؤال را پیدا کنیم: «بزرگ‌ترین مقسوم‌علیه مشترک بین 33,264 و 35,640 چند است؟» تمام کاری که باید انجام دهیم این است که مراحل قبلی را تکرار کنیم:

1. مقسوم علیه‌های 33,264 عبارتند از: 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 18, 21, 22, 24, 27, 28, 33, 36, 42, 44, 48, 54, 56, 63, 66, 72, 77, 84, 88, 99, 108, 112, 126, 132, 144, 154, 168, 176, 189, 198, 216, 231, 252, 264, 297, 308, 336, 378, 396, 432, 462, 504, 528, 594, 616, 693, 756, 792, 924, 1008, 1188, 1232, 1386, 1512, 1584, 1848, 2079, 2376, 2772, 3024, 3696, 4158, 4752, 5544, 8316, 11,088, 16,632, 33,264.
2. مقسوم علیه‌های 35,640 عبارتند از: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 18, 20, 22, 24, 27, 30, 33, 36, 40, 44, 45, 54, 55, 60, 66, 72, 81, 88, 90, 99, 108, 110, 120, 132, 135, 162, 165, 180, 198, 216, 220, 264, 270, 297, 324, 330, 360, 396, 405, 440, 495, 540, 594, 648, 660, 792, 810, 891, 990, 1080, 1188, 1320, 1485, 1620, 1782, 1980, 2376, 2970, 3240, 3564, 3960, 4455, 5940, 7128, 8910, 11,880, 17,820, 35,640.
3. لیست تمام مقسوم‌علیه‌های مشترک: 1, 2, 3, 4, 6, 8, 9, 11, 12, 18, 22, 24, 27, 33, 36, 44, 54, 66, 72, 88, 99, 108, 132, 198, 216, 264, 297, 396, 594, 792, 1188, 2376.
4. نتیجه نهایی: 2376.

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

تجزیه به عوامل اول

روش دیگری که معمولاً برای محاسبه بزرگ‌ترین مقسوم‌علیه مشترک استفاده می‌شود، تجزیه به عوامل اول است. این روش تا حدی به روش ذکر شده در بالا مرتبط است. به جای لیست کردن تمام عوامل ممکن، فقط عواملی که اعداد اول هستند را پیدا می‌کنیم. در نتیجه، حاصل‌ضرب تمام اعداد اول مشترک پاسخ مسئله ما خواهد بود. نکته مهم این است که همیشه فقط یک راه منحصر به فرد برای تجزیه هر عدد به عوامل اول وجود دارد. حالا بیایید بزرگ‌ترین مقسوم‌علیه مشترک 72 و 40 را با استفاده از تجزیه به عوامل اول پیدا کنیم:

1. عوامل اول 72 عبارتند از: 2, 2, 2, 3, 3.
2. عوامل اول 40 عبارتند از: 2, 2, 2, 5.
3. به عبارت دیگر، می‌توانیم بنویسیم: 72 = 2 × 2 × 2 × 3 × 3 و 40 = 2 × 2 × 2 × 5.
4. بخش مشترک در هر دو مورد عبارت است از: 2 × 2 × 2 = 8، که همان بزرگ‌ترین مقسوم‌علیه مشترک است.

می‌بینیم که برای این مثال ساده، نتیجه با روش قبلی سازگار است. حالا ببینیم آیا این روش برای یک مثال پیچیده‌تر نیز به خوبی کار می‌کند یا خیر. با روش تجزیه به عوامل اول، بزرگ‌ترین مقسوم‌علیه مشترک 33,264 و 35,640 چیست؟

1. عوامل اول 33,264 عبارتند از: 2, 2, 2, 2, 3, 3, 3, 7, 11.
2. عوامل اول 35,640 عبارتند از: 2, 2, 2, 3, 3, 3, 3, 5, 11.
3. با استفاده از نماد توان، می‌توانیم حاصل‌ضرب‌ها را به صورت زیر بنویسیم: 33,264 = 2⁴ × 3³ × 7 × 11، 35,640 = 2³ × 3⁴ × 5 × 11.
4. حاصل‌ضرب مشترک این دو عدد برابر است با: 2³ × 3³ × 11. همچنین می‌توان آن را به صورت فشرده‌تر و پیچیده‌تر با در نظر گرفتن فاکتوریل‌ها نوشت: (3!)³ × 11. ببینید ابزار ب.م.م ما نیز همین نتیجه یعنی 2376، را به شما می‌دهد.

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

ایده‌ای که اساس الگوریتم اقلیدسی را تشکیل می‌دهد، بیان می‌کند که اگر عدد k بزرگ‌ترین مقسوم‌علیه مشترک اعداد A و B باشد، آنگاه k همچنین ب.م.م برای تفاضل این اعداد A - B است. با دنبال کردن این روش، در نهایت به عدد 0 می‌رسیم. نتیجه این است که بزرگ‌ترین مقسوم‌علیه مشترک همان آخرین عدد غیرصفر است. بیایید یک بار دیگر به مثال‌های خود نگاه کنیم، اعداد 40 و 72. هر بار که تفریق انجام می‌دهیم، دو عدد را با ترتیب از بزرگ‌ترین به کوچک‌ترین مقایسه می‌کنیم:

• ب.م.م اعداد 72 و 40: تفاضل 72 - 40 برابر است با 32،
• ب.م.م اعداد 40 و 32: 40 - 32 = 8،
• ب.م.م اعداد 32 و 8: 32 - 8 = 24،
• ب.م.م اعداد 24 و 8: 24 - 8 = 16،
• ب.م.م اعداد 16 و 8: 16 - 8 = 8،
• ب.م.م اعداد 8 و 8: 8 - 8 = 0 توقف!

در آخرین مرحله، از تفریق به عدد 0 می‌رسیم. به این معنی که بزرگ‌ترین مقسوم‌علیه مشترک خود را پیدا کرده‌ایم و مقدار آن در خط ماقبل آخر تفریق‌ها برابر با 8 است.

حالا بیایید یک مثال پیچیده‌تر با اعداد 33,264 و 35,640 را بررسی کرده و سعی کنیم با استفاده از الگوریتم اقلیدسی آن را حل کنیم:

• ب.م.م اعداد 35,640 و 33,264: 35,640 - 33,264 = 2376،
• ب.م.م اعداد 33,264 و 2376: 33,264 - 2376 = 30,888،
• ب.م.م اعداد 30,888 و 2376: 30,888 - 2376 = 28,512،
• ب.م.م اعداد 28,512 و 2376: 28,512 - 2376 = 26,136،
• ب.م.م اعداد 26,136 و 2376: 26,136 - 2376 = 23,760،
• ب.م.م اعداد 23,760 و 2376: 23,760 - 2376 = 21,384،
• ب.م.م اعداد 21,384 و 2376: 21,384 - 2376 = 19,008،
• ب.م.م اعداد 19,008 و 2376: 19,008 - 2376 = 16,632،
• ب.م.م اعداد 16,632 و 2376: 16,632 - 2376 = 14,256،
• ب.م.م اعداد 14,256 و 2376: 14,256 - 2376 = 11,880،
• ب.م.م اعداد 11,880 و 2376: 11,880 - 2376 = 9504،
• ب.م.م اعداد 9504 و 2376: 9504 - 2376 = 7128،
• ب.م.م اعداد 7128 و 2376: 7128 - 2376 = 4752،
• ب.م.م اعداد 4752 و 2376: 4752 - 2376 = 2376،
• ب.م.م اعداد 2376 و 2376: 2376 - 2376 = 0 توقف!

مشابه مثال قبلی، بزرگ‌ترین مقسوم‌علیه مشترک اعداد 33,264 و 35,640 آخرین تفریق غیرصفر در این روش است که برابر با 2376 است.

ویژگی‌های ب.م.م

تا به حال چندین ویژگی از بزرگ‌ترین مقسوم‌علیه مشترک را معرفی کرده‌ایم. در این بخش، مهم‌ترین آن‌ها را فهرست می‌کنیم:

• اگر نسبت دو عدد a و b (a > b) یک عدد صحیح باشد، آنگاه gcf(a, b) = b.
• gcf(a, 0) = a، که در الگوریتم اقلیدسی استفاده می‌شود.
• gcf(a, 1) = 1.
• اگر a و b مقسوم‌علیه مشترکی نداشته باشند (نسبت به هم اول باشند)، آنگاه gcf(a, b) = 1.
• تمام مقسوم‌علیه‌های مشترک a و b همچنین مقسوم‌علیه‌های gcf(a,b) هستند.
• اگر b × c / a یک عدد صحیح باشد و gcf(a, b) = d، آنگاه a × c / d نیز یک عدد صحیح است.
• برای هر عدد صحیح k: gcf(k×a, k×b) = k × gcf(a, b)، که در الگوریتم دودویی استفاده می‌شود.
• برای هر عدد صحیح مثبت k: gcf(a/k, b/k) = gcf(a, b) / k.
• gcf(a, b) × lcm(a, b) = |a×b|.
• gcf(a, lcm(b, c)) = lcm(gcf(a, b), gcf(a, c)).
• lcm(a, gcf(b, c)) = gcf(lcm(a, b), lcm(a, c)).