الگوریتم اقلیدس: روشی گامبهگام برای محاسبه بزرگترین مقسومعلیه مشترک
الگوریتم اقلیدس چیست؟ (تقسیمهای پیاپی)
الگوریتم اقلیدس1 یک روش کارا برای پیدا کردن بزرگترین عددی است که دو عدد صحیح مثبت را بدون باقیمانده تقسیم میکند. این عدد در ریاضیات با نماد $ b.m.m (a, b) $ نشان داده میشود. زیبایی این الگوریتم در سادگی و تکرار شدن یک فرآیند مشخص است تا به نتیجه برسیم. این روش بر این اصل استوار است که بزرگترین مقسومعلیه مشترک دو عدد، با بزرگترین مقسومعلیه مشترک عدد کوچکتر و باقیمانده تقسیم عدد بزرگتر بر کوچکتر برابر است.
برای درک بهتر، فرض کنید میخواهیم ب.م.م دو عدد $ a $ و $ b $ (با شرط $ a \ge b $) را پیدا کنیم. طبق این الگوریتم، مراحل زیر را تکرار میکنیم:
گام ۲ اگر باقیمانده صفر باشد ($ r = 0 $)، آنگاه عدد کوچکتر ($ b $) همان ب.م.م است و کار تمام است.
گام ۳ اگر باقیمانده مخالف صفر باشد، دو عدد جدید $ b $ (عدد کوچکتر قبلی) و $ r $ (باقیمانده) را در نظر گرفته و به گام ۱ بازمیگردیم.
بهعنوان یک مثال علمی، بیایید ب.م.م دو عدد $ 252 $ و $ 105 $ را محاسبه کنیم:
- مرحله ۱: $ 252 \div 105 = 2 $ باقیمانده $ 42 $ (چون $ 2 \times 105 = 210 $ و $ 252 - 210 = 42 $).
- مرحله ۲: حالا ب.م.م ($ 105, 42 $) را حساب میکنیم: $ 105 \div 42 = 2 $ باقیمانده $ 21 $.
- مرحله ۳: حالا ب.م.م ($ 42, 21 $) را حساب میکنیم: $ 42 \div 21 = 2 $ باقیمانده $ 0 $.
با صفر شدن باقیمانده، عدد $ 21 $ بزرگترین مقسومعلیه مشترک اعداد $ 252 $ و $ 105 $ است.
کاربرد عملی: سادهسازی کسرها و مسئلههای روزمره
شاید در نگاه اول بهنظر برسد پیدا کردن ب.م.م فقط یک تمرین ریاضیست، اما این مفهوم و الگوریتم محاسبه آن کاربردهای فراوانی در زندگی روزمره و علوم کامپیوتر دارد. یکی از سادهترین کاربردهای آن، سادهسازی کسرها2 است. برای مثال، اگر بخواهیم کسر $ \frac{252}{105} $ را ساده کنیم، با تقسیم صورت و مخرج بر ب.م.م بهدستآمده ($ 21 $)، به کسر سادهشده $ \frac{12}{5} $ میرسیم.
فرض کنید میخواهید یک زمین مستطیلشکل به ابعاد $ 252 $ متر در $ 105 $ متر را به بزرگترین قطعات مربعشکل ممکن تقسیم کنید. اندازه ضلع هر قطعه برابر با ب.م.م این دو عدد، یعنی $ 21 $ متر خواهد بود. همچنین در علوم کامپیوتر، این الگوریتم پایهای برای الگوریتمهای رمزنگاری مانند RSA3 است که برای امنیت ارتباطات در اینترنت استفاده میشود.
مقایسه روشهای محاسبه ب.م.م
روشهای مختلفی برای محاسبه بزرگترین مقسومعلیه مشترک وجود دارد. در جدول زیر، دو روش رایج را با هم مقایسه کردهایم:
| ویژگی | روش تجزیه به عوامل اول | الگوریتم اقلیدس |
|---|---|---|
| روش کار | تجزیه هر دو عدد به عوامل اول و انتخاب عوامل مشترک با کوچکترین توان | تقسیمهای پیاپی و محاسبه باقیمانده تا رسیدن به صفر |
| سرعت برای اعداد بزرگ | کند (یافتن عوامل اول دشوار است) | بسیار سریع |
| پیچیدگی محاسباتی | $ O(\sqrt{n}) $ برای هر عدد | $ O(\log(min(a, b))) $ |
| ریسک خطای انسانی | بالا (بهدلیل فراموشی یک عامل) | پایین (رویهای مکانیکی و مرحلهای) |
چالشهای مفهومی
زیرا در هر مرحله، باقیمانده تقسیم از مقسومعلیه (عدد کوچکتر) کوچکتر است. بنابراین یک دنباله نزولی از اعداد صحیح نامنفی ایجاد میشود که به صفر ختم خواهد شد. این اصل، تضمین میکند که الگوریتم پس از تعداد محدودی مرحله پایان مییابد.
بزرگترین مقسومعلیه مشترک یک عدد با صفر، برابر با قدر مطلق آن عدد است، زیرا هر عددی میتواند صفر را تقسیم کند (چون $ a \times 0 = 0 $). بنابراین $ b.m.m(a, 0) = |a| $. الگوریتم اقلیدس نیز در اولین مرحله، با تقسیم $ a $ بر $ 0 $ مواجه میشود که تعریفنشده است، بنابراین این حالت را بهعنوان شرط اولیه در نظر میگیریم.
خیر. میتوان آن را برای یافتن ب.م.م چند عدد نیز بهکار برد. کافی است ابتدا ب.م.م دو عدد اول را محاسبه کنیم، سپس ب.م.م نتیجهی بهدستآمده با عدد سوم، و به همین ترتیب تا آخر. یعنی $ b.m.m(a, b, c) = b.m.m(b.m.m(a, b), c) $.
پاورقی
1 الگوریتم اقلیدس (Euclidean Algorithm): روشی برای محاسبه بزرگترین مقسومعلیه مشترک دو عدد با استفاده از تقسیمهای پیاپی.
2 کسر (Fraction): به معنای یک جزء از یک کل است که به صورت $ \frac{صورت}{مخرج} $ نمایش داده میشود.
3 آراسای (RSA): یکی از اولین و پرکاربردترین سیستمهای رمزنگاری کلید عمومی که امنیت آن مبتنی بر دشواری تجزیه اعداد بزرگ به عوامل اول است.
