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

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)$ .

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

אם $p$ מספר ראשוני, אז כל המספרים הקטנים מ-$p$ זרים לו, ולכן $\phi (p)=p-1$ . באופן כללי יותר, המספרים הזרים ל-$p^s$ הם כל אלו שאינם מתחלקים ב-$p$ , ולכן

$\phi (p^s)=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,\dots ,p_k$ הם הגורמים הראשוניים השונים של $n$ . למשל $\phi (45)=45(1-\frac{1}{3})(1-\frac{1}{5})=24$ .

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

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

לכל $n>2$ , $\phi (n)$ מספר זוגי. ניתן לראות זאת מתכונת הכפליות. אם $n=2^k$ עבור $k>1$ אז

$\phi (n)=2^k(1-\frac{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$ הוא קבוע אוילר.

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

מקורות

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