تابع اویلر، $\phi(n)$، برابر است با تعداد اعداد طبیعی کوچک‌تر یا مساوی n که نسبت به n اول‌اند.

مقدار این تابع به ازای اعداد ۱ تا ۵ به شرح زیر است.

 φ(1) = 1
 φ(2) = 1
 φ(3) = 2
 φ(4) = 2
 φ(5) = 4 

سه ویژگی عمده‌ی تابع اویلر در زیر آمده است. با استفاده از این ویژگی‌ها می‌توان تابع اویلر را برای هر عدد طبیعی محاسبه نمود.

• اگر p یک عدد اول باشد، آن‌گاه $\phi(p) = p - 1$.
• اگر p یک عدد اول و a یک عدد طبیعی باشد، آن‌گاه $\phi(p^a) = p^a - p^{a-1}$.
• اگر a و b نسبت به هم اول باشند، آن‌گاه $\phi(ab) = \phi(b) \times \phi(b)$.

ویژگی اول بدیهی است، زیرا هر عدد طبیعی کوچک‌تر از p نسبت به آن اول است. برای اثبات ویژگی دوم کافی است دقت کنیم که تنها اعدادی نسبت به $p^a$ اول‌ نیستند که مضربی از p باشند. چنین مضاربی که کوچک‌تر یا مساوی $p^a$ هستند عبارت‌‌اند از $p, 2p, 3p, \ldots, p^{a-1}p$ که تعداد آن‌ها برابر $p^a/p = p^{a-1}$ است. ویژگی سوم از قضیه‌ی باقی‌مانده‌ی چینی نتیجه می‌شود.

در ساده‌ترین روش، می‌توان با بررسی تمام اعداد طبیعی بین ۱ تا n، تعداد اعدادی که نسبت به n اول‌اند شمرد. در زیر برای بررسی اول بودن دو عدد نسبت به هم از تابع کمکی gcd استفاده شده که بزرگ‌ترین مقسوم‌علیه مشترک دو عدد داده‌شده را به صورت بازگشتی محاسبه می‌کند.

phi.py

def phi(n):
    res = 0
    for i in range(n):
        if gcd(i, n) == 1:
            res += 1
    return res
 
def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

از آن‌جایی که تابع gcd در زمان $O(\log n)$ اجرا می‌شود، الگوریتم بالا دارای مرتبه‌ی زمانی $O(n \log n)$ است.

می‌توان تابع اویلر را از طریق تجزیه به عوامل اول به صورت کاراتری محاسبه کرد.

با توجه به ویژگی‌هایی که در بالا ذکر شد، اگر $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$، که در آن $p_i$ها عومل اول $n$ هستند، آن‌گاه داریم:

$$\phi(n) = \phi(p_1^{a_1}) \times \phi(p_2^{a_2}) \times \cdots \times \phi(p_k^{a_k})$$

$$= (p_1^{a_1} - p_1^{a_1-1}) \times (p_2^{a_2} - p_2^{a_2-1}) \times \cdots \times (p_k^{a_k} - p_k^{a_k-1})$$

\[= n \prod_{i=1}^{k} \left(1 - {1 \over p_i} \right) \]

با استفاده از ایده‌ی فوق می‌توان تابع اویلر را به صورت زیر در زمان $O(\sqrt{n})$ محاسبه نمود.

phi.py

def phi(n):
    res = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n = n // i
            res -= res // i
        i += 1
    if n > 1:
        res -= res // n
    return res

معروف‌ترین و مهم‌ترین کاربرد تابع اویلر در قضیه‌ی اویلر است که به شکل زیر بیان می‌شود. اگر a و m نسبت به هم اول باشند، آن گاه:

$$a^{\phi(m)} \equiv 1 \pmod{m}$$

در حالت خاص وقتی m یک عدد اول است، قضیه‌ی اویلر به قضیه‌‌ی زیر تبدیل می‌شود که به عنون قضیه‌ی کوچک فرما شناخته می‌شود:

$$a^{m - 1} \equiv 1 \pmod{m}$$

در زیر فهرستی از مسائل نمونه را می‌بینید که حل آن‌ها نیازمند محاسبه‌ی تابع اویلر بوده، یا از قضیه‌ی اویلر استفاده می‌کنند.

• UVA#10179: کسرهای ساده‌ی تحویل‌ناپذیر [سطح: ساده]
• UVA#10299: نسبت‌ها [سطح: ساده]
• UVA#11327: شمارش اعداد گویا [سطح: متوسط]
• TIMUS #1673: دعوت به آزمون [سطح: مشکل]

• تابع اویلر - سایت ماکزیمال
• تابع اویلر - ویکی‌پدیا