تابع فی اویلر

در نظریه اعداد تابع فی اویلر یا

\varphi (n)

تابعی است که تعداد اعداد طبیعی کوچکتر از n که نسبت به n اول اند را می‌شمارد. اگر n یک عدد طبیعی مثبت باشد، آنگاه

\varphi (n)

برابر است با تعداد اعداد طبیعی k در بازه ۱ تا n به‌طوری‌که gcd(n, k) = ۱. تابع فی اویلر یک تابع ضربی است، بدین معنی که اگر دو عدد m و n نسبت به هم اول باشند آنگاه

\varphi (mn)=\varphi (m)\varphi (n)

. برای مثلاً (۹)φ برابر ۶ است. زیرا اعداد ۱، ۲، ۴، ۵، ۷ و ۸ نسبت به ۹ اول هستند.

تاریخچه و نمادگذاری

لئونارد اولر این تابع را در سال ۱۷۶۳ معرفی کرد. در آن زمان او هنوز نماد خاصی برای این تابع تعیین نکرده بود. بعدها لئونارد اویلر با مطالعه بیشتر تابع فی، حرف یونانی π را برای آن برگزید. نماد استاندارد φ بعدها توسط گاوس استفاده شده‌است.

محاسبه مقدار تابع فی

چندین راه برای محاسبه این فرمول وجود دارد.

فرمول ضرب اویلر

اگر $p$ اول و $k \geq 1 باشد$ ، سپس

${\ displaystyle \ varphi (p ^ {k}) = p ^ {k-1} (p-1) = p ^ {k} \ left (1 - {\ frac {1} {p}} \ right). }$

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

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

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

تبدیل فوریه

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

{\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}}

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

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

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