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


===== تعریف =====

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

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

<code>
 φ(1) = 1
 φ(2) = 1
 φ(3) = 2
 φ(4) = 2
 φ(5) = 4 
</code>

===== ویژگی‌ها =====

سه ویژگی عمده‌ی تابع اویلر در زیر آمده است.
با استفاده از این ویژگی‌ها می‌توان تابع اویلر را برای هر عدد طبیعی محاسبه نمود.
  * اگر 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''
استفاده شده که بزرگ‌ترین مقسوم‌علیه مشترک دو عدد داده‌شده را به صورت بازگشتی محاسبه می‌کند.


<file python 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)
</file>

از آن‌جایی که تابع  ''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})$ محاسبه نمود.
 
<file python 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
</file>

===== کابردهای تابع اویلر =====

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


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

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

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

/* قضیه‌ی اویلر اغلب در مسائل کاربردی ظاهر می‌شود. به طور مثال مسئله‌ی [[معکوس یک عدد در همنهشتی]] را ببینید. */

===== مسائل نمونه =====

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

  * [[http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1120|UVA#10179: کسرهای ساده‌ی تحویل‌ناپذیر]]   [سطح: ساده]
  * [[http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1240|UVA#10299: نسبت‌ها]]   [سطح: ساده]
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2302|UVA#11327: شمارش اعداد گویا]]   [سطح: متوسط]
  * [[http://acm.timus.ru/problem.aspx?space=1&num=1673|TIMUS #1673: دعوت به آزمون]]   [سطح: مشکل]


===== مراجع =====

  * [[http://e-maxx.ru/algo/euler_function|تابع اویلر - سایت ماکزیمال]]
  * [[http://en.wikipedia.org/wiki/Euler%27s_totient_function|تابع اویلر - ویکی‌پدیا]]