ماشین‌حساب LCM – کوچکترین مضرب مشترک

چه چیزی LCM (Least Common Multiple) است؟

LCM (Least Common Multiple) دو یا چند عدد صحیح است که کوچکترین عدد صحیح است که به طور کامل توسط هر یک از این اعداد بخش پذیر است - بدون باقیمانده. به عبارت دیگر، آن عدد کوچکترین عدد است که تمام اعداد داده شده می توانند به طور کامل در آن تقسیم شوند.

برای مثال، عدد 4 و 6 را در نظر بگیرید. چند برابر 4: 4، 8، 12، 16، 20، 24 … چند برابر 6: 6، 12، 18، 24 … اولین عدد که در هر دو لیست ظاهر می شود 12 است، بنابراین LCM(4، 6) = 12.

LCM یکی از مفاهیم بنیادین در نظریه اعداد و حساب است. این مفهوم به طور نزدیکی با Greatest Common Divisor (GCD)، که همچنین به عنوان بزرگترین عاملی شناخته می شود، مرتبط است (GCF)، از طریق این هویت زیبا:

LCM(a، b) = |a × b| / GCD(a، b)

این رابطه اجازه می دهد تا ما LCM را با استفاده از الگوریتم اقلیدس برای GCD محاسبه کنیم که حتی برای اعداد صحیح بزرگ نیز در زمان لگاریتمی اجرا می شود. ما در این کالبکر از این روش استفاده می کنیم تا نتایج سریع و دقیق را برای هر دو عدد صحیح مثبت که وارد می کنید، ارائه دهیم.

LCM فقط برای اعداد صحیح تعریف شده است. برای دو عدد صحیح مثبت، LCM حداقل به اندازه بزرگتر از دو عدد است و حداکثر برابر با حاصل ضرب آنها است. اگر دو عدد هیچ عاملی مشترک دیگری جز 1 (آنها coprime هستند) ندارند، LCM(a، b) = a × b.

چگونه LCM را پیدا کنیم – سه روش توضیح داده شده

سه روش استاندارد برای محاسبه LCM دستی وجود دارد. درک هر روش، حس شمارش شما را افزایش می دهد و به شما کمک می کند تا برای هر مشکل خاصی، روش کارآمدترین روش را انتخاب کنید.

<h3>روش 1: فهرست کردن چند برابر</h3>
<p> چند برابر هر عدد را بنویسید تا اولین عدد را که در هر دو لیست پیدا کنید. این روش برای اعداد کوچک کار می کند اما برای اعداد بزرگ غیر عملی است.</p>
<p><strong>مثال: LCM(6، 8)</strong></p>
<ul>
    <li> چند برابر 6: 6، 12، 18، <strong>24</strong>، 30 …</li>
    <li> چند برابر 8: 8، 16، <strong>24</strong>، 32 …</li>
    <li> LCM(6، 8) = <strong>24</strong></li>
</ul>

<h3>روش 2: فاکتورهای اول</h3>
<p> هر عدد را به فاکتورهای اولش تجزیه کنید. سپس قدرت <em>بالاترین</em> هر فاکتور اول را که در هر تجزیه و تحلیل ظاهر می شود را با هم ضرب کنید.</p>
<p><strong>مثال: LCM(12، 18)</strong></p>
<ul>
    <li> 12 = 2² × 3¹</li>
    <li> 18 = 2¹ × 3²</li>
    <li> قدرت های بالاتر: 2² × 3² = 4 × 9 = <strong>36</strong></li>
    <li> LCM(12، 18) = <strong>36</strong></li>
</ul>

<h3>روش 3: استفاده از GCD (فعالترین)</h3>
<p> فرمول <strong>LCM(a، b) = (a × b) / GCD(a، b)</strong> را استفاده کنید. برای پیدا کردن GCD، از الگوریتم اقلیدس استفاده کنید: با جایگزین کردن بزرگتر عدد با باقیمانده هنگام تقسیم بزرگتر بر کوچک‌تر، تا زمانی که 0 را به دست آورده باشید.</p>
<p><strong>مثال: LCM(48، 36)</strong></p>
<ul>
    <li> GCD(48، 36): 48 = 1×36 + 12 → GCD(36، 12): 36 = 3×12 + 0 → GCD = 12</li>
    <li> LCM(48، 36) = (48 × 36) / 12 = 1728 / 12 = <strong>144</strong></li>
</ul>

<table>
    <thead><tr><th>روش</th><th>بهترین برای</th><th>سرعت</th></tr></thead>
    <tbody>
        <tr><td>فهرست چند برابر</td><td>عدد های کوچک (&lt;20)</td><td> کند برای اعداد بزرگ</td></tr>
        <tr><td>فاکتورهای اول</td><td>3+ اعداد، استفاده آموزشی</td><td>متوسط</td></tr>
        <tr><td>GCD / الگوریتم اقلیدس</td><td>هر اندازه اعداد، محاسبات</td><td> بسیار سریع (log n)</td></tr>
    </tbody>
</table>

جدول مرجع LCM – زوج های عدد متداول

جدول زیر LCM را برای زوج های عدد متداول نشان می دهد. از این جدول به عنوان یک مرجع سریع برای کار با مسائل ریاضی، برنامه ریزی یا حساب جبری استفاده کنید.

توجه کنید که الگوی این است که وقتی یک عدد به طور کامل به عدد دیگر بخش پذیر است (به عنوان مثال، 5 و 10)، LCM بزرگتر عدد است. وقتی دو عدد بدون عاملی مشترک هستند (همه عاملی مشترک ندارند)، LCM برابر با حاصل ضرب آنها است.

LCM سه یا بیشتر عدد

برای یافتن LCM سه یا بیشتر عدد، خاصیت همزمان LCM را به طور تکراری اعمال کنید:

LCM(a, b, c) = LCM(LCM(a, b), c)

این را می‌توانید به هر تعداد عدد گسترش دهید. برای مثال:

LCM(4, 6, 10)

1. LCM(4, 6) = 12
2. LCM(12, 10) = 60
3. LCM(4, 6, 10) = 60

Alternatively، از فاکتورهای اول همه اعداد همزمان استفاده کنید:

• 4 = 2²
• 6 = 2¹ × 3¹
• 10 = 2¹ × 5¹
• LCM = 2² × 3¹ × 5¹ = 4 × 3 × 5 = 60

تظاهرات واقعی LCM

LCM ممکن است به نظر برسد که یک مفهوم ریاضی انتزاعی است، اما در بسیاری از سناریوهای عملی در زندگی روزمره، مهندسی و برنامه‌ریزی ظاهر می‌شود.

<h3>اضافه و کسر تقسیم</h3>
<p>برای اضافه کردن تقسیمات با تقسیمات ناهمسان، باید ابتدا LCM از تقسیم کنندگان را پیدا کنید — که در واقع LCM تقسیم کنندگان است.</p>
<p>مثال: 1/4 + 1/6. LCM = LCM(4, 6) = 12. بنابراین: 3/12 + 2/12 = 5/12.</p>
<p>بدون LCM، حساب جبری تقسیمات به کارهای غیرضروری با اعداد بزرگتر نیاز دارد. LCM محاسبات را به سادگی ممکن می‌کند.</p>

<h3> برنامه‌ریزی و هماهنگی</h3>
<p>LCM به شما می‌گوید که وقایع چرخشی در چه زمانی هماهنگ می‌شوند. این در:</p>
<ul>
    <li><strong> برنامه‌ریزی قطار:</strong> اگر قطار A هر 12 دقیقه حرکت می‌کند و قطار B هر 8 دقیقه حرکت می‌کند، آنها هر LCM(12, 8) = 24 دقیقه هماهنگ می‌شوند.</li>
    <li><strong>سیستم‌های چرخشی:</strong> یک چرخی با 12 دندان با یک چرخی که 8 دندان دارد هر LCM(12, 8) = 24 چرخه چرخشی کوچک را برای هماهنگی دوباره نیاز دارد.</li>
    <li><strong>موسیقی و ریتم:</strong> یک الگوی ضربان 3 و یک الگوی ضربان 4 هر LCM(3, 4) = 12 ضربان را هماهنگ می‌کنند — اساس پلی‌ریتم در موسیقی.</li>
    <li><strong>چراغ‌های چشمک زن:</strong> دو چراغ ترافیک با چرخه‌های 30 ثانیه و 45 ثانیه هر LCM(30, 45) = 90 ثانیه همزمان چشمک می‌زنند.</li>
</ul>

<h3> رمزگشایی و حساب جبری مدولار</h3>
<p>در رمزگشایی RSA، کارمایکل توئنت فانکشن λ(n) با LCM مرتبط است. به طور خاص، λ(pq) = LCM(p−1, q−1) برای اعداد اول DISTINCT p و q است. این مقدار LCM برای محاسبه اکسپوننت‌های رمزگذاری و رمزگشایی در RSA استفاده می‌شود و LCM را به امنیت اینترنت مرتبط می‌کند.</p>

<h3> علوم کامپیوتر: هماهنگی حافظه</h3>
<p>آدرس‌های حافظه کامپیوتر باید اغلب چند برابر چندین اندازه کلمه (به عنوان مثال، 4 بایت یا 8 بایت) قرار بگیرند. هنگامی که ساختار حافظه مشترک را برای سازگاری با چندین نوع داده تخصیص می‌دهید، آدرس شروع به هماهنگی LCM از الزامات مورد نیاز می‌شود — تا از هزینه‌های ناخواسته دسترسی به حافظه غیر هماهنگ اجتناب شود.</p>

LCM در برابر GCD – تفاوت‌های کلیدی

LCM و GCD مفاهیم مکمل هستند که با هم ساختار چندگانه اعداد را درک می‌کنند. درک هر دو مفیدتر می‌شود.

همان‌طور که همیشه برای اعداد مثبت صادق است، رابطه کلیدی LCM(a,b) × GCD(a,b) = a × b وجود دارد. این بدان معنی است که اگر یکی از آنها را بدانید، دیگری را می‌توانید بدست آورید.

برای مثال: LCM(12, 18) = 36 و GCD(12, 18) = 6. چک کنید: 36 × 6 = 216 = 12 × 18. ✓

مورد خاص و شرایط مرزی

فهم شرایط مرزی LCM به جلوگیری از خطاهای رایج در محاسبات و برنامه‌نویسی کمک می‌کند.

• LCM(n, n) = n: هر عدد خود را به عنوان LCM خود دارد. LCM(7, 7) = 7.
• LCM(1, n) = n: 1 هر عدد را تقسیم می‌کند، بنابراین LCM(1, n) = n برای هر عدد صحیح مثبت n است.
• LCM از اعداد متوالی: LCM(n, n+1) = n(n+1) زیرا اعداد متوالی همیشه بدون спільی (GCD = 1) هستند.
• LCM با اعداد اول: اگر p اول باشد و p n را تقسیم نکند، سپس LCM(p, n) = p × n. اگر p n را تقسیم کند، سپس LCM(p, n) = n.
• LCM از توان‌های 2: LCM(2, 4, 8, 16) = 16 — بالاترین توان در مجموعه.
• اعداد منفی: LCM معمولاً برای اعداد صحیح مثبت تعریف می‌شود. برای ورودی‌های منفی، از مقادیر مطلق استفاده کنید: LCM(−4, 6) = LCM(4, 6) = 12.
• صفر: LCM(0, n) = 0 به صورت رسمی (زیرا صفر یک ضریب از هر عدد صحیح است).

LCM در ریاضیات دبیرستان

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

• دوره 4-5: چندین‌ها و فاکتورها؛ شناسایی LCM با فهرست چندین‌ها
• دوره 5-6: جمع و تفریق بخش‌ها با استفاده از LCD (= LCM از بخش‌ها)
• دوره 6-7: روش فاکتورهای اول برای LCM؛ رابطه با GCF
• دوره 8+: LCM در بخش‌های ریاضی؛ LCM چندجمله‌ای؛ کاربردهای حساب جبری

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

نمونه روش لاسته: LCM(24, 36)

  2 | 24  36
  2 | 12  18
  3 |  6   9
    |  2   3
LCM = 2 × 2 × 3 × 2 × 3 = 72
    

تایید: LCM(24, 36) = (24 × 36) / GCD(24, 36) = 864 / 12 = 72. ✓

LCM در برنامه‌نویسی و توسعه نرم‌افزار

LCM در وظایف برنامه‌نویسی، از طراحی الگوریتم تا برنامه‌ریزی سیستم، به طور مکرر ظاهر می‌شود. در ادامه، نحوه پیاده‌سازی و استفاده از آن در کد نشان داده شده است:

محاسبه LCM با استفاده از GCD (پایتون):

از math import gcd

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

# LCM چندین عدد:
از functools import reduce
def lcm_multiple(*nums):
    return reduce(lcm, nums)

# مثال‌ها:
print(lcm(12, 18))        # 36
print(lcm_multiple(4, 6, 10))  # 60

کاربردهای برنامه‌نویسی رایج:

• برنامه‌ریزی وظیفه: اگر وظیفه A در پس‌زمینه هر 15 ثانیه اجرا می‌شود و وظیفه B هر 20 ثانیه اجرا می‌شود، آن‌ها هر LCM(15, 20) = 60 ثانیه هم‌زمان می‌شوند. LCM کمک می‌کند تا بازه‌های برنامه‌ریزی را برای اجتناب از تعارض منابع طراحی کنید.
• هماهنگ‌سازی آرایه: در حالیکه چندین آرایه با طول‌های مختلف همزمان پردازش می‌شوند (به عنوان مثال، صدا در 44,100 هرتز و ویدئو در 30 فریم در ثانیه)، طول چرخه LCM آن‌ها تعیین می‌کند که همه جریان‌ها دوباره هماهنگ شوند.
• تولید کلید رمزنگاری: در RSA، λ(n) = LCM(p−1, q−1) Carmichael's totient است — برای یافتن مقادیر رمزگذاری معتبر استفاده می‌شود.
• اعشار در کد: زبان‌های برنامه‌نویسی مانند پایتون (کلاس Fraction) و جاوا (BigInteger) از LCM برای حساب اعشار داخلی استفاده می‌کنند، تا نشان دهنده‌ها به اندازه ممکن کم شوند.

در پایتون 3.9+، math.lcm() به کتابخانه استاندارد اضافه شد، که پشتیبانی از چندین آرگومان را پشتیبانی می‌کند: math.lcm(4, 6, 10) 60 را بازگردانده است. قبل از 3.9، توسعه‌دهندگان از فرمول abs(a*b)//gcd(a,b) یا الگوریتم کاهش استفاده می‌کردند.

تمرین‌های LCM با پاسخ‌ها

با این تمرین‌ها، درک خود را با این تمرین‌ها آزمایش کنید، که هر یک از آنها یک سناریوی مختلفی را نشان می‌دهند که نیاز به محاسبه LCM است:

برای تأیید مشکل 5: 720 ÷ 36 = 20 ✓; 720 ÷ 48 = 15 ✓; 720 ÷ 60 = 12 ✓. همه سه عدد به طور کامل تقسیم می‌شوند. و 720 کوچک‌ترین عدد است (سعی کنید 360 را امتحان کنید: 360 ÷ 48 = 7.5 ✗). این انواع مشکل — برنامه‌ریزی، حساب اعشار و سیستم‌های دنده — سه کاربرد LCM واقعی در جهان را نشان می‌دهند که در آن‌ها با آن مواجه می‌شوید.

تمرین بیشتر: LCM(100, 75) = ؟ با استفاده از GCD: GCD(100, 75) = 25; LCM = (100×75)/25 = 7500/25 = 300. تأیید: 300÷100=3 ✓; 300÷75=4 ✓. روش GCD به طور قابل اعتماد سریع‌ترین روش برای هر جفت عدد است، بی‌توجه به اندازه. یک یادداشت نهایی در مورد کارایی: برای اعداد بسیار بزرگ (صد‌ها رقم)، حتی الگوریتم اقلیدس از گسترش GCD یا GCD دودویی برای کارایی استفاده می‌کند. پیاده‌سازی‌های بهینه C math.gcd() و math.lcm() از پایتون برای اعداد صحیح بزرگ بدون محدودیت کار می‌کنند — که چرا کالبکر آنلاین ما نیز بدون مشکل کارایی می‌تواند اعداد بزرگ را پردازش کند.