Euler's totient

Picture the numbers from 1 up to n and ask how many of them are strangers to n in the sense of sharing no common factor. That count is what Euler's totient measures: it tallies the integers in that range that are relatively prime to n.

Written φ(n) (the Greek letter phi), it is the number of integers k with 1 ≤ k ≤ n and gcd(k, n) = 1. For a prime p every smaller positive number is coprime to it, so φ(p) = p − 1. The function is multiplicative for coprime inputs — φ(m n) = φ(m) φ(n) when gcd(m, n) = 1 — and for a prime power, φ(p^k) = p^k − p^(k−1). Combining these gives a formula from the prime factorization: φ(n) = n times the product of (1 − 1/p) over all primes p dividing n.

The totient is the backbone of Euler's theorem, a^(φ(n)) ≡ 1 (mod n) for a coprime to n, which in turn underlies the RSA cryptosystem. A common stumble: φ is not multiplicative for inputs that share a factor — φ(2 times 2) = φ(4) = 2, not φ(2) times φ(2) = 1 — so the multiplicative property strictly requires coprime arguments.