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

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

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

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

==חישוב הפונקציה==
אם <math>p</math> מספר ראשוני, אזי כל המספרים הקטנים מ-<math>p</math> זרים לו, ולכן <math>\phi(p)=p-1</math>. באופן כללי יותר, המספרים שאינם זרים ל-<math>p^s</math> הם כל אלה המתחלקים ב-<math>p</math>, שמספרם <math>p^{s-1}</math>, ולכן <math>\phi(p^s)=p^s-p^{s-1}=p^{s-1}(p-1)=p^s\left(1-\frac{1}{p}\right)</math>. ממשפט השאריות הסיני נובע שפונקציית אוילר כפלית, כלומר <math>\phi(n_1n_2)=\phi(n_1)\phi(n_2)</math> עבור <math>n_1,n_2</math> זרים.
מכיוון שכך, אפשר לחשב את ערכיה על-פי הנוסחה
:<math>\phi(n)=n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right)</math>
כאשר <math>p_1,\ldots,p_k</math> הם הגורמים הראשוניים השונים של <math>n</math>. לדוגמה <math>\phi(45)=45\left(1-\frac13\right)\left(1-\frac15\right)=24</math>. נראה זאת. נכתוב <math>n=p_1^{k_1}\cdots p_r^{k_r}</math> ונקבל ממה שאנו כבר יודעים עבור חישוב פונקציית אוילר לחזקה של ראשוני כי:
:<math>\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}</math>

==תכונות הפונקציה==
*פונקציית אוילר מקיימת את הזהות <math>\sum_{d|n}\phi(d)=n</math>, אותה אפשר להסביר באמצעות חישוב הסדרים של איברים בחבורה הציקלית <math>\Z/n\Z</math>. 
*נוכל להסתכל על הזהות הזו כקונבולוציה <math>\varphi*1=\text{id}</math> כאשר <math>\text{id}</math> פונקציית הזהות. לכן, מנוסחת ההיפוך של מביוס נובע כי
:<math>\varphi(n)=(\mu*\text{id})(n)=\sum_{d|n}\mu(d)\frac{n}{d}=n\sum_{d|n}\frac{\mu(d)}{d}</math>
כאשר <math>\mu</math> פונקציית מביוס.

נוכל לתת הוכחה נוספת, המבוססת על הנוסחה <math>\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)</math> לחישוב הפונקציה שהראינו. הרי אם <math>p_1,\ldots,p_r</math> הגורמים הראשוניים השונים המחלקים את <math>n</math>, נוכל להבחין כי
:<math>\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<\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{align}</math>
שהרי לכל מחלק <math>d>1, d|n</math>, אם הוא לא מכפלת ראשוניים שונים אז <math>\mu(d)=0</math> מהגדרת פונקציית מביוס.
*לכל <math>n>2</math>, <math>\phi(n)</math> מספר זוגי. ניתן לראות זאת מתכונת הכפליות. אם <math>n=2^k</math> בעבור <math>k>1</math>, אז <math>\phi(n)=2^k(1-0.5)=2^{k-1}</math>. אחרת ל-<math>n</math> יש מחלק <math>p</math> ראשוני אי-זוגי, כלומר הוא מהצורה <math>n=p^km</math>, ולכן: <math>\phi(n)=\phi(p^k)\phi(m)=p^{k-1}(p-1)\phi(m)</math>, ו-<math>p-1</math> זוגי.
*הערך הממוצע של הפונקציה הוא <math>\frac{\phi(1)+\cdots+\phi(n)}{n}\sim\frac{3}{\pi^2}n</math>. הגבול התחתון של היחס <math>\frac{\phi(n)}{n/\ln(\ln(n))}</math> הוא <math>e^{-\gamma}</math>, כאשר <math>\gamma</math> הוא קבוע אוילר-מסקרוני.
*ניתן לכתוב את טור דיריכלה של פונקציית אוילר באופן הבא:
:<math>F_\phi(s)=\sum_{n\,=\,1}^\infty\frac{\phi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}</math>
:כאשר <math>\zeta</math> פונקציית זטא של רימן.
*<math>\sum_{d|n}\frac{\mu(d)^2}{\varphi(d)}=\frac{n}{\phi(n)}</math>
*בתורת גלואה, פונקציית אוילר מופיעה כממד של ההרחבה הציקלוטומית <math>\Q[\rho_n]/\Q</math> של שדה המספרים הרציונליים על ידי שורש היחידה מסדר <math>n</math> (הסיבה לכך היא שהפולינום הציקלוטומי הוא אי פריק).

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

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

*
*

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

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