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

פונקציית אוילר (על שם המתמטיקאי השווייצרי לאונרד אוילר) היא דוגמה חשובה לפונקציה אריתמטית.

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

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

חישוב הפונקציה

אם $p$ מספר ראשוני, אזי כל המספרים הקטנים מ- $p$ זרים לו, ולכן $ϕ (p) = p - 1$ . באופן כללי יותר, המספרים שאינם זרים ל- $p^{s}$ הם כל אלה המתחלקים ב- $p$ , שמספרם $p^{s - 1}$ , ולכן $ϕ (p^{s}) = p^{s} - p^{s - 1} = p^{s - 1} (p - 1) = p^{s} (1 - \frac{1}{p})$ . ממשפט השאריות הסיני נובע שפונקציית אוילר כפלית, כלומר $ϕ (n_{1} n_{2}) = ϕ (n_{1}) ϕ (n_{2})$ עבור $n_{1}, n_{2}$ זרים. מכיוון שכך, אפשר לחשב את ערכיה על-פי הנוסחה

ϕ (n) = n (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{k}})

כאשר $p_{1}, \dots, p_{k}$ הם הגורמים הראשוניים השונים של $n$ . לדוגמה $ϕ (45) = 45 (1 - \frac{1}{3}) (1 - \frac{1}{5}) = 24$ . נראה זאת. נכתוב $n = p_{1}^{k_{1}} \dots p_{r}^{k_{r}}$ ונקבל ממה שאנו כבר יודעים עבור חישוב פונקציית אוילר לחזקה של ראשוני כי:

\begin{aligned} ϕ (n) & = ϕ (p_{1}^{k_{1}}) \dots ϕ (p_{r}^{k_{r}}) \\ = p_{1}^{k_{1}} (1 - \frac{1}{p_{1}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p_{r}}) \\ = p_{1}^{k_{1}} \dots p_{r}^{k_{r}} (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{r}}) \\ = n (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{r}}) \end{aligned}

תכונות הפונקציה

פונקציית אוילר מקיימת את הזהות $\sum_{d | n} ϕ (d) = n$ , אותה אפשר להסביר באמצעות חישוב הסדרים של איברים בחבורה הציקלית $ℤ / n ℤ$ .
נוכל להסתכל על הזהות הזו כקונבולוציה $φ * 1 = id$ כאשר $id$ פונקציית הזהות. לכן, מנוסחת ההיפוך של מביוס נובע כי

φ (n) = (μ * id) (n) = \sum_{d | n} μ (d) \frac{n}{d} = n \sum_{d | n} \frac{μ (d)}{d}

כאשר $μ$ פונקציית מביוס.

נוכל לתת הוכחה נוספת, המבוססת על הנוסחה $ϕ (n) = n \prod_{p | n} (1 - \frac{1}{p})$ לחישוב הפונקציה שהראינו. הרי אם $p_{1}, \dots, p_{r}$ הגורמים הראשוניים השונים המחלקים את $n$ , נוכל להבחין כי

\begin{aligned} \prod_{p | n} (1 - \frac{1}{p}) & = (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{r}}) \\ = \sum_{k = 0}^{r} \sum_{1 \leq i_{1} < \dots < i_{k} \leq r} \frac{(- 1)^{k}}{p_{i_{1}} \dots p_{i_{k}}} \\ = \sum_{k = 0}^{r} \sum_{1 \leq i_{1} < \dots < i_{k} \leq r} \frac{μ (p_{i_{1}} \dots p_{i_{k}})}{p_{i_{1}} \dots p_{i_{k}}} \\ = \sum_{d | n} \frac{μ (d)}{d} \end{aligned}

שהרי לכל מחלק $d > 1, d | n$ , אם הוא לא מכפלת ראשוניים שונים אז $μ (d) = 0$ מהגדרת פונקציית מביוס.

לכל $n > 2$ , $ϕ (n)$ מספר זוגי. ניתן לראות זאת מתכונת הכפליות. אם $n = 2^{k}$ בעבור $k > 1$ , אז $ϕ (n) = 2^{k} (1 - 0.5) = 2^{k - 1}$ . אחרת ל- $n$ יש מחלק $p$ ראשוני אי-זוגי, כלומר הוא מהצורה $n = p^{k} m$ , ולכן: $ϕ (n) = ϕ (p^{k}) ϕ (m) = p^{k - 1} (p - 1) ϕ (m)$ , ו- $p - 1$ זוגי.
הערך הממוצע של הפונקציה הוא^[1] $\frac{ϕ (1) + \dots + ϕ (n)}{n} \sim \frac{3}{π^{2}} n$ . הגבול התחתון של היחס $\frac{ϕ (n)}{n / \ln (\ln (n))}$ הוא $e^{- γ}$ , כאשר $γ$ הוא קבוע אוילר-מסקרוני.
ניתן לכתוב את טור דיריכלה של פונקציית אוילר באופן הבא: