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

1,000 הערכים הראשונים של פונקציית אוילר

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

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

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

אם $p$ מספר ראשוני, אז כל המספרים הקטנים מ-$p$ זרים לו, ולכן $\phi (p)=p-1$. באופן כללי יותר, המספרים שאינם זרים ל-$p^s$ הם כל אלו שמתחלקים ב-$p$, שמספרם $p^s/p=p^{s-1}$, ולכן $\phi (p^s)=p^s-p^{s-1}=p^{s-1}(p-1)=p^s(1-\frac{1}{p})$. ממשפט השאריות הסיני נובע שפונקציית אוילר היא כפלית, כלומר, $\phi (nm)=\phi (n)\phi (m)$ כל אימת שהמספרים $n,m$ זרים. מכיוון שכך, אפשר לחשב את ערכיה על-פי הנוסחה $\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})$, כאשר $p_1,p_2,...,p_k$ הם הגורמים הראשוניים השונים של $n$. לדוגמה $\phi (45)=45(1-\frac{1}{3})(1-\frac{1}{5})=24$. נראה זאת. נכתוב $n=p_1^{k_1}\dots p_r^{k_r}$ ואז נקבל ממה שאנו כבר יודעים עבור חישוב פונקציית אוילר לחזקה של ראשוני כי:

$\begin{array}{rl}\phi (n)& =\phi \left(p_1^{k_1}\right)\cdots \phi \left(p_r^{k_r}\right)\\ & =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}\phi (d)=n$, אותה אפשר להסביר באמצעות חישוב הסדרים של איברים בחבורה הציקלית $\mathbb{\mathbb{Z}}/n\mathbb{\mathbb{Z}}$.

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

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

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

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

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

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

• לכל $2<n$, $\phi (n)$ מספר זוגי. ניתן לראות זאת מתכונת הכפליות. אם $n=2^k$ בעבור $1<k$, אז $\phi (n)=2^k(1-1/2)=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$ זוגי.

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

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

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

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

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

מקורות

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

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

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

• פונקציית אוילר, באתר MathWorld (באנגלית)
• סדרת מספרי פונקציית אוילר באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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