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

פונקציית אוילר נקראת על שם אוילר. מסמנים אותה φ (פי). φ(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}. הפונקצ...