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

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):=|U_{n}|$ .

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

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

אם $p$ מספר ראשוני, אז כל המספרים הקטנים מ- $p$ זרים לו, ולכן $\varphi (p)=p-1$ . באופן כללי יותר, המספרים שאינם זרים ל- $p^{s}$ הם כל אלו שמתחלקים ב- $p$ , שמספרם $p^{s}/p=p^{s-1}$ , ולכן $\varphi (p^{s})=p^{s}-p^{s-1}=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$ . נראה זאת. נכתוב $n=p_{1}^{k_{1}}\dots p_{r}^{k_{r}}$ ואז נקבל ממה שאנו כבר יודעים עבור חישוב פונקציית אוילר לחזקה של ראשוני כי:

${\begin{aligned}\varphi (n)&=\varphi \left(p_{1}^{k_{1}}\right)\cdots \varphi \left(p_{r}^{k_{r}}\right)\\&=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}\varphi (d)=n$ , אותה אפשר להסביר באמצעות חישוב הסדרים של איברים בחבורה הציקלית $\mathbb {Z} /n\mathbb {Z}$ .

נוכל להסתכל על הזהות הזו כקונבולוציה $\varphi *1=i$ כאשר $i$ היא פונקציית הזהות. לכן, מנוסחת ההיפוך של מוביוס נובע כי

$\varphi (n)=(\mu *i)(n)=\sum _{d\mid n}\mu (d){\frac {n}{d}}=n\sum _{d\mid n}{\frac {\mu (d)}{d}}$

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

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

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

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

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

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