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

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$ זוגי.

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

$F_{\varphi }(s)=\sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}$

כאשר $\zeta$ היא פונקציית זטא של רימן.

• $\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}$.

• בתורת גלואה, פונקציית אוילר מופיעה כממד של ההרחבה הציקלוטומית $\mathbb {Q} [\rho _{n}]/\mathbb {Q}$ של שדה המספרים הרציונליים על ידי שורש היחידה מסדר $n$ (הסיבה לכך היא שהפולינום הציקלוטומי הוא אי פריק).

מקורות

• Hardy and Wright, An Introduction to the Theory of Numbers, פרק 18.

קישורים חיצוניים

מדיה וקבצים בנושא פונקציית אוילר בוויקישיתוף

• פונקציית אוילר, באתר MathWorld (באנגלית)