phifunktsioon

Phifunktsioon, also called Euler’s totient function, is a number-theoretic function denoted φ(n) that counts the positive integers up to n that are coprime to n. Formally, φ(n) = |{k : 1 ≤ k ≤ n, gcd(k, n) = 1}|. It is defined for positive integers n, with φ(1) = 1.

Key properties include multiplicativity: φ(ab) = φ(a)φ(b) whenever gcd(a, b) = 1. For prime powers, φ(p^k) = p^k − p^{k−1} = p^{k−1}(p − 1). For a general n with factorization n = ∏ p_i^{a_i}, φ(n) = ∏ φ(p_i^{a_i}) = ∏ p_i^{a_i−1}(p_i − 1) = n ∏_{p|n}(1 − 1/p). The totient also equals the size of the group of units modulo n, i.e., |(Z/nZ)×|.

Examples help illustrate: φ(36) = 12 since 36 = 2^2·3^2 and φ(36) = 36(1 − 1/2)(1 − 1/3) = 12; φ(10) = 4 because 10 = 2·5 and φ(10) = 10(1 − 1/2)(1 − 1/5) = 4. By convention, ∑_{d|n} φ(d) = n.

Applications of the phifunktsioon include counting coprime residues modulo n and cryptographic uses such as RSA-style key generation, where a public exponent e is chosen with gcd(e, φ(n)) = 1. Related functions include Carmichael’s λ(n), which sometimes yields smaller values, and Jordan’s totient functions, which generalize φ.