تابع فی اویلر

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

تابع فی اویلر یا \varphi(n) تابعی است که تعداد اعداد هم‌اول با n و کوچکتر از آن را می‌شمارد. به طور مثال \varphi(9)=6 می‌باشد، زیرا اعداد ۱، ۲، ۴، ۵، ۷ و ۸ نسبت به ۹ اول هستند. اگر p_i نمایان‌گر اعداد اول باشد، برای محاسبه‌ی تابع \varphi(n) از قوانین زیر استفاده می‌کنیم:

  • برای هر عدد اول p_i داریم: \varphi(p_i)=p_i-1
  • برای هر عددی که به صورت p_i^k نوشته می‌شود داریم: \varphi(n)= p_i^k - p_i^{k-1}
  • و اگر n به صورت n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r} تجزیه شود داریم:
\varphi(n)=\varphi(p_1^{k_1})\varphi(p_2^{k_2})\cdots \varphi(p_r^{k_r})