الگوریتم اقلیدس؛ محاسبه سریع ب.م.م و ک.م.م
آموزش تقسیم متوالی اقلیدسی، یافتن بزرگترین مقسومعلیه مشترک، ک.م.م و کاربرد در مسائل نظریه اعداد.
پاسخ کوتاه
الگوریتم اقلیدس بدون تجزیه کامل عددهای بزرگ، ب.م.م را با چند تقسیم پیدا میکند. در هر مرحله، مقسومعلیه مرحله قبل جای عدد بزرگتر و باقیمانده جای عدد کوچکتر را میگیرد تا باقیمانده صفر شود.
اصل تقسیم اقلیدسی
برای اعداد صحیح a و b با b>0 میتوان نوشت a=bq+r که 0≤r<b است. مقسومعلیههای مشترک a و b دقیقاً با مقسومعلیههای مشترک b و r یکیاند؛ بنابراین gcd(a,b)=gcd(b,r).
تقسیمهای متوالی
عدد بزرگتر را بر کوچکتر تقسیم کن و باقیمانده را بنویس. سپس مقسومعلیه قبلی را بر باقیمانده تقسیم کن. این روند تا باقیمانده صفر ادامه مییابد و آخرین باقیمانده ناصفر همان ب.م.م است.
اعداد نسبت به هم اول
اگر ب.م.م دو عدد یک باشد، آنها نسبت به هم اولاند؛ لازم نیست خود اعداد اول باشند. در این حالت هیچ عامل اول مشترکی ندارند. دو عدد متوالی همیشه نسبت به هم اولاند، زیرا هر مقسومعلیه مشترک باید تفاضل یک را نیز تقسیم کند.
رابطه با ک.م.م
برای دو عدد صحیح مثبت a و b داریم gcd(a,b)×lcm(a,b)=ab. پس بعد از یافتن ب.م.م، ک.م.م از تقسیم حاصلضرب بر آن به دست میآید. استفاده از تقسیم پیش از ضرب، احتمال بزرگشدن عددها را کم میکند.
مثال و تست کوتاه
برای 252 و 105 مینویسیم 252=2×105+42، سپس 105=2×42+21 و در پایان 42=2×21+0. پس ب.م.م برابر 21 است. ک.م.م نیز 252×105/21 یعنی 1260 خواهد بود.
چکلیست حل تست
- آخرین باقیمانده ناصفر ب.م.م است.
- باقیمانده هر مرحله از مقسومعلیه کوچکتر است.
- حاصلضرب ب.م.م و ک.م.م برابر حاصلضرب دو عدد است.