تابع فی اویلر

تابع فی اویلر یا $\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})$