Euler's totient function φ(n)

What is Euler's totient?

φ(n) counts integers from 1 to n that are coprime to n (GCD = 1). For n = 12: the coprimes are 1, 5, 7, 11, so φ(12) = 4.

Formula

φ(n) = n × ∏(1 − 1/p) for each distinct prime p dividing n.

Example: φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12.

Special values

φ(p) = p − 1 for any prime p. φ(p^k) = p^k − p^(k−1). φ(1) = 1.

Euler's theorem

If GCD(a, n) = 1, then a^φ(n) ≡ 1 (mod n). This generalizes Fermat's little theorem and is the basis of RSA cryptography.