خانه ویکی

تابع فی اویلر

تابع فی اویلر تعداد اعداد طبیعی در بازه $[1 , n]$ را که نسبت به $n$ اول هستند ، می شمارد . اگر $n$ یک عدد طبیعی مثبت باشد ، آنگاه $ \phi (n)$ برابر است با تعداد اعداد طبیعی مانند $k$ که $1 <= k <= n$ به طوری که $gcd(n , k) = 1$ باشد .(دقت کنید که فرض می کنیم ۱ نسبت به هر عدد دیگری اول است) راجع بهبزرگترین مقسوم علیه مشترکمیتوانید بخوانید.

محاسبه

در زیر ثابت می کنیم $ \phi(n) = n\prod\limits_{p|n}1-\frac{1}{p} $
طبق اصل شمول و عدم شمول اگر S را مجموعه زیر مجموعه های عوامل اول n بنامیم آنگاه:
$ \phi(n) = \sum\limits_{R \subset S}(-1)^{|R|}\frac{n}{\prod\limits_{p \in R}p} $
یک $n$ از سیگما فاکتور می گیریم:
$ \phi(n) = n\sum\limits_{R \subset S}(-1)^{|R|}\frac{1}{\prod\limits_{p \in R}p} $
و می دانیم
$ \sum\limits_{R \subset S}(-1)^{|R|}\frac{1}{\prod\limits_{p \in R}p} = \prod\limits_{p|n}1-\frac{1}{p} $
پس حکم مساله نتیجه گرفته شد.

پیاده سازی

این یک پیاده سازی با استفاده از تجزیه $n$ است در $O( \sqrt{n})$

int phi(int n) 
{
    int result = n;
    for (int i = 2; i * i <= n; i++) 
    {
        if(n % i == 0) 
        {
            while(n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if(n > 1)
        result -= result / n;
    return result;
}

کاربردهای قضیه اویلر

مهم ترین ویژگی در تابع فی اویلر در قضیه اویلر مطرح می شود و به این صورت است که اگر $a , m$ نسبت به هم اول باشند ، داریم : $a^{ \phi (m)} \equiv 1 \mod m$ در حالت به خصوصی که $m$ اول باشد قضیه اویلر تبدیل می شود به قضیه فرمای کوچک که می گوید : $a^{m - 1} \equiv 1 \mod m$ قضیه اویلر و تابع فی اویلر در جاهای زیادی کاربرد دارند به عنوان مثال برای محاسبه معکوس پیمانه ایی