تابع فی و قضیه اویلر؛ چرخه توان در پیمانه مرکب
آموزش محاسبه تابع فی اویلر، شرط نسبت اول و کاهش توانهای بزرگ در پیمانههای اول و مرکب.
پاسخ کوتاه
قضیه اویلر نسخه عمومیتر قضیه کوچک فرماست و برای پیمانه مرکب نیز چرخهای از توانها میسازد. اگر پایه با n نسبت اول باشد، توان φ(n) در پیمانه n همنهشت با یک است؛ پس محاسبه درست تابع فی و کنترل ب.م.م دو گام اصلی حلاند.
تعریف تابع فی
φ(n) تعداد عددهای صحیح از 1 تا n است که با n نسبت اولاند. برای عدد اول p داریم φ(p)=p-1. همچنین برای توان اول p^k، رابطه φ(p^k)=p^k-p^(k-1) برقرار است.
فرمول تجزیه اول
اگر n=∏p_i^a_i باشد، φ(n)=n∏(1-1/p_i). توان عاملهای اول در خود n حضور دارد، اما هر عامل متمایز فقط یک بار در حاصلضرب پرانتزها وارد میشود؛ پس ابتدا تجزیه کامل لازم است.
قضیه اویلر
اگر ب.م.م a و n برابر 1 باشد، a^φ(n)≡1 mod n. شرط نسبت اول ضروری است؛ برای پایه دارای عامل مشترک با پیمانه، کاهش خودکار توان بر φ(n) ممکن است پاسخ غلط تولید کند.
کاهش توان
توان بزرگ N را بر φ(n) تقسیم و باقیمانده r را پیدا کن. سپس a^N≡a^r mod n است، به شرط برقرار بودن نسبت اول. اگر r صفر باشد، نتیجه یک است و پیمانه نهایی همچنان n باقی میماند.
مثال حلشده
برای 7^100 در پیمانه 20، ب.م.م 7 و 20 برابر 1 و φ(20)=20(1-1/2)(1-1/5)=8 است. چون 100 در تقسیم بر 8 باقیمانده 4 دارد، 7^100≡7^4≡1 mod 20.
ارتباط با فرما
برای پیمانه اول p، تابع فی برابر p-1 میشود و قضیه اویلر دقیقاً به قضیه کوچک فرما میرسد. در تست، اگر پیمانه اول است از فرما و اگر مرکب ولی پایه نسبت اول است از فی اویلر استفاده کن.
چکلیست حل تست
- پیمانه را پیش از محاسبه فی تجزیه کن.
- نسبت اول بودن پایه و پیمانه شرط اصلی است.
- برای پیمانه اول، φ(p)=p-1 است.