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

1000 הערכים הראשונים של פונקציית אוילר

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

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

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

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

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

$\varphi (n)=n(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_k})$

כאשר $p_1,\dots ,p_k$ הם הגורמים הראשוניים השונים של $n$. לדוגמה $\varphi (45)=45(1-\frac{1}{3})(1-\frac{1}{5})=24$. נראה זאת. נכתוב $n=p_1^{k_1}\cdots p_r^{k_r}$ ונקבל ממה שאנו כבר יודעים עבור חישוב פונקציית אוילר לחזקה של ראשוני כי:

$\begin{array}{cc}\varphi (n)& =\varphi (p_1^{k_1})\cdots \varphi (p_r^{k_r})\\ & =p_1^{k_1}(1-\frac{1}{p_1})\cdots p_r^{k_r}(1-\frac{1}{p_r})\\ & =p_1^{k_1}\cdots p_r^{k_r}(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_r})\\ & =n(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_r})\end{array}$

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

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

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

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

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

$\begin{array}{cc}\prod _{p|n}(1-\frac{1}{p})& =(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_r})\\ & =\sum _{k=0}^r\sum _{1\le i_1<\cdots <i_k\le r}\frac{(-1{)}^k}{p_{i_1}\cdots p_{i_k}}\\ & =\sum _{k=0}^r\sum _{1\le i_1<\cdots <i_k\le 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{array}$

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

• לכל $n>2$, $\varphi (n)$ מספר זוגי. ניתן לראות זאת מתכונת הכפליות. אם $n=2^k$ בעבור $k>1$, אז $\varphi (n)=2^k(1-0.5)=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}^{\mathrm{\infty }}\frac{\varphi (n)}{n^s}=\frac{\zeta (s-1)}{\zeta (s)}$

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

• $\sum _{d|n}\frac{\mu (d{)}^2}{\phi (d)}=\frac{n}{\varphi (n)}$
• בתורת גלואה, פונקציית אוילר מופיעה כממד של ההרחבה הציקלוטומית $\mathbb{Q}[{\rho }_n]/\mathbb{Q}$ של שדה המספרים הרציונליים על ידי שורש היחידה מסדר $n$ (הסיבה לכך היא שהפולינום הציקלוטומי הוא אי פריק).

מקורות

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

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

• תבנית:MathWorld
• תבנית:OEIS