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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

[עריכה] חישוב הפונקציה

אם \ p מספר ראשוני, אז כל המספרים הקטנים מ- p זרים לו, ולכן \ \phi(p)=p-1. באופן כללי יותר, המספרים הזרים ל- ps הם כל אלו שאינם מתחלקים ב- 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-{1\over p_1})(1-{1\over p_2})...(1-{1\over p_k}), כאשר \ p_1,p_2,...,p_k הם הגורמים הראשוניים השונים של n. לדוגמה \ \phi(45)=45(1-\frac{1}{3})(1-\frac{1}{5})=24.

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

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

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