מחשבון פונקציית אוילר

אודות מחשבון זה

מחשבון זה מוצא את פונקציית אוילר φ(n) — מספר המספרים השלמים החיוביים בין 1 ל-n שזרים ל-n (אין להם עם n מחלק משותף פרט ל-1). היא מחושבת מהפירוק לגורמים ראשוניים של n בעזרת נוסחת המכפלה φ(n) = n·∏(1 − 1/p) על פני כל גורם ראשוני שונה p של n; עבור ראשוני p עצמו, φ(p) = p − 1.

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