تابع فی اویلر

این تابع بیان می‌کند که

${\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}$

که در آن ${\displaystyle p}$ یک عدد اول است به‌طوری‌که ${\displaystyle n}$ بر ${\displaystyle p}$ بخش پذیر است.

مقدار تابع فی برابر است با مقدار تبدیل فوریه گسسته ب.م.م در ۱:

${\displaystyle {\begin{aligned}{\mathcal {F}}\left\{\mathbf {x} \right\}[m]&=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}},\mathbf {x} =\left\{\gcd(k,n)\right\}\quad {\text{for}}\,k\in \left\{1\dots n\right\}\\\varphi (n)&={\mathcal {F}}\left\{\mathbf {x} \right\}[1]=\sum \limits _{k=1}^{n}\gcd(k,n)e^{{-2\pi i}{\frac {k}{n}}}.\end{aligned}}}$

مقدار حقیقی این فرمول برابر است با:

${\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {2\pi {\frac {k}{n}}}.}$

توجه کنید که برخلاف دو فرمول دیگر در این فرمول نیازی به دانستن عوامل اول n نیست. اما چون فرمول شامل محاسبه ب.م.م n و همه اعداد مثبت کمتر از n است در نهایت به تجزیه n نیاز خواهیم داشت.

فرمول کلاسیک اویلر

${\displaystyle \sum _{d\mid n}\varphi (d)=n,}$

این فرمول به روش‌های مختلف قابل اثبات است.

برای n>1 می‌توان تابع فی را به عنوان یک حد تابع زتای ریمان محاسبه کرد

${\displaystyle \varphi (n)=n\lim \limits _{s\rightarrow 1}\zeta (s)\sum \limits _{d|n}\mu (d)(e^{1/d})^{(s-1)}}$

که در این فرمول

${\displaystyle \zeta (s)}$ تابع زتای ریمان است، ${\displaystyle \mu }$ تابع موبیوس است، ${\displaystyle e}$ عدد نپر است، و d مقسوم علیه است.

اشنایدر دو رابطه پیدا کرد که نسبت طلایی و تابع فی و تابع موبیوس را به هم مرتبط می‌کرد. در فرمول‌های زیر ${\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}=1.618\dots }$ نسبت طلایی است.

این روابط به صورت زیر هستند: ${\displaystyle \phi =-\sum _{k=1}^{\infty }{\frac {\varphi (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right)}$ و

${\displaystyle {\frac {1}{\phi }}=-\sum _{k=1}^{\infty }{\frac {\mu (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right).}$

از کم کردن این دو نتیجه می‌شود

${\displaystyle \sum _{k=1}^{\infty }{\frac {\mu (k)-\varphi (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right)=1.}$

با اعمال تابع نمایی به هر دو طرف رابطه به یک رابطه برای عدد نپر می‌رسیم

${\displaystyle e=\prod _{k=1}^{\infty }\left(1-{\frac {1}{\phi ^{k}}}\right)^{\frac {\mu (k)-\varphi (k)}{k}}.}$

اثبات بر پایه دو فرمول زیر است:

${\displaystyle \sum _{k=1}^{\infty }{\frac {\varphi (k)}{k}}(-\log(1-x^{k}))={\frac {x}{1-x}}}$ and ${\displaystyle \sum _{k=1}^{\infty }{\frac {\mu (k)}{k}}(-\log(1-x^{k}))=x,}$

در سیستم RSA ابتدا دو عدد اول بزرگ p و q را انتخاب می‌کنیم. سپس مقادیر n=pq و k=${\displaystyle \varphi (n)}$ را محاسبه می‌کنیم؛ و دوعدد e و d را پیدا می‌کنیم به‌طوری‌که ed به پیمانه k برابر ۱ باشد. n و e به عنوان کلید عمومی اعلان می‌شوند و n و d به عنوان کلید خصوصی مخفی نگاه داشته می‌شود.

یک پیام مانند عدد مثبت m به صورت S = m^e mod n رمزگذاری می‌شود.

برای رمزگشایی مقدار t = S^d mod n محاسبه می‌شود. قضیه اویلر نشان می‌دهد که اگر t کمتر از n باشد آنگاه t=m.

سیستم RSA به خطر خواهد افتاد اگر بتوانیم عدد n را تجزیه کنیم یا بتوانیم مقدار تابع فی را بدون تجزیه n بدست بیاوریم.

اگر p اول باشد آنگاه ${\displaystyle \varphi (p)=p-1}$. لیمر در سال ۱۹۳۲ سؤال زیر را مطرح کرد:

آیا عدد مرکب n وجود دارد به‌طوری‌که ${\displaystyle \varphi (n)|n-1}$؟

در سال ۱۹۳۳ لیمر اثبات کرد که اگر n وجود داشته باشد آنگاه حتماً باید فرد باشد و باید حداقل ۷ عامل اول داشته باشد. در سال ۱۹۸۰ کوهن و هاگیس اثبات کردند که n>10²⁰ و باید حداقل ۱۴ عامل اول داشته باشد. بعدها هاگیس نشان داد که اگر n بر ۳ بخش پذیر باشد آنگاه n>10^1937042 و باید حداقل ۲۹۸۸۴۷ عامل اول داشته باشد.

حدس: هیچ عددی مانند n وجود ندارد به‌طوری‌که برای هر عدد دیگر مانند m داشته باشیم ${\displaystyle \varphi (n)!=\varphi (m)}$. اگر یک مثال نقض برای این گزاره پیدا شود آنگاه می‌توان نشان داد که بی‌نهایت مثال نقض برای این گزاره وجود دارد. می‌توان نشان داد که کوچکترین مثال نقض برای این گزاره در مبنای ۱۰ بیش از ۱۰ میلیارد رقم دارد.