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

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

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

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

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

אם p מספר ראשוני, אז כל המספרים הקטנים מ-p זרים לו, ולכן φ(p)=p1. באופן כללי יותר, המספרים שאינם זרים ל-ps הם כל אלו שמתחלקים ב-p, שמספרם ps/p=ps1, ולכן φ(ps)=psps1=ps1(p1)=ps(11p). ממשפט השאריות הסיני נובע שפונקציית אוילר היא כפלית, כלומר, φ(nm)=φ(n)φ(m) כל אימת שהמספרים n,m זרים. מכיוון שכך, אפשר לחשב את ערכיה על-פי הנוסחה φ(n)=n(11p1)(11p2)(11pk), כאשר p1,p2,...,pk הם הגורמים הראשוניים השונים של n. לדוגמה φ(45)=45(113)(115)=24. נראה זאת. נכתוב n=p1k1prkr ואז נקבל ממה שאנו כבר יודעים עבור חישוב פונקציית אוילר לחזקה של ראשוני כי:

φ(n)=φ(p1k1)φ(prkr)=p1k1(11p1)prkr(11pr)=p1k1prkr(11p1)(11pr)=n(11p1)(11pr).

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

  • פונקציית אוילר מקיימת את הזהות d|nφ(d)=n, אותה אפשר להסביר באמצעות חישוב הסדרים של איברים בחבורה הציקלית /n.

φ(n)=(μ*i)(n)=dnμ(d)nd=ndnμ(d)d

כאשר μ היא פונקציית מוביוס.

נוכל לתת הוכחה נוספת, המבוססת על הנוסחה φ(n)=npn(11p) לחישוב הפונקציה שהראינו. הרי אם נסמן ב-p1,,pr את הגורמים הראשוניים השונים שמחלקים את n, נוכל להבחין כי

pn(11p)=(11p1)(11p2)(11pr)=k=0r1i1<i2<<ikr(1)k1pi1pi2pik=k=0r1i1<i2<<ikrμ(pi1pi2pik)pi1pi2pik=dnμ(d)d

שהרי לכל מחלק d>1,dn, אם הוא לא מכפלת ראשוניים שונים אז μ(d)=0 מהגדרת פונקציית מוביוס.

  • לכל 2<n, φ(n) מספר זוגי. ניתן לראות זאת מתכונת הכפליות. אם n=2k בעבור 1<k, אז φ(n)=2k(11/2)=2k1. אחרת, ל-n יש מחלק p ראשוני אי-זוגי, כלומר הוא מהצורה n=pkm, ולכן: φ(n)=φ(pk)φ(m)=pk1(p1)φ(m), ו-p1 זוגי.
  • הערך הממוצע של הפונקציה הוא[1] φ(1)++φ(n)n3π2n. הגבול התחתון של היחס φ(n)n/lnlnn הוא eγ, כאשר γ הוא קבוע אוילר.
  • ניתן לכתוב את טור דיריכלה של פונקציית אוילר באופן הבא:

Fφ(s)=n=1φ(n)ns=ζ(s1)ζ(s)

כאשר ζ היא פונקציית זטא של רימן.

  • dnμ2(d)φ(d)=nφ(n).

מקורות

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

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

ויקישיתוף מדיה וקבצים בנושא פונקציית אוילר בוויקישיתוף

הערות שוליים

  1. זו השערה לא מפורסמת של גאוס מ-1796. פורסמה לראשונה על ידי דיריכלה ב-1849, והוכחה לבסוף על ידי Arnold Walfisz.
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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