حساب پیمانهای و همنهشتی؛ باقیمانده توانهای بزرگ
آموزش تعریف همنهشتی، قواعد جمع و ضرب، چرخه توانها و حل تستهای باقیمانده در نظریه اعداد.
پاسخ کوتاه
دو عدد نسبت به پیمانه m همنهشتاند اگر هنگام تقسیم بر m باقیمانده یکسان داشته باشند. این زبان اجازه میدهد عددهای بسیار بزرگ را با نمایندههای کوچکتر جایگزین کنیم و باقیمانده جمع، ضرب و توان را سریع به دست آوریم.
تعریف همنهشتی
رابطه a≡b (mod m) یعنی m تفاضل a-b را تقسیم میکند. برای نمونه 17≡2 (mod 5)، چون تفاضل 15 مضرب 5 است. هر عدد با باقیمانده استاندارد خود بین صفر و m-1 همنهشت است.
جمع و ضرب
اگر a≡b و c≡d نسبت به یک پیمانه باشند، آنگاه a+c≡b+d و ac≡bd است. میتوان بعد از هر عمل باقیمانده گرفت تا عددها کوچک بمانند. تفریق نیز مجاز است، اما باقیمانده منفی را بهتر است به نماینده نامنفی تبدیل کنیم.
توانها و چرخه
برای یافتن باقیمانده a^n، چند توان اول را پیمانهای حساب کن و دوره تکرار را پیدا کن. سپس n را بر طول دوره تقسیم کن. باقیمانده صفرِ تقسیم نمایانگر آخرین عضو چرخه است، نه لزوماً عضو اول.
تقسیم در پیمانه
حذف یک عامل مشترک از دو طرف همنهشتی همیشه مجاز نیست. اگر عامل با پیمانه نسبت به هم اول باشد، وارون پیمانهای دارد و میتوان آن را حذف کرد. در غیر این صورت تقسیم ممکن است بعضی جوابها را از بین ببرد یا پیمانه را تغییر دهد.
مثال و تست کوتاه
برای باقیمانده 3^100 بر 5، توانها چرخه 3، 4، 2، 1 با طول 4 دارند. چون 100 بر 4 بخشپذیر است، عضو چهارم چرخه انتخاب میشود و باقیمانده برابر 1 خواهد بود.
چکلیست حل تست
- همنهشتی یعنی تفاضل بر پیمانه بخشپذیر است.
- پس از هر جمع یا ضرب باقیمانده بگیر.
- تقسیم پیمانهای فقط با کنترل وارون مجاز است.