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

פונקציית אוילר, נקראת על שם לאונרד אוילר, היא פונקציה אריתמטית חשובה. מסמנים אותה בדרך כלל ב‑φ (פי). φ(n) הוא מספר המספרים הטבעיים הקטנים מ‑n ש"זרי"ים לו. זר, כלומר שאין לו גורם משותף עם n חוץ מ‑1. למשל: φ(5)=4 כי 1,2,3,4 כולם זרים ל‑5; φ(6)=2 כי רק 1 ו‑5 זרים ל‑6; ו‑φ(1)=1 כי 1 נחשב זר לעצמו. זו גם גודלה של חבורת אוילר U_n המתאימה ל‑n. משפט אוילר אומר שהסדר של כל איבר בחבורה כזו מחלק את φ(n).


אם p הוא מספר ראשוני, כל המספרים הקטנים מ‑p זרים לו, ולכן φ(p)=p−1. עבור חזקה של ראשוני p^s המספרים שאינם זרים הם אלה שמתחלקים ב‑p, ולכן φ(p^s)=p^s−p^{s−1}=p^{s−1}(p−1)=p^s(1−1/p). פונקציית אוילר היא כפלית, כלומר אם n1 ו‑n2 זרים זה לזה אז φ(n1n2)=φ(n1)φ(n2). מכאן מתקבלת הנוסחה הכללית: φ(n)=n∏_{p|n}(1−1/p), כאשר p_1,…,p_k הם הגורמים הראשוניים השונים של n. לדוגמה φ(45)=45(1−1/3)(1−1/5)=24.


ניתן לכתוב את φ באמצעות כפול של פונקציית מביוס μ והפונקציה הזהותית id: φ=(μ*id). באופן מקוצר: φ(n)=∑_{d|n}μ(d)·(n/d)=n∑_{d|n}μ(d)/d. כאן μ היא פונקציית מביוס, המוגדרת לפי פירוק המספרים לראשוניים. יש גם ביטוי סדרה דיריכלה: ∑_{n=1}^∞ φ(n)/n^s = ζ(s−1)/ζ(s), כאשר ζ היא פונקציית זטא של רימן.

פונקציית אוילר נקראת על שם אוילר. מסמנים אותה φ (פי). φ(n) סופר כמה מספרים קטנים מ‑n הם "זרים" לו. זר אומר שאין להם מחלק משותף עם n חוץ מ‑1. לדוגמה: φ(5)=4 כי 1,2,3,4 זרים ל‑5. φ(6)=2 כי רק 1 ו‑5 זרים ל‑6.


אם p הוא מספר ראשוני, אז φ(p)=p−1. אם יש חזקה של ראשוני p^s נקבל φ(p^s)=p^s−p^{s−1}. הפונקציה גם כפלית: אם שני מספרים אינם משתפים גורם משותף אז φ של המוצר שלהם שווה למכפלת ה‑φ שלהם. לכן אפשר לחשב φ(n) בעזרת כל הגורמים הראשוניים של n: φ(n)=n·(1−1/p_1)·(1−1/p_2)·… . לדוגמה φ(45)=24.


יש נוסחה נוספת שמשתמשת בסכום על כל המחלקים של n ובפונקציית מביוס. בנוסף יש קשר עם פונקציית זטא של רימן, דרך סכום של φ(n)/n^s.