تابع فی اویلر کیست؟ توضیح بده.
در نظریه اعداد تابع فی اویلر یا formula_1 تابعی است که تعداد اعداد طبیعی کوچکتر مساوی "n" که نسبت به "n" اول اند را می‌شمارد. اگر "n" یک عدد طبیعی مثبت باشد، آنگاه formula_1 برابر است با تعداد اعداد طبیعی "k" در بازه ۱ تا n به‌طوری‌که بزرگترین مقسوم‌علیه مشترک (ب.م.م) n و k برابر ۱ باشد.تابع فی اویلر یک تابع ضربی است، بدین معنی که اگر دو عدد "m" و "n" نسبت به هم اول باشند آنگاه formula_3.برای مثلاً (۹)φ برابر ۶ است. زیرا اعداد ۱، ۲، ۴، ۵، ۷ و ۸ نسبت به ۹ اول هستند.تابع فی اویلر نقش کلیدی در تعریف سیستم رمزنگاری RSA دارد.تاریخچه و نمادگذاری.لئونارد اولر این تابع را در سال ۱۷۶۳ معرفی کرد. در آن زمان او هنوز نماد خاصی برای این تابع تعیین نکرده بود. بعدها لئونارد اویلر با مطالعه بیشتر تابع فی، حرف یونانی π را برای آن برگزید. نماد استاندارد φ بعدها توسط گاوس استفاده شده‌است.محاسبه مقدار تابع فی.چندین راه برای محاسبه این فرمول وجود دارد.فرمول ضرب اویلر.این تابع بیان می‌کند کهکه در آن formula_5 یک عدد اول است به‌طوری‌که formula_6 بر formula_5 بخش پذیر است.تبدیل فوریه.مقدار تابع فی برابر است با مقدار تبدیل فوریه گسسته ب.م.م در ۱:مقدار حقیقی این فرمول برابر است با:توجه کنید که برخلاف دو فرمول دیگر در این فرمول نیازی به دانستن عوامل اول n نیست. اما چون فرمول شامل محاسبه ب.م.م n و همه اعداد مثبت کمتر از n است در نهایت به تجزیه n نیاز خواهیم داشت.جمع مقسوم علیه‌ها.فرمول کلاسیک اویلراین فرمول به روش‌های مختلف قابل اثبات است.تابع زتای ریمان.برای n&gt;1 می‌توان تابع فی را به عنوان یک حد تابع زتای ریمان محاسبه کردکه در این فرمولformula_12تابع زتای ریمان است،formula_13تابع موبیوس است،formula_14عدد نپر است،و d مقسوم علیه است.چند مقدار تابع.۹۹ مقدار اولیه این تابع در جدول و نمودار زیر قابل مشاهده است.خط y = n-1 یک کران بالا برای تابع است و زمانی رخ می‌دهد که n اول باشد.قضیه اویلر.بیان می‌کند: اگر n و a نسبت به هم اول باشند آنگاهدر حالت خاصی که n عدد اول باشد این قضیه به قضیه کوچک فرما معروف است.این قضیه از قضیه لاگرانژ نتیجه می‌شود.سیستم رمزنگاری RSA بر روی همین قضیه بنا شده است: بیان می‌کنید که معکوس تابع formula_16 در واقع همان تابع formula_17 است که e معکوس ضربی d به پیمانه formula_1 است.دیگر فرمول‌های مرتبط با formula_1.نسبت طلایی.اشنایدر دو رابطه پیدا کرد که نسبت طلایی و تابع فی و تابع موبیوس را به هم مرتبط می‌کرد.در فرمول‌های زیر formula_32 نسبت طلایی است.این روابط به صورت زیر هستند:formula_33واز کم کردن این دو نتیجه می‌شودبا اعمال تابع نمایی به هر دو طرف رابطه به یک رابطه برای عدد نپر می‌رسیماثبات بر پایه دو فرمول زیر است:توابع مولد.سری دیریکله برای تابع فی را می‌توان بر حسب جملات تابع زتای ریمان به صورت زیر نوشتهمچنین تابع مولد سری لامبرت به صورت زیر استکه در ان اندازه q کمتر از ۱ است.هر دو روابط بالا با استفاده ضرب سری‌های پایه و با استفاده از فرمول‌های محاسبه تابع فی قابل اثبات هستند.نسبت دو جمله متوالی.در سال ۱۹۵۰ سومایاجولو اثبات کردوکاربرد.رمزنگاری RSA.در سیستم RSA ابتدا دو عدد اول بزرگ p و q را انتخاب می‌کنیم. سپس مقادیر n=pq و k=formula_1 را محاسبه می‌کنیم؛ و دوعدد e و d را پیدا می‌کنیم به‌طوری‌که ed به پیمانه k برابر ۱ باشد. n و e به عنوان کلید عمومی اعلان می‌شوند و n و d به عنوان کلید خصوصی مخفی نگاه داشته می‌شود.یک پیام مانند عدد مثبت m به صورت S = me mod n رمزگذاری می‌شود.برای رمزگشایی مقدار t = Sd mod n محاسبه می‌شود. قضیه اویلر نشان می‌دهد که اگر t کمتر از n باشد آنگاه t=m.سیستم RSA به خطر خواهد افتاد اگر بتوانیم عدد n را تجزیه کنیم یا بتوانیم مقدار تابع فی را بدون تجزیه n بدست بیاوریم.مسئله‌های حل نشده.حدس لیمر.اگر p اول باشد آنگاه formula_44. لیمر در سال ۱۹۳۲ سؤال زیر را مطرح کرد:آیا عدد مرکب n وجود دارد به‌طوری‌که formula_45؟در سال ۱۹۳۳ لیمر اثبات کرد که اگر n وجود داشته باشد آنگاه حتماً باید فرد باشد و باید حداقل ۷ عامل اول داشته باشد. در سال ۱۹۸۰ کوهن و هاگیس اثبات کردند که n&gt;1020 و باید حداقل ۱۴ عامل اول داشته باشد. بعدها هاگیس نشان داد که اگر n بر ۳ بخش پذیر باشد آنگاه n&gt;101937042 و باید حداقل ۲۹۸۸۴۷ عامل اول داشته باشد.حدس کارمایکل.حدس: هیچ عددی مانند n وجود ندارد به‌طوری‌که برای هر عدد دیگر مانند m داشته باشیم formula_46.اگر یک مثال نقض برای این گزاره پیدا شود آنگاه می‌توان نشان داد که بی‌نهایت مثال نقض برای این گزاره وجود دارد.می‌توان نشان داد که کوچکترین مثال نقض برای این گزاره در مبنای ۱۰ بیش از ۱۰ میلیارد رقم دارد.