Euler's Totient Function φ(n)
n (positive integer ≤ 1,000,000)
φ(n) = count of integers from 1 to n that are coprime to n.
Euler's totient function φ(n) counts how many integers from 1 to n are coprime to n (share no common factor other than 1). It is fundamental in number theory and RSA encryption.
- 1For prime p: φ(p) = p−1
- 2φ(pᵏ) = pᵏ−pᵏ⁻¹
- 3Multiplicative: φ(mn) = φ(m)φ(n) when gcd(m,n)=1
- 4φ(12) = φ(4)×φ(3) = 2×2 = 4
φ(12)=4 (coprime: 1,5,7,11)
φ(7)=6 (prime: all 1–6 are coprime)
| n | φ(n) | Coprime integers |
|---|---|---|
| 6 | 2 | 1,5 |
| 10 | 4 | 1,3,7,9 |
| 12 | 4 | 1,5,7,11 |
| 20 | 8 | 1,3,7,9,11,13,17,19 |
References
🔒
100% Gratis
Ingen registrering
✓
Præcis
Verificerede formler
⚡
Øjeblikkelig
Resultater med det samme
📱
Mobilvenlig
Alle enheder