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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
1,000 הערכים הראשונים של פונקציית אוילר

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

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

חישוב הפונקציה[עריכת קוד מקור | עריכה]

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

תכונות הפונקציה[עריכת קוד מקור | עריכה]

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

לכל 2<n, \varphi(n) מספר זוגי. ניתן לראות זאת מתכונת הכפליות. אם n = 2^k ל-1<k אז \varphi(n) = 2^k(1-1/2) = 2^{k-1}. אחרת, ל-n יש מחלק p ראשוני אי-זוגי, כלומר הוא מהצורה  n = p^km, ולכן: \varphi(n) = \varphi(p^k)\varphi(m) = p^{k-1}(p-1)\varphi(m), ו-p-1 זוגי.

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

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

מקורות[עריכת קוד מקור | עריכה]

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