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

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

מקובל לסמנה באות היוונית \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_1n_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-\frac13\right)\left(1-\frac15\right)=24. נראה זאת. נכתוב n=p_1^{k_1}\cdots p_r^{k_r} ונקבל ממה שאנו כבר יודעים עבור חישוב פונקציית אוילר לחזקה של ראשוני כי:
:\begin{align} \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{align}

## תכונות הפונקציה
*פונקציית אוילר מקיימת את הזהות \sum_{d|n}\phi(d)=n, אותה אפשר להסביר באמצעות חישוב הסדרים של איברים בחבורה הציקלית \Z/n\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{align}\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\le i_1
שהרי לכל מחלק 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^km, ולכן: \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}^\infty\frac{\phi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}
:כאשר \zeta פונקציית זטא של רימן.
*\sum_{d|n}\frac{\mu(d)^2}{\varphi(d)}=\frac{n}{\phi(n)}
*בתורת גלואה, פונקציית אוילר מופיעה כממד של ההרחבה הציקלוטומית \Q[\rho_n]/\Q של שדה המספרים הרציונליים על ידי שורש היחידה מסדר n (הסיבה לכך היא שהפולינום הציקלוטומי הוא אי פריק).

## מקורות
*Hardy and Wright, An Introduction to the Theory of Numbers, פרק 18.

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

*
*

## הערות שוליים

קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה
אוילר
קטגוריה:לאונרד אוילר
קטגוריה:חשבון מודולרי