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

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

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

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

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

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

\phi (n)=n\left(1-{\frac {1}{p_{1}}}\right)\cdots \left(1-{\frac {1}{p_{k}}}\right)

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

{\begin{aligned}\phi (n)&=\phi (p_{1}^{k_{1}})\cdots \phi (p_{r}^{k_{r}})\\&=p_{1}^{k_{1}}\left(1-{\frac {1}{p_{1}}}\right)\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{r}}}\right)\\&=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{1}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)\\&=n\left(1-{\frac {1}{p_{1}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)\end{aligned}}

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

פונקציית אוילר מקיימת את הזהות $\sum _{d|n}\phi (d)=n$ , אותה אפשר להסביר באמצעות חישוב הסדרים של איברים בחבורה הציקלית $\mathbb {Z} /n\mathbb {Z}$ .
נוכל להסתכל על הזהות הזו כקונבולוציה $\varphi *1={\text{id}}$ כאשר ${\text{id}}$ פונקציית הזהות. לכן, מנוסחת ההיפוך של מביוס נובע כי

\varphi (n)=(\mu *{\text{id}})(n)=\sum _{d|n}\mu (d){\frac {n}{d}}=n\sum _{d|n}{\frac {\mu (d)}{d}}

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

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

{\begin{aligned}\prod _{p|n}\left(1-{\frac {1}{p}}\right)&=\left(1-{\frac {1}{p_{1}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)\\&=\sum _{k\,=\,0}^{r}\sum _{1\leq i_{1}<\cdots <i_{k}\leq r}{\frac {(-1)^{k}}{p_{i_{1}}\cdots p_{i_{k}}}}\\&=\sum _{k\,=\,0}^{r}\sum _{1\leq i_{1}<\cdots <i_{k}\leq r}{\frac {\mu (p_{i_{1}}\cdots p_{i_{k}})}{p_{i_{1}}\cdots p_{i_{k}}}}\\&=\sum _{d|n}{\frac {\mu (d)}{d}}\end{aligned}}

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

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