gen-define-euler-s-totient-function-and-give-one-short-worked-ex-8976

Define Euler's totient function and give one short worked example.

# Euler's Totient Function **Definition:** Euler's totient function φ(n) counts the number of positive integers less than or equal to n that are relatively prime to n (i.e., that have gcd with n equal to 1). ## Worked Example Find φ(12). We need to count integers from 1 to 12 that share no common factors with 12. Since 12 = 2² × 3, an integer is relatively prime to 12 if and only if it's divisible by neither 2 nor 3. List: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 Relatively prime to 12: **1, 5, 7, 11** Therefore, **φ(12) = 4**. --- *Note: For prime powers, there's a formula: φ(p^k) = p^k - p^(k-1). More generally, φ(12) = φ(2²)φ(3) = (4-2)(3-1) = 2 × 2 = 4.*