פונקציית אוילר

1,000 הערכים הראשונים של פונקציית אוילר

פונקציית אוילר, הקרויה על-שם לאונרד אוילר, היא דוגמה חשובה לפונקציה אריתמטית. הפונקציה, שאותה מקובל לסמן באות היוונית $\ \varphi$ (פִי), מוגדרת באופן הבא: $\ \varphi(n)$ שווה למספרם של המספרים הטבעיים הזרים ל-n ואינם גדולים ממנו. למשל, $\ \varphi(5)=|\{1,2,3,4\}|=4$ , $\ \varphi(6)=|\{1,5\}|=2$ , ואילו $\ \varphi(1)=|\{1\}|=1$ (1 הוא המספר הטבעי היחיד שזר לעצמו).

הפונקציה מוכרת ושימושית בעיקר בזכות משפט אוילר, שלפיו הסדר של כל איבר בחבורת אוילר מסדר $\ n$ מחלק את $\ \varphi(n)$ .

חישוב הפונקציה [עריכה]

אם $\ p$ מספר ראשוני, אז כל המספרים הקטנים מ- $\ p$ זרים לו, ולכן $\ \varphi(p)=p-1$ . באופן כללי יותר, המספרים הזרים ל- $\ p^{s}$ הם כל אלו שאינם מתחלקים ב- $\ p$ , ולכן $\ \varphi(p^s)=p^{s-1}(p-1) = p^s\left(1-\frac{1}{p}\right)$ . ממשפט השאריות הסיני נובע שפונקציית אוילר היא כפלית, כלומר, $\ \varphi(nm) = \varphi(n)\varphi(m)$ כל אימת שהמספרים $\ n,m$ זרים. מכיוון שכך, אפשר לחשב את ערכיה על-פי הנוסחה $\ \varphi(n) = n\left(1-{1\over p_1}\right)\left(1-{1\over p_2}\right)\cdots\left(1-{1\over p_k}\right)$ , כאשר $\ p_1,p_2,...,p_k$ הם הגורמים הראשוניים השונים של $\ n$ . לדוגמה $\ \varphi(45)=45\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)=24$ .

תכונות הפונקציה [עריכה]

פונקציית אוילר מקיימת את הזהות $\ \sum_{d|n} \varphi(d)=n$ , אותה אפשר להסביר באמצעות חישוב הסדרים של איברים בחבורה הציקלית $\ \mathbb{Z}/n\mathbb{Z}$ .

לכל $2<n$ , $\varphi(n)$ מספר זוגי. ניתן לראות זאת מתכונת הכפליות. אם $n = 2^k$ ל- $1<k$ אז $\varphi(n) = 2^k(1-1/2) = 2^{k-1}$ . אחרת, ל-n יש מחלק p ראשוני אי-זוגי, כלומר הוא מהצורה $n = p^km$ , ולכן: $\varphi(n) = \varphi(p^k)\varphi(m) = p^{k-1}(p-1)\varphi(m)$ , ו- $p-1$ זוגי.

הערך הממוצע של הפונקציה הוא $\ \frac{\varphi(1)+\cdots+\varphi(n)}{n} \sim \frac{6}{\pi^2}n$ . הגבול התחתון של היחס $\ \frac{\varphi(n)}{n/\ln\ln n}$ הוא $\ e^{-\gamma}$ , כאשר $\ \gamma$ הוא הקבוע של אוילר.