تابع فی اویلر

از shaazzz
پرش به ناوبری پرش به جستجو

تابع فی اویلر تعداد اعداد طبیعی در بازه را که نسبت به اول هستند ، می شمارد . اگر یک عدد طبیعی مثبت باشد ، آنگاه برابر است با تعداد اعداد طبیعی مانند که به طوری که باشد .(دقت کنید که ۱ نسبت به هر عدد دیگری اول است)

محاسبه[ویرایش]

در زیر ثابت می کنیم

طبق اصل شمول و عدم شمول اگر را مجموعه زیر مجموعه های عوامل اول بنامیم آنگاه:

یک از سیگما فاکتور می گیریم:

و می دانیم

پس حکم مساله نتیجه گرفته شد.

پیاده سازی[ویرایش]

این یک پیاده سازی با استفاده از تجزیه است در

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;
}

کاربردهای تابع فی اویلر[ویرایش]

مهم ترین ویژگی در تابع فی اویلر در قضیه اویلر مطرح می شود و به این صورت است که اگر نسبت به هم اول باشند ، داریم : در حالت به خصوصی که اول باشد قضیه اویلر تبدیل می شود به قضیه کوچک فرما که می گوید : قضیه اویلر و تابع فی اویلر در جاهای زیادی کاربرد دارند به عنوان مثال برای محاسبه معکوس پیمانه ای

مسائل تمرینی[ویرایش]