فهرست مندرجات

محاسبه‌ی تابع اویلر

تعریف

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

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

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

ویژگی‌ها

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

ویژگی اول بدیهی است، زیرا هر عدد طبیعی کوچک‌تر از 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}$$

مسائل نمونه

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

مراجع