totients

Totients, in number theory, usually refer to Euler's totient function φ(n). For a positive integer n, φ(n) counts the integers k with 1 ≤ k ≤ n that are relatively prime to n. By convention φ(1) = 1.

If n factorizes as n = ∏ p_i^{a_i} into distinct primes p_i, then φ(n) = ∏ (p_i^{a_i} − p_i^{a_i−1}) = ∏ p_i^{a_i−1}(p_i − 1). Equivalently, φ(n) = n ∏_{p|n} (1 − 1/p).

Key properties: φ is multiplicative, meaning φ(ab) = φ(a)φ(b) whenever gcd(a,b) = 1. For prime powers, φ(p^a) = p^a − p^{a−1}.

Examples: φ(10) = 4; φ(12) = 4; φ(1) = 1; φ(7) = 6.

Several facts: φ(n) is even for n > 2. The sum of φ(k) for k ≤ n is asymptotically 3n^2/π^2. Euler's theorem states that if gcd(a,n) = 1, then a^{φ(n)} ≡ 1 (mod n).

Applications include cryptography (notably RSA, which uses φ(n) when n is a product of two primes) and various counting problems where the coprimality constraint arises.

Related notions include Jordan's totient function J_k(n), which counts k-tuples of integers up to n that are coprime to n, and the Carmichael function, which gives the smallest exponent with a^λ(n) ≡ 1 mod n for all a coprime to n.