قضیه کوچک فرما؛ باقیمانده توانهای بزرگ در تست
آموزش شرط اولبودن پیمانه، کاهش توان با قضیه کوچک فرما و محاسبه باقیمانده توانهای بزرگ بدون بسط.
پاسخ کوتاه
قضیه کوچک فرما چرخه توانها را در پیمانه اول کوتاه میکند. اگر p عددی اول و a بر p بخشپذیر نباشد، آنگاه a^(p-1) با 1 همنهشت است؛ بنابراین توان بسیار بزرگ را میتوان به باقیمانده تقسیم آن بر p-1 کاهش داد.
بیان دقیق قضیه
برای عدد اول p و عدد صحیح a که ب.م.م آن با p برابر 1 است، a^(p-1)≡1 mod p. شکل دیگر میگوید a^p≡a mod p و برای همه عددهای صحیح a معتبر است، حتی وقتی a مضرب p باشد.
کنترل شرطها
پیش از استفاده باید اولبودن پیمانه و نداشتن عامل مشترک پایه با آن را بررسی کنی. برای پیمانه مرکب، رابطه با توان p-1 الزاماً درست نیست؛ در آن حالت چرخه مستقیم، تابع فی اویلر یا تجزیه پیمانه ممکن است مناسب باشد.
کاهش توان
توان n را به صورت n=q(p-1)+r بنویس. سپس a^n=[a^(p-1)]^q a^r≡a^r mod p میشود. اگر r صفر باشد، باقیمانده 1 است؛ مگر آنکه پایه بر p بخشپذیر باشد که باید جدا بررسی شود.
مثال حلشده
برای باقیمانده 3^100 بر 7، چون 7 اول و ب.م.م 3 و 7 برابر 1 است، 3^6≡1. عدد 100 در تقسیم بر 6 باقیمانده 4 دارد، پس 3^100≡3^4=81≡4 mod 7.
ترکیب با همنهشتی پایه
پایه را نیز پیش از توانرسانی به باقیمانده کوچکتر تبدیل کن. مثلاً 20^50 mod 7 همان 6^50 یا (-1)^50 است و مستقیم باقیمانده 1 میدهد؛ این راه از اجرای کامل قضیه هم کوتاهتر است.
دام تستی
از a^(p-1)≡1 نمیتوان در حالت a مضرب p استفاده کرد. همچنین کاهش توان بر پیمانه p-1 مربوط به توانِ پایههای مجاز است، نه اینکه خود عدد a^n را بر p-1 محاسبه کنیم؛ پیمانه نهایی همچنان p باقی میماند.
چکلیست حل تست
- اولبودن پیمانه و ب.م.م پایه را کنترل کن.
- توان را بر p-1 کاهش بده، اما پیمانه نهایی p است.
- گاهی تبدیل پایه به منفی یک سریعترین راه است.