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

بروزرسانی شده در: 2:50 1404/06/26 مشاهده: 7 دسته بندی: کپسول آموزشی

بزرگ‌ترین مقسوم‌علیه مشترک (GCD)^[1]: کلید درک اشتراکات اعداد

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

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

مقسوم‌علیه و مقسوم‌علیه مشترک چیست؟

قبل از پرداختن به «بزرگترین» مقسوم‌علیه مشترک، باید با خودِ مفهوم «مقسوم‌علیه» آشنا شویم. مقسوم‌علیه^[2] یک عدد، عددی است که عدد اصلی بر آن به طور کامل و بدون باقیمانده تقسیم (بخش‌پذیر) می‌شود.

برای مثال، مقسوم‌علیه‌های عدد 18 را در نظر بگیرید:

18 ÷ 1 = 18 (پس ۱ مقسوم‌علیه است)
18 ÷ 2 = 9 (پس ۲ مقسوم‌علیه است)
18 ÷ 3 = 6 (پس ۳ مقسوم‌علیه است)
18 ÷ 6 = 3 (پس ۶ مقسوم‌علیه است)
18 ÷ 9 = 2 (پس ۹ مقسوم‌علیه است)
18 ÷ 18 = 1 (پس ۱۸ مقسوم‌علیه است)

پس مقسوم‌علیه‌های عدد 18 عبارت‌اند از: 1, 2, 3, 6, 9, 18.

حالا دو عدد 18 و 24 را با هم در نظر می‌گیریم. مقسوم‌علیه‌های 24 عبارت‌اند از: 1, 2, 3, 4, 6, 8, 12, 24.

مقسوم‌علیه‌های «مشترک» این دو عدد، یعنی اعدادی که در هر دو لیست وجود دارند، عبارت‌اند از: 1, 2, 3, 6.

بزرگترین عدد بین این مقسوم‌علیه‌های مشترک، عدد 6 است. بنابراین می‌گوییم بزرگترین مقسوم‌علیه مشترک (GCD) اعداد 18 و 24 برابر است با 6 که به صورت GCD(18, 24) = 6 نشان داده می‌شود.

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

برای پیدا کردن GCD دو یا چند عدد، روش‌های مختلفی وجود دارد که بسته به اندازهٔ اعداد و سطح پیچیدگی، می‌توان از آن‌ها استفاده کرد.

۱. روش فهرست کردن مقسوم‌علیه‌ها

این روش که در مثال قبل دیدیم، ساده‌ترین روش است. برای اعداد کوچک بسیار مناسب است.

مثال: GCD اعداد 12 و 30 را پیدا کنید.

مقسوم‌علیه‌های 12: 1, 2, 3, 4, 6, 12
مقسوم‌علیه‌های 30: 1, 2, 3, 5, 6, 10, 15, 30
مقسوم‌علیه‌های مشترک: 1, 2, 3, 6
بزرگترین آن‌ها: 6

پاسخ: GCD(12, 30) = 6

۲. روش تجزیه به عوامل اول^[3]

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

مثال: GCD اعداد 40 و 60 را با تجزیه پیدا کنید.

تجزیهٔ عوامل اول:

40 = 2 × 2 × 2 × 5 = 2³ × 5¹
60 = 2 × 2 × 3 × 5 = 2² × 3¹ × 5¹

عوامل مشترک با کمترین توان: 2² و 5¹.

حالا این عوامل را ضرب می‌کنیم: 2² × 5¹ = 4 × 5 = 20.

پاسخ: GCD(40, 60) = 20.

فرمول کلی: اگر دو عدد a و b را به صورت $a = p_1^{x_1} \times p_2^{x_2} \times ... \times p_n^{x_n}$ و $b = p_1^{y_1} \times p_2^{y_2} \times ... \times p_n^{y_n}$ تجزیه کرده باشیم، آنگاه: $GCD(a, b) = p_1^{\min(x_1, y_1)} \times p_2^{\min(x_2, y_2)} \times ... \times p_n^{\min(x_n, y_n)}$

۳. الگوریتم اقلیدس^[4] (برای سطوح پیش‌رفته‌تر)

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

قاعده: GCD دو عدد a و b با GCD عدد کوچک‌تر و باقیماندهٔ تقسیم عدد بزرگتر بر عدد کوچک‌تر برابر است. این فرآیند آنقدر تکرار می‌شود تا باقیمانده صفر شود. در آن مرحله، عدد کوچک‌تر (مقسوم‌علیه) همان GCD است.

مثال: GCD اعداد 270 و 192 را با الگوریتم اقلیدس پیدا کنید.

مرحله ۱: 270 ÷ 192 = 1 و باقیمانده 78 می‌شود.
پس GCD(270, 192) = GCD(192, 78)
مرحله ۲: 192 ÷ 78 = 2 و باقیمانده 36 می‌شود.
پس GCD(192, 78) = GCD(78, 36)
مرحله ۳: 78 ÷ 36 = 2 و باقیمانده 6 می‌شود.
پس GCD(78, 36) = GCD(36, 6)
مرحله ۴: 36 ÷ 6 = 6 و باقیمانده 0 می‌شود.
پس GCD(36, 6) = 6

چون باقیمانده صفر شد، جواب نهایی 6 است. پاسخ: GCD(270, 192) = 6.

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

کاربردهای GCD در دنیای واقعی و ریاضیات

شاید برایتان سؤال باشد که یادگیری GCD چه فایده‌ای دارد. کاربردهای آن بسیار گسترده است:

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

مثال: کسر $\frac{24}{36}$ را ساده کنید.
اول GCD(24, 36) را پیدا می‌کنیم که برابر 12 است.
سپس صورت و مخرج را بر 12 تقسیم می‌کنیم: $\frac{24 \div 12}{36 \div 12} = \frac{2}{3}$.
پس $\frac{24}{36}$ در ساده‌ترین شکل خود معادل $\frac{2}{3}$ است.

۲. تقسیم عادلانه: فرض کنید می‌خواهید 12 شکلات و 18 آبنبات را بین چندین نفر به طور کاملاً مساوی تقسیم کنید، به طوری که کوچکترین تعداد بسته‌ها را داشته باشید و هیچ شکلات یا آبنباتی اضافه نماند. GCD به شما کمک می‌کند.

GCD(12, 18) = 6. این یعنی می‌توانید همهٔ خوراکی‌ها را بین 6 نفر تقسیم کنید. هر نفر $12 \div 6 = 2$ شکلات و $18 \div 6 = 3$ آبنبات خواهد گرفت.

۳. الگوهای تکراری و کاشی‌کاری: اگر بخواهیم یک صفحه را با کاشی‌های مربعی شکل بدون برش بپوشانیم، اندازهٔ ضلع کاشی‌ها باید برابر با GCD طول و عرض آن صفحه باشد. این تضمین می‌کند که کاشی‌ها به طور کامل در صفحه جای می‌گیرند.

پرسش‌های متداول و اشتباهات رایج

سؤال: آیا GCD دو عدد اول همیشه ۱ است؟

بله، دقیقاً. زیرا اعداد اول فقط بر ۱ و خودشان بخش‌پذیر هستند. پس تنها مقسوم‌علیه مشترک بین هر دو عدد اول متفاوت، عدد ۱ خواهد بود. مثلاً GCD(7, 13) = 1.

سؤال: اگر یکی از اعداد بر دیگری بخش‌پذیر باشد، GCD چیست؟

در این حالت، عدد کوچک‌تر خودش بزرگترین مقسوم‌علیه مشترک است. مثلاً چون 15 بر 5 بخش‌پذیر است، GCD(5, 15) = 5.

سؤال: اشتباه رایج: آیا GCD همیشه یکی از دو عدد اصلی است؟

خیر. این یک اشتباه رایج است. GCD می‌تواند کوچکتر از هر دو عدد باشد. به مثال اول مقاله برگردید: GCD(18, 24) = 6. عدد 6 از هر دو عدد 18 و 24 کوچکتر است.

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

پاورقی

^[1] GCD: مخفف Greatest Common Divisor (بزرگترین مقسوم‌علیه مشترک).

^[2] Divisor (مقسوم‌علیه): به عددی که عدد دیگری بر آن بخش‌پذیر است گفته می‌شود.

^[3] Prime Factorization (تجزیه به عوامل اول): شکستن یک عدد به صورت حاصلضرب اعداد اول.

^[4] Euclidean Algorithm (الگوریتم اقلیدس): روشی کارآمد برای یافتن GCD که توسط ریاضیدان یونانی، اقلیدس، ابداع شد.

محاسبات با کسر

اطلاع از تغییرات در بسته‌های گاما

کاربر عزیز سلام!