totient

Totient, usually Euler's totient function φ(n), counts the positive integers up to n that are relatively prime to n. In other words, φ(n) is the number of reduced residues modulo n. For example, φ(12) = 4, since among 1 through 12 only 1, 5, 7, and 11 are coprime to 12.

If n = ∏ p_i^{a_i} is the prime factorization of n, then φ(n) = ∏ p_i^{a_i-1}(p_i - 1). Equivalently, φ(n) = n ∏_{p|n} (1 - 1/p). The function is multiplicative: if gcd(m,n) = 1, then φ(mn) = φ(m)φ(n). Also φ(1) = 1.

For a prime power, φ(p^k) = p^k - p^{k-1} = p^{k-1}(p-1). φ(n) is even for n > 2. It also equals the number of units in the ring Z/nZ, i.e., the integers mod n that have a multiplicative inverse.

Computing φ(n) requires factoring n. The totient function appears in various number theoretic contexts, such as counting primitive roots and in cryptographic applications (for example, RSA) where φ(n) governs certain key-generation aspects.

Generalizations include Jordan's totient function J_k(n) = n^k ∏_{p|n} (1 - p^{-k}); J_1(n) = φ(n). The Carmichael function λ(n) gives the exponent of the multiplicative group of units modulo n. When primitive roots modulo n exist, their number is φ(φ(n)).