1000 הערכים הראשונים של פונקציית אוילר פונקציית אוילר (על שם המתמטיקאי הגרמני לאונרד אוילר ) היא דוגמה חשובה לפונקציה אריתמטית .
מקובל לסמנה באות היוונית ϕ {\displaystyle \phi } (פי ), והיא מוגדרת באופן הבא: ϕ ( n ) {\displaystyle \phi (n)} שווה למספר המספרים הטבעיים הקטנים מ- n {\displaystyle n} וזרים לו. למשל, ϕ ( 5 ) = | { 1 , 2 , 3 , 4 } | = 4 , ϕ ( 6 ) = | { 1 , 5 } | = 2 {\displaystyle \phi (5)=|\{1,2,3,4\}|=4,\phi (6)=|\{1,5\}|=2} , ואילו ϕ ( 1 ) = | { 1 } | = 1 {\displaystyle \phi (1)=|\{1\}|=1} (1 הוא המספר הטבעי היחיד שזר לעצמו). כלומר, זהו גודלה של חבורת אוילר U n {\displaystyle U_{n}} המתאימה ל- n {\displaystyle n} .
הפונקציה מוכרת ושימושית בעיקר בזכות משפט אוילר , שלפיו הסדר של כל איבר בחבורת אוילר מסדר n {\displaystyle n} מחלק את ϕ ( n ) {\displaystyle \phi (n)} .
אם p {\displaystyle p} מספר ראשוני , אזי כל המספרים הקטנים מ- p {\displaystyle p} זרים לו, ולכן ϕ ( p ) = p − 1 {\displaystyle \phi (p)=p-1} . באופן כללי יותר, המספרים שאינם זרים ל- p s {\displaystyle p^{s}} הם כל אלה המתחלקים ב- p {\displaystyle p} , שמספרם p s − 1 {\displaystyle p^{s-1}} , ולכן ϕ ( p s ) = p s − p s − 1 = p s − 1 ( p − 1 ) = p s ( 1 − 1 p ) {\displaystyle \phi (p^{s})=p^{s}-p^{s-1}=p^{s-1}(p-1)=p^{s}\left(1-{\frac {1}{p}}\right)} . ממשפט השאריות הסיני נובע שפונקציית אוילר כפלית , כלומר ϕ ( n 1 n 2 ) = ϕ ( n 1 ) ϕ ( n 2 ) {\displaystyle \phi (n_{1}n_{2})=\phi (n_{1})\phi (n_{2})} עבור n 1 , n 2 {\displaystyle n_{1},n_{2}} זרים. מכיוון שכך, אפשר לחשב את ערכיה על-פי הנוסחה
ϕ ( n ) = n ( 1 − 1 p 1 ) ⋯ ( 1 − 1 p k ) {\displaystyle \phi (n)=n\left(1-{\frac {1}{p_{1}}}\right)\cdots \left(1-{\frac {1}{p_{k}}}\right)} כאשר p 1 , … , p k {\displaystyle p_{1},\ldots ,p_{k}} הם הגורמים הראשוניים השונים של n {\displaystyle n} . לדוגמה ϕ ( 45 ) = 45 ( 1 − 1 3 ) ( 1 − 1 5 ) = 24 {\displaystyle \phi (45)=45\left(1-{\frac {1}{3}}\right)\left(1-{\frac {1}{5}}\right)=24} . נראה זאת. נכתוב n = p 1 k 1 ⋯ p r k r {\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}} ונקבל ממה שאנו כבר יודעים עבור חישוב פונקציית אוילר לחזקה של ראשוני כי:
ϕ ( n ) = ϕ ( p 1 k 1 ) ⋯ ϕ ( p r k r ) = p 1 k 1 ( 1 − 1 p 1 ) ⋯ p r k r ( 1 − 1 p r ) = p 1 k 1 ⋯ p r k r ( 1 − 1 p 1 ) ⋯ ( 1 − 1 p r ) = n ( 1 − 1 p 1 ) ⋯ ( 1 − 1 p r ) {\displaystyle {\begin{aligned}\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{aligned}}} פונקציית אוילר מקיימת את הזהות ∑ d | n ϕ ( d ) = n {\displaystyle \sum _{d|n}\phi (d)=n} , אותה אפשר להסביר באמצעות חישוב הסדרים של איברים בחבורה הציקלית Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } . נוכל להסתכל על הזהות הזו כקונבולוציה φ ∗ 1 = id {\displaystyle \varphi *1={\text{id}}} כאשר id {\displaystyle {\text{id}}} פונקציית הזהות . לכן, מנוסחת ההיפוך של מביוס נובע כי φ ( n ) = ( μ ∗ id ) ( n ) = ∑ d | n μ ( d ) n d = n ∑ d | n μ ( d ) d {\displaystyle \varphi (n)=(\mu *{\text{id}})(n)=\sum _{d|n}\mu (d){\frac {n}{d}}=n\sum _{d|n}{\frac {\mu (d)}{d}}} כאשר μ {\displaystyle \mu } פונקציית מביוס .
נוכל לתת הוכחה נוספת, המבוססת על הנוסחה ϕ ( n ) = n ∏ p | n ( 1 − 1 p ) {\displaystyle \phi (n)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)} לחישוב הפונקציה שהראינו. הרי אם p 1 , … , p r {\displaystyle p_{1},\ldots ,p_{r}} הגורמים הראשוניים השונים המחלקים את n {\displaystyle n} , נוכל להבחין כי
∏ p | n ( 1 − 1 p ) = ( 1 − 1 p 1 ) ⋯ ( 1 − 1 p r ) = ∑ k = 0 r ∑ 1 ≤ i 1 < ⋯ < i k ≤ r ( − 1 ) k p i 1 ⋯ p i k = ∑ k = 0 r ∑ 1 ≤ i 1 < ⋯ < i k ≤ r μ ( p i 1 ⋯ p i k ) p i 1 ⋯ p i k = ∑ d | n μ ( d ) d {\displaystyle {\begin{aligned}\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\leq i_{1}<\cdots <i_{k}\leq r}{\frac {(-1)^{k}}{p_{i_{1}}\cdots p_{i_{k}}}}\\&=\sum _{k\,=\,0}^{r}\sum _{1\leq i_{1}<\cdots <i_{k}\leq 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{aligned}}} שהרי לכל מחלק d > 1 , d | n {\displaystyle d>1,d|n} , אם הוא לא מכפלת ראשוניים שונים אז μ ( d ) = 0 {\displaystyle \mu (d)=0} מהגדרת פונקציית מביוס.
לכל n > 2 {\displaystyle n>2} , ϕ ( n ) {\displaystyle \phi (n)} מספר זוגי . ניתן לראות זאת מתכונת הכפליות. אם n = 2 k {\displaystyle n=2^{k}} בעבור k > 1 {\displaystyle k>1} , אז ϕ ( n ) = 2 k ( 1 − 0.5 ) = 2 k − 1 {\displaystyle \phi (n)=2^{k}(1-0.5)=2^{k-1}} . אחרת ל- n {\displaystyle n} יש מחלק p {\displaystyle p} ראשוני אי-זוגי, כלומר הוא מהצורה n = p k m {\displaystyle n=p^{k}m} , ולכן: ϕ ( n ) = ϕ ( p k ) ϕ ( m ) = p k − 1 ( p − 1 ) ϕ ( m ) {\displaystyle \phi (n)=\phi (p^{k})\phi (m)=p^{k-1}(p-1)\phi (m)} , ו- p − 1 {\displaystyle p-1} זוגי. הערך הממוצע של הפונקציה הוא[1] ϕ ( 1 ) + ⋯ + ϕ ( n ) n ∼ 3 π 2 n {\displaystyle {\frac {\phi (1)+\cdots +\phi (n)}{n}}\sim {\frac {3}{\pi ^{2}}}n} . הגבול התחתון של היחס ϕ ( n ) n / ln ( ln ( n ) ) {\displaystyle {\frac {\phi (n)}{n/\ln(\ln(n))}}} הוא e − γ {\displaystyle e^{-\gamma }} , כאשר γ {\displaystyle \gamma } הוא קבוע אוילר-מסקרוני . ניתן לכתוב את טור דיריכלה של פונקציית אוילר באופן הבא: F ϕ ( s ) = ∑ n = 1 ∞ ϕ ( n ) n s = ζ ( s − 1 ) ζ ( s ) {\displaystyle F_{\phi }(s)=\sum _{n\,=\,1}^{\infty }{\frac {\phi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}} כאשר ζ {\displaystyle \zeta } פונקציית זטא של רימן . Hardy and Wright, An Introduction to the Theory of Numbers, פרק 18. ^ זו השערה לא מפורסמת של גאוס מ-1796. פורסמה לראשונה על ידי דיריכלה ב-1849, והוכחה לבסוף על ידי Arnold Walfisz.